在协调无向图上计算 A*(A-star) 算法中的 f 成本
Calculate the f cost in A*(A-star) algorithm on coordinated undirected graph
我正在尝试在 react.js 中实现 A* 算法，但在实现 fScore 函数时我遇到了困难。我知道 f=g+h 其中 g 是从起始节点到当前节点的 gScore，h 是从当前节点到结束节点的启发式距离。我使用欧氏距离计算了启发式方法，我在其中发送了当前节点和结束节点的坐标，但我不知道如何计算 gScore。
我图中的每个节点都有：
ID，
名称，
X，
是的，
connectedToIds:[] //neihbours 或 connectedNodes 列表。 更新： 我向每个节点添加了变量 parentId、fscore、gscore、hscore。所以现在每个节点都有变量：id，
名称，
X，
是的，
connectedToIds:[],
f分数：0，
g分数：0，
hscore: 0,
父母身份：空。
Update2: originLocationId为起始节点id。 destinationLocationId 是结束节点的 id。 locations 是所有节点的列表。
我的代码：
export default class TurnByTurnComponent extends React.PureComponent {
constructor(props) {
super(props);
}
render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
console.log(locations)
console.log(originLocationId)
console.log(destinationLocationId)
var openedList = [];
var closedList = [];
if (destinationLocationId != null && originLocationId != null) {
openedList.push(originLocationId);
while (openedList.length != 0) {
var currentLoc = openedList[0]; //minFvalue
const currIndex = openedList.indexOf(currentLoc);
openedList.splice(currIndex, 1); //deleting currentNode from openedList
closedList.push(currentLoc) //adding currentNode to closedList
if (currentLoc == destinationLocationId) {
//return path
}
}
}
function heuristic(currentNode, endNode) { //euclidean distance
var x = Math.pow(endNode.x - currentNode.x, 2);
var y = Math.pow(endNode.y - currentNode.y, 2);
var dist = Math.sqrt(x + y);
return dist;
}
function gScore(startNode, currentNode) {
}
return (
<div className="turn-by-turn-component">
{locations.map(loc => (
<li key={loc.id}>
{loc.name}
</li>
))}
<TodoList
title="Mandatory work"
list={[
]}
/>
<TodoList
title="Optional work"
list={[
]}
/>
</div>
);
}
}
TurnByTurnComponent.propTypes = {
destinationLocationId: PropTypes.number,
locations: PropTypes.arrayOf(PropTypes.shape({
id: PropTypes.number.isRequired,
name: PropTypes.string.isRequired,
x: PropTypes.number.isRequired,
y: PropTypes.number.isRequired,
connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
})),
originLocationId: PropTypes.number
};
Update3：我的代码的新版本
export default class TurnByTurnComponent extends React.PureComponent {
constructor(props) {
super(props);
this.state = { shortestPath: [] }
}
render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
if (destinationLocationId != null && originLocationId != null) {
if (originLocationId == destinationLocationId) { //check if the startNode node is the end node
return originLocationId;
}
var openList = [];
let startNode = getNodeById(originLocationId);
let endNode = getNodeById(destinationLocationId)
startNode.gcost = 0
startNode.heuristic = manhattanDistance(startNode, endNode)
startNode.fcost = startNode.gcost + startNode.heuristic;
//start A*
openList.push(startNode); //starting with the startNode
while (openList.length) {
console.log("inside while")
var currentNode = getNodeOfMinFscore(openList);
if (currentIsEqualDistanation(currentNode)) {
var path = getPath(currentNode)
this.setState({
shortestPath: path,
});
return path //todo
}
deleteCurrentFromOpenList(currentNode, openList);
for (let neighbourId of currentNode.connectedToIds) {
var neighbourNode = getNodeById(neighbourId);
var currentNodeGcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
console.log(currentNodeGcost)
console.log(neighbourNode.gcost)
if (currentNodeGcost < neighbourNode.gcost) {
console.log("Helloooo")
neighbourNode.parentId = currentNode.id;
// keep track of the path
// total cost saved in neighbour.g
neighbourNode.gcost = currentNodeGcost;
neighbourNode.heuristic = manhattanDistance(neighbourNode, endNode);
neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
if (!openList.includes(neighbourId)) {
openList.push(neighbourNode);
}
}
}
}
return null;
}
function deleteCurrentFromOpenList(currentNode, openList) {
const currIndex = openList.indexOf(currentNode);
openList.splice(currIndex, 1); //deleting currentNode from openList
}
function currentIsEqualDistanation(currentNode) {
//check if we reached out the distanation node
return (currentNode.id == destinationLocationId)
}
function getNodeById(id) {
var node;
for (let i = 0; i < locations.length; i++) {
if (locations[i].id == id) {
node = locations[i]
}
}
return node
}
function getPath(endNode) {
var path = []
while (endNode.parentId) {
path.push(endNode.name)
endNode = endNode.parentId;
}
return path;
}
function getNodeOfMinFscore(openList) {
var minFscore = openList[0].fcost; //initValue
var nodeOfminFscore;
for (let i = 0; i < openList.length; i++) {
if (openList[i].fcost <= minFscore) {
minFscore = openList[i].fcost //minFvalue
nodeOfminFscore = openList[i]
}
}
return nodeOfminFscore
}
//manhattan distance is for heuristic and gScore. Here I use Manhattan instead of Euclidean
//because in this example we dont have diagnosal path.
function manhattanDistance(startNode, endNode) {
var x = Math.abs(endNode.x - startNode.x);
var y = Math.abs(endNode.y - startNode.y);
var dist = x + y;
return dist;
}
return (
<div className="turn-by-turn-component">
{locations.map(loc => (
<li key={loc.id}>
{JSON.stringify(loc.name)},
</li>
))}
<TodoList
title="Mandatory work"
list={
this.state.shortestPath
}
/>
<TodoList
title="Optional work"
list={[
]}
/>
</div>
);
}
}
TurnByTurnComponent.propTypes = {
destinationLocationId: PropTypes.number,
locations: PropTypes.arrayOf(PropTypes.shape({
id: PropTypes.number.isRequired,
name: PropTypes.string.isRequired,
x: PropTypes.number.isRequired,
y: PropTypes.number.isRequired,
connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
})),
originLocationId: PropTypes.number
};
h 是启发式算法，是对到达终点节点所需的可能成本的合理猜测，g 是到达当前节点所花费的实际成本。在您的情况下，它甚至可能与您用于 h.
的欧几里德距离相同
在真实案例中，使用欧几里得距离，连接不同城市的图表，h是两个城市的空中距离，g是他们的道路距离。
此外，如果您使用的是单调启发式算法（或低估启发式算法，例如欧几里得距离），则不需要关闭列表，因为事实证明第一个找到的路径也是最短的：更长或者已经访问过的路径将在探索之前被丢弃。
可能令人困惑的是，您需要在探索图表期间跟踪 g，而 h 只是测量当前节点和结束节点之间的直线，g 测量您探索的节点之间的所有线以达到当前。
// h
function heuristic(n1, n2) {
return Math.sqrt(
Math.pow(n1.x - n2.x, 2) +
Math.pow(n1.y - n2.y, 2)
);
}
// g - actually is the same as h
const cost = heuristic;
function astar(start, end, graph, h, g) {
if (start.id == end.id) { return [ start.id ] }
// omitted CLEAN-UP of the graph
// close is not needed with an optimistic heuristic
// so I've commented the "close" parts.
// An optimistic heuristic works also if you decomment them
// var close = [];
var open = [];
start.g = 0;
start.h = h(start, end);
start.f = start.g + start.h;
open.push(start);
while (open.length) {
// since open is sorted, by popping
// the last element we take the cheapest node
var curr = open.pop();
if (curr == end) { return resolvePath(curr, graph); }
// close.push(curr);
for (let nid of curr.connectedToIds) {
// if (close.some(n => n.id == nid)) { continue; }
var neighbour = graph.find(n => n.id == nid);
// HERE you compute and store
// the current g of the node
var current_g = curr.g + g(curr, neighbour);
var isBetter_g = false;
var isInOpen = open.some(n => n.id == nid);
// Some implementations skip this check
// because they assume that the cost function
// is a non-negative distance.
// if so you could check just the two nodes g
// and insert the node if not already in the open set
// because the default g of a node is 0
if (!isInOpen) {
// unexplored node, maybe we should explore it
// later, so we add to the open set and
// we update it with the current path cost
open.push(neighbour)
isBetter_g = true;
}
else if (current_g < neighbour.g) {
// the current path is better than
// those already explored, we need to
// update the neighbour with the current path cost
isBetter_g = true;
}
if (isBetter_g) {
// === path cost update ===
// track current path
neighbour.parent = curr.id;
// HERE you keep track of the path
// total cost saved in neighbour.g
neighbour.g = current_g;
// neighbour.h is redundant, can be stored directly in f
// but keep it for debugging purpose
neighbour.h = h(neighbour, end);
neighbour.f = neighbour.g + neighbour.h;
if (!isInOpen) {
// sorting makes the last element of
// open the cheapest node. We sort after
// the path cost update to ensure this property
open.sort((n1, n2) => n2.f - n1.f)
}
}
}
}
// failure
return []; // or return null
}
// utility to retrieve an array of ids
// from the tracked path
function resolvePath(end, graph) {
let path = [ end.id ];
while (end && end.parent >= 0) {
path.unshift(end.parent);
end = graph.find(n => n.id == end.parent);
}
return path;
}
// example of using the function
astar(startNode, endNode, locations, heuristic, cost);
我正在尝试在 react.js 中实现 A* 算法，但在实现 fScore 函数时我遇到了困难。我知道 f=g+h 其中 g 是从起始节点到当前节点的 gScore，h 是从当前节点到结束节点的启发式距离。我使用欧氏距离计算了启发式方法，我在其中发送了当前节点和结束节点的坐标，但我不知道如何计算 gScore。 我图中的每个节点都有： ID， 名称， X， 是的， connectedToIds:[] //neihbours 或 connectedNodes 列表。 更新： 我向每个节点添加了变量 parentId、fscore、gscore、hscore。所以现在每个节点都有变量：id， 名称， X， 是的， connectedToIds:[], f分数：0， g分数：0， hscore: 0, 父母身份：空。 Update2: originLocationId为起始节点id。 destinationLocationId 是结束节点的 id。 locations 是所有节点的列表。 我的代码：
export default class TurnByTurnComponent extends React.PureComponent {
constructor(props) {
super(props);
}
render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
console.log(locations)
console.log(originLocationId)
console.log(destinationLocationId)
var openedList = [];
var closedList = [];
if (destinationLocationId != null && originLocationId != null) {
openedList.push(originLocationId);
while (openedList.length != 0) {
var currentLoc = openedList[0]; //minFvalue
const currIndex = openedList.indexOf(currentLoc);
openedList.splice(currIndex, 1); //deleting currentNode from openedList
closedList.push(currentLoc) //adding currentNode to closedList
if (currentLoc == destinationLocationId) {
//return path
}
}
}
function heuristic(currentNode, endNode) { //euclidean distance
var x = Math.pow(endNode.x - currentNode.x, 2);
var y = Math.pow(endNode.y - currentNode.y, 2);
var dist = Math.sqrt(x + y);
return dist;
}
function gScore(startNode, currentNode) {
}
return (
<div className="turn-by-turn-component">
{locations.map(loc => (
<li key={loc.id}>
{loc.name}
</li>
))}
<TodoList
title="Mandatory work"
list={[
]}
/>
<TodoList
title="Optional work"
list={[
]}
/>
</div>
);
}
}
TurnByTurnComponent.propTypes = {
destinationLocationId: PropTypes.number,
locations: PropTypes.arrayOf(PropTypes.shape({
id: PropTypes.number.isRequired,
name: PropTypes.string.isRequired,
x: PropTypes.number.isRequired,
y: PropTypes.number.isRequired,
connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
})),
originLocationId: PropTypes.number
};
Update3：我的代码的新版本
export default class TurnByTurnComponent extends React.PureComponent {
constructor(props) {
super(props);
this.state = { shortestPath: [] }
}
render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
if (destinationLocationId != null && originLocationId != null) {
if (originLocationId == destinationLocationId) { //check if the startNode node is the end node
return originLocationId;
}
var openList = [];
let startNode = getNodeById(originLocationId);
let endNode = getNodeById(destinationLocationId)
startNode.gcost = 0
startNode.heuristic = manhattanDistance(startNode, endNode)
startNode.fcost = startNode.gcost + startNode.heuristic;
//start A*
openList.push(startNode); //starting with the startNode
while (openList.length) {
console.log("inside while")
var currentNode = getNodeOfMinFscore(openList);
if (currentIsEqualDistanation(currentNode)) {
var path = getPath(currentNode)
this.setState({
shortestPath: path,
});
return path //todo
}
deleteCurrentFromOpenList(currentNode, openList);
for (let neighbourId of currentNode.connectedToIds) {
var neighbourNode = getNodeById(neighbourId);
var currentNodeGcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
console.log(currentNodeGcost)
console.log(neighbourNode.gcost)
if (currentNodeGcost < neighbourNode.gcost) {
console.log("Helloooo")
neighbourNode.parentId = currentNode.id;
// keep track of the path
// total cost saved in neighbour.g
neighbourNode.gcost = currentNodeGcost;
neighbourNode.heuristic = manhattanDistance(neighbourNode, endNode);
neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
if (!openList.includes(neighbourId)) {
openList.push(neighbourNode);
}
}
}
}
return null;
}
function deleteCurrentFromOpenList(currentNode, openList) {
const currIndex = openList.indexOf(currentNode);
openList.splice(currIndex, 1); //deleting currentNode from openList
}
function currentIsEqualDistanation(currentNode) {
//check if we reached out the distanation node
return (currentNode.id == destinationLocationId)
}
function getNodeById(id) {
var node;
for (let i = 0; i < locations.length; i++) {
if (locations[i].id == id) {
node = locations[i]
}
}
return node
}
function getPath(endNode) {
var path = []
while (endNode.parentId) {
path.push(endNode.name)
endNode = endNode.parentId;
}
return path;
}
function getNodeOfMinFscore(openList) {
var minFscore = openList[0].fcost; //initValue
var nodeOfminFscore;
for (let i = 0; i < openList.length; i++) {
if (openList[i].fcost <= minFscore) {
minFscore = openList[i].fcost //minFvalue
nodeOfminFscore = openList[i]
}
}
return nodeOfminFscore
}
//manhattan distance is for heuristic and gScore. Here I use Manhattan instead of Euclidean
//because in this example we dont have diagnosal path.
function manhattanDistance(startNode, endNode) {
var x = Math.abs(endNode.x - startNode.x);
var y = Math.abs(endNode.y - startNode.y);
var dist = x + y;
return dist;
}
return (
<div className="turn-by-turn-component">
{locations.map(loc => (
<li key={loc.id}>
{JSON.stringify(loc.name)},
</li>
))}
<TodoList
title="Mandatory work"
list={
this.state.shortestPath
}
/>
<TodoList
title="Optional work"
list={[
]}
/>
</div>
);
}
}
TurnByTurnComponent.propTypes = {
destinationLocationId: PropTypes.number,
locations: PropTypes.arrayOf(PropTypes.shape({
id: PropTypes.number.isRequired,
name: PropTypes.string.isRequired,
x: PropTypes.number.isRequired,
y: PropTypes.number.isRequired,
connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
})),
originLocationId: PropTypes.number
};
h 是启发式算法，是对到达终点节点所需的可能成本的合理猜测，g 是到达当前节点所花费的实际成本。在您的情况下，它甚至可能与您用于 h.
在真实案例中，使用欧几里得距离，连接不同城市的图表，h是两个城市的空中距离，g是他们的道路距离。
此外，如果您使用的是单调启发式算法（或低估启发式算法，例如欧几里得距离），则不需要关闭列表，因为事实证明第一个找到的路径也是最短的：更长或者已经访问过的路径将在探索之前被丢弃。
可能令人困惑的是，您需要在探索图表期间跟踪 g，而 h 只是测量当前节点和结束节点之间的直线，g 测量您探索的节点之间的所有线以达到当前。
// h
function heuristic(n1, n2) {
return Math.sqrt(
Math.pow(n1.x - n2.x, 2) +
Math.pow(n1.y - n2.y, 2)
);
}
// g - actually is the same as h
const cost = heuristic;
function astar(start, end, graph, h, g) {
if (start.id == end.id) { return [ start.id ] }
// omitted CLEAN-UP of the graph
// close is not needed with an optimistic heuristic
// so I've commented the "close" parts.
// An optimistic heuristic works also if you decomment them
// var close = [];
var open = [];
start.g = 0;
start.h = h(start, end);
start.f = start.g + start.h;
open.push(start);
while (open.length) {
// since open is sorted, by popping
// the last element we take the cheapest node
var curr = open.pop();
if (curr == end) { return resolvePath(curr, graph); }
// close.push(curr);
for (let nid of curr.connectedToIds) {
// if (close.some(n => n.id == nid)) { continue; }
var neighbour = graph.find(n => n.id == nid);
// HERE you compute and store
// the current g of the node
var current_g = curr.g + g(curr, neighbour);
var isBetter_g = false;
var isInOpen = open.some(n => n.id == nid);
// Some implementations skip this check
// because they assume that the cost function
// is a non-negative distance.
// if so you could check just the two nodes g
// and insert the node if not already in the open set
// because the default g of a node is 0
if (!isInOpen) {
// unexplored node, maybe we should explore it
// later, so we add to the open set and
// we update it with the current path cost
open.push(neighbour)
isBetter_g = true;
}
else if (current_g < neighbour.g) {
// the current path is better than
// those already explored, we need to
// update the neighbour with the current path cost
isBetter_g = true;
}
if (isBetter_g) {
// === path cost update ===
// track current path
neighbour.parent = curr.id;
// HERE you keep track of the path
// total cost saved in neighbour.g
neighbour.g = current_g;
// neighbour.h is redundant, can be stored directly in f
// but keep it for debugging purpose
neighbour.h = h(neighbour, end);
neighbour.f = neighbour.g + neighbour.h;
if (!isInOpen) {
// sorting makes the last element of
// open the cheapest node. We sort after
// the path cost update to ensure this property
open.sort((n1, n2) => n2.f - n1.f)
}
}
}
}
// failure
return []; // or return null
}
// utility to retrieve an array of ids
// from the tracked path
function resolvePath(end, graph) {
let path = [ end.id ];
while (end && end.parent >= 0) {
path.unshift(end.parent);
end = graph.find(n => n.id == end.parent);
}
return path;
}
// example of using the function
astar(startNode, endNode, locations, heuristic, cost);