出于某种原因，我的双向 A* 实现在非常具体的图形初始化中没有返回最短路径。
我正在运行两个 A* 搜索，一个从源到目标，另一个从目标到源。从我所读到的内容来看，当这两个搜索的闭合集相交时，我们已经连接了两个搜索的最短路径并找到了最短路径。
问题是，在非常特殊的情况下，两个搜索的闭集在搜索实际发现应包含在各自最短路径中的节点之前是相交的。这意味着 A* 无法探索足够的节点来找到最短路径。
这个交叉条件是正确的处理方式，还是我应该使用不同的条件来确定何时停止两次搜索？
你可以在这里运行我的代码：https://jasperhuangg.github.io/pathfinding-visualizer。
发生此问题的情况是某些(不是全部(情况，即壁和重物都放置在网格上。
如果有帮助，这是代码，如果它很乱，对不起！
async function bidirectionalAStar(graph, startNode, finishNode) {
recolorGrid();
searching = true;
const infinity = Number.MAX_VALUE;
var openSource = [];
var openDest = [];
var closedSource = [];
var closedDest = [];
var numSteps = -3; // -2 for both start and finish nodes + -1 for overlapping connecting node
$("#steps-taken").html("Cells Examined: " + numSteps);
const startX = startNode.x;
const startY = startNode.y;
const finishX = finishNode.x;
const finishY = finishNode.y;
var bidirectionalAStarGraph = shallowCopyGraph(graph, []);
// initialize all nodes to dist infinity from the startNode
for (let i = 0; i < bidirectionalAStarGraph.length; i++) {
for (let j = 0; j < bidirectionalAStarGraph[i].length; j++) {
bidirectionalAStarGraph[i][j].fSrc = infinity;
bidirectionalAStarGraph[i][j].gSrc = infinity;
bidirectionalAStarGraph[i][j].hSrc = infinity;
bidirectionalAStarGraph[i][j].fDest = infinity;
bidirectionalAStarGraph[i][j].gDest = infinity;
bidirectionalAStarGraph[i][j].hDest = infinity;
bidirectionalAStarGraph[i][j].setSource = "neither";
bidirectionalAStarGraph[i][j].setDest = "neither";
}
}
// initialize start/finish node distance from start/finish to 0
bidirectionalAStarGraph[startX][startY].fSrc = 0;
bidirectionalAStarGraph[startX][startY].gSrc = 0;
bidirectionalAStarGraph[startX][startY].hSrc = 0;
bidirectionalAStarGraph[startX][startY].setSource = "open";
openSource.push(bidirectionalAStarGraph[startX][startY]);
bidirectionalAStarGraph[finishX][finishY].fDest = 0;
bidirectionalAStarGraph[finishX][finishY].gDest = 0;
bidirectionalAStarGraph[finishX][finishY].hDest = 0;
bidirectionalAStarGraph[finishX][finishY].setDest = "open";
openDest.push(bidirectionalAStarGraph[finishX][finishY]);
var lastNodeSource;
var lastNodeDest;
while (openSource.length > 0 && openDest.length > 0) {
openSource.sort((a, b) => {
if (a.fSrc !== b.fSrc) return a.fSrc - b.fSrc;
else return a.hSrc - b.hSrc;
});
openDest.sort((a, b) => {
if (a.fDest !== b.fDest) return a.fDest - b.fDest;
else return a.hDest - b.hDest;
});
var currNodeSource = openSource.shift();
var currNodeDest = openDest.shift();
$(".currentNodeGray").removeClass("currentNodeGray");
$(".currentNodeSunset").removeClass("currentNodeSunset");
$(".currentNodeOcean").removeClass("currentNodeOcean");
$(".currentNodeChaos").removeClass("currentNodeChaos");
$(".currentNodeGreen").removeClass("currentNodeGreen");
$(".currentNodeCottonCandy").removeClass("currentNodeCottonCandy");
if (checkIntersection(closedSource, closedDest)) {
break; // the paths have reached each other
}
numSteps += 2;
$("#steps-taken").html("Cells Examined: " + numSteps);
currNodeSource.setSource = "closed";
currNodeDest.setDest = "closed";
closedSource.push(currNodeSource);
closedDest.push(currNodeDest);
colorNode(currNodeSource, "currentNode");
colorNode(currNodeDest, "currentNode");
if (lastNodeSource !== undefined && currentSpeed !== "instantaneous")
colorNode(lastNodeSource, "visited");
if (lastNodeDest !== undefined && currentSpeed !== "instantaneous")
colorNode(lastNodeDest, "visited");
if (currentSpeed === "fast") await sleep(20);
else if (currentSpeed === "medium") await sleep(180);
else if (currentSpeed === "slow") await sleep(500);
var validNeighborsSource = [];
var validNeighborsDest = [];
var left = currNodeSource.x - 1;
var right = currNodeSource.x + 1;
var up = currNodeSource.y - 1;
var down = currNodeSource.y + 1;
// consider all of the current node's (from source) valid neighbors
if (left >= 0 && !bidirectionalAStarGraph[left][currNodeSource.y].blocked) {
validNeighborsSource.push(
bidirectionalAStarGraph[left][currNodeSource.y]
);
}
if (
right < grid_width &&
!bidirectionalAStarGraph[right][currNodeSource.y].blocked
) {
validNeighborsSource.push(
bidirectionalAStarGraph[right][currNodeSource.y]
);
}
if (up >= 0 && !bidirectionalAStarGraph[currNodeSource.x][up].blocked) {
validNeighborsSource.push(bidirectionalAStarGraph[currNodeSource.x][up]);
}
if (
down < grid_height &&
!bidirectionalAStarGraph[currNodeSource.x][down].blocked
) {
validNeighborsSource.push(
bidirectionalAStarGraph[currNodeSource.x][down]
);
}
left = currNodeDest.x - 1;
right = currNodeDest.x + 1;
up = currNodeDest.y - 1;
down = currNodeDest.y + 1;
// consider all of the current node's (from dest) valid neighbors
if (left >= 0 && !bidirectionalAStarGraph[left][currNodeDest.y].blocked) {
validNeighborsDest.push(bidirectionalAStarGraph[left][currNodeDest.y]);
}
if (
right < grid_width &&
!bidirectionalAStarGraph[right][currNodeDest.y].blocked
) {
validNeighborsDest.push(bidirectionalAStarGraph[right][currNodeDest.y]);
}
if (up >= 0 && !bidirectionalAStarGraph[currNodeDest.x][up].blocked) {
validNeighborsDest.push(bidirectionalAStarGraph[currNodeDest.x][up]);
}
if (
down < grid_height &&
!bidirectionalAStarGraph[currNodeDest.x][down].blocked
) {
validNeighborsDest.push(bidirectionalAStarGraph[currNodeDest.x][down]);
}
// UPDATE NEIGHBORS FROM SOURCE
for (let i = 0; i < validNeighborsSource.length; i++) {
let neighbor = validNeighborsSource[i];
if (neighbor.setSource === "closed") continue;
let cost = 0;
if (currNodeSource.weighted === true || neighbor.weighted === true)
cost = currNodeSource.gSrc + 10;
else cost = currNodeSource.gSrc + 1;
if (neighbor.setSource === "open" && cost < neighbor.gSrc) {
neighbor.setSource = "neither";
neighbor.gSrc = cost;
neighbor.fSrc = neighbor.gSrc + neighbor.hSrc;
openSource.remove(neighbor);
}
if (neighbor.setSource === "neither") {
openSource.push(neighbor);
neighbor.setSource = "open";
neighbor.gSrc = cost;
neighbor.hSrc = calculateHeuristic(neighbor, finishNode);
neighbor.fSrc = neighbor.gSrc + neighbor.hSrc;
neighbor.predecessorSource = currNodeSource;
}
}
lastNodeSource = currNodeSource;
// UPDATE NEIGHBORS FROM DEST
for (let i = 0; i < validNeighborsDest.length; i++) {
let neighbor = validNeighborsDest[i];
if (neighbor.setDest === "closed") continue;
let cost = 0;
if (currNodeDest.weighted === true || neighbor.weighted === true)
cost = currNodeDest.gDest + 10;
else cost = currNodeDest.gDest + 1;
if (neighbor.setDest === "open" && cost < neighbor.gDest) {
neighbor.setDest = "neither";
neighbor.gDest = cost;
neighbor.fDest = neighbor.gDest + neighbor.hDest;
openDest.remove(neighbor);
}
if (neighbor.setDest === "neither") {
openDest.push(neighbor);
neighbor.setDest = "open";
neighbor.gDest = cost;
neighbor.hDest = calculateHeuristic(neighbor, startNode);
neighbor.fDest = neighbor.gDest + neighbor.hDest;
neighbor.predecessorDest = currNodeDest;
}
}
lastNodeDest = currNodeDest;
}
没有任何代码，我无法识别您的算法中的任何特定错误，但关于双向 A* 的事情是它只和你的 A* 一样好。
A* 是灵活的，因为它能够像哑广度优先搜索和哑深度优先搜索一样起作用 - 通常它位于中间的某个地方，而"中间"由启发式的质量定义。
在另一侧添加第二个 A* 是"加速"倾向于广度的 A* 启发式的好方法，但是，它不会"修复"倾向于深度的启发式。
如果您希望保证双向 A* 搜索始终能找到最短的路径，那么您的启发式搜索需要倾向于广度。 (通常这是通过估计启发式来完成的 - 一个节点的想象探索成本，如曼哈顿到目标的距离加上到该节点的距离。 然后对节点进行排序，并将节点抛出最低节点的 1.5 倍以上——1.5 是一个你可以玩的变量，太高了，你会先做一个传统的宽度，太低，你可能会抛出实际的最低路径，如果它是一个复杂的路径。
很抱歉含糊不清，一些代码片段可能有助于提供更多方向！