java - 如何让我的寻路算法不走回头路？

Question

我的寻路方法是给定两个对象，其中包含 ID、名称、x/y 坐标和存储在数组列表中的路径。路径数据是它可以直接连接到的每个对象的 ID。目标是递归调用我的方法，直到它使用最短距离找到目标，当它到达终点时返回 true。

问题:如果到您来自的节点的距离比当前节点路径中的其他节点短，那么它将导致无限循环在两个节点之间来回弹跳。我已经为这个问题苦苦挣扎了几个小时，可能想多了。任何意见或建议将不胜感激!

算法:

while (!pathfound) {
    current = findPath(current, end);
}

public static Place findPath(Place curPlace, Place endPlace) {
    ArrayList<Integer> path = curPlace.path;
    int id;
    double lastdist = 999;
    double distance;
    Place bestPlace = null;

    for (int i = 0; i < path.size(); i++) {
        id = curPlace.path.get(i);
        distance = distance(getPlace(id), curPlace)
                + distance(getPlace(id), endPlace);
        if (distance < lastdist) {
            bestPlace = getPlace(id);
        } 

        lastdist = distance;
    }

    if (result.length() == 0) {
        result += bestPlace.name;
    } else {
        result += ", " + bestPlace.name;
    }

    System.out.println("CURCITY: " + bestPlace.id);
    System.out.println(result);
    System.out.println(lastdist);

    if (bestPlace == endPlace) {
        pathfound = true;
    }

    return bestPlace;
}

你可以忽略结果，它是为了跟上通过的节点。如果您想了解任何其他详细信息，请询问。

Answer 1

如果修改 Place 是可以接受的，您可以添加一个 boolean 值“已访问”标志。在运行算法之前将它们全部重置为 false；当你访问时设置为 true，当你离开时设置为 false(不要忘记在递归结束时取消设置它们 - 如果你这样做正确，你甚至可以避免在开始之前显式重置标志)。跳过标志为真的节点。

一个更短视的选择是将上次访问的 Place 作为参数传递给函数，然后跳过那个。这不会阻止更大的循环，但可能完全适合您的情况并且最容易实现。

以上两者都是 O(1) 且开销最小。如果您不能修改 Place，您可以存储一个 Set 访问过的地方(在退出递归时将它们从集合中删除)，并跳过已经在该集合中的地方.根据您的性能要求，如果您使用 HashSet，您将需要提出一个适当的散列函数。

按照这些思路，以更多内存为代价，如果您的 ID 号是唯一的并且覆盖合理大小的有限范围，则由 ID 号索引的 boolean[] 是一个常数时间替代在此处设置(它本质上是“已访问”标志选项，标志存储在外部)。