我正在研究一种在六边形网格中查找路径的算法。为此,我使用深度优先搜索,深度为 3。它的工作原理是找到正确的路径。唯一的问题是它不返回它。相反,它返回一个空集。
public Set findPath(Game game, Point origin, Point destination, Set<Point> hasVisited, int depth) throws Exception {
if (origin.equals(destination)){
System.out.println("Return from goal requirements: " + hasVisited);
return hasVisited;
}
if (!origin.equals(destination)){
if (depth != 0) {
for (Point emptyNeighbor : getEmptyNeighbors(game, origin)) {
if (!hasVisited.contains(emptyNeighbor)) {
if (!game.isHiveBrokenAfterPush(origin, emptyNeighbor)) {
hasVisited.add(emptyNeighbor);
game.push(origin.x, origin.y, emptyNeighbor.x, emptyNeighbor.y);
findPath(game, emptyNeighbor, destination, actualOrigin, hasVisited, depth - 1);
hasVisited.remove(emptyNeighbor);
game.push(emptyNeighbor.x, emptyNeighbor.y, origin.x, origin.y);
}
}
}
}
}
System.out.println("Return from end of function: " + hasVisited);
return hasVisited;
}
加载 If 语句后,它将节点添加到 hasVisited 并将该片段推向该方向。然后它调用自己继续在树的分支上。它会删除 hasVisited 形式的节点,如果不起作用则取消推送。
现在发生的情况是,最终的返回似乎来自函数的 and 。这些是它打印的最后几行:
Return from goal requirements: [java.awt.Point[x=-1,y=0], java.awt.Point[x=-2,y=1], java.awt.Point[x=-2,y=2]]
Return from end of function: [java.awt.Point[x=-1,y=0], java.awt.Point[x=-2,y=1]]
Return from end of function: [java.awt.Point[x=-1,y=0]]
Return from end of function: []
[]
上面的坐标集是它应该返回的。但如您所见,它返回一个空集。
我尝试返回 findPath 而不是仅仅执行它。这样做只会执行一个分支。它不会取消无效的 Action 。我在代码中看不到问题,希望你们能帮助我。干杯!
最佳答案
如果只有一种解,则立即返回。 递归将一个元素添加到集合中,递归调用并撤消添加。 这将改变集合和结果。当收集多个结果时,人们会复制该组结果。
public boolean findPath(Game game, Point origin, Point destination, Set<Point> hasVisited,
int depth) throws Exception {
if (origin.equals(destination)){
System.out.println("Return from goal requirements: " + hasVisited);
return true;
}
if (depth != 0) {
for (Point emptyNeighbor : getEmptyNeighbors(game, origin)) {
if (!hasVisited.contains(emptyNeighbor)) {
if (!game.isHiveBrokenAfterPush(origin, emptyNeighbor)) {
hasVisited.add(emptyNeighbor);
game.push(origin.x, origin.y, emptyNeighbor.x, emptyNeighbor.y);
boolean found = findPath(game, emptyNeighbor,
destination, actualOrigin, hasVisited, depth - 1);
if (found) {
return true;
}
hasVisited.remove(emptyNeighbor);
game.push(emptyNeighbor.x, emptyNeighbor.y, origin.x, origin.y);
}
}
}
}
System.out.println("Not found");
return false;
}
关于java - 我无法返回深度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58943451/