出于某种原因，我双向B *的实现未在图形的非常特定的初始化中返回最短路径。
我正在运行两个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作为一个可以使用的变量，太高，您将首先进行传统的广度计算，而太低，如果这是一个复杂的变量，您可能会抛弃实际的最低路径。）
很抱歉，有些代码片段可能有助于提供更多指导！