A-Star寻路选择了不好的航点

Question

---

已解决：非常抱歉，我错误地重构了路径。我以为closedSet只有从起点到终点的所有航点，但它还有其他航点。我误解了这个概念。现在它可以正常工作了！

---

我仍然在使用A*算法时遇到一些问题。

我的角色正在寻找他的路径，但有时候，根据我在地图上点击的位置不同，算法会找到最短路径或路径，但选择了许多不应该选择的节点。

我尝试遵循维基百科和A* Pathfinding for Beginner's的实现，但它们给我相同的结果。我不知道是启发式函数还是算法本身有问题，但肯定有问题。

这是两个不同节点的单击问题示例：http://i.imgur.com/gtgxi.jpg

这是Pathfind类：

import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

public class Pathfind {
public Pathfind(){

}

public ArrayList<Node> findPath(Node start, Node end, ArrayList<Node> nodes){

    ArrayList<Node> openSet = new ArrayList<Node>();
    ArrayList<Node> closedSet = new ArrayList<Node>();

    Node current;

    openSet.add(start);

    while(openSet.size() > 0){

        current = openSet.get(0);

        current.setH_cost(ManhattanDistance(current, end));

        if(start == end) return null;           
        else if(closedSet.contains(end)){
            System.out.println("Path found!");
            return closedSet;
        }

        openSet.remove(current);
        closedSet.add(current);

        for(Node n : current.getNeigbours()){           
            if(!closedSet.contains(n)){     
                if(!openSet.contains(n) || (n.getG_cost() < (current.getG_cost()+10))){ 
                    n.setParent(current);
                    n.setG_cost(current.getG_cost()+10);
                    n.setH_cost(ManhattanDistance(n, end));

                        if(!openSet.contains(n))
                            openSet.add(n);

                    Collections.sort(openSet);
                }
            }
        }
    }       

    return null;
}

private int ManhattanDistance(Node start, Node end){
    int cost = start.getPenalty();

    int fromX = start.x, fromY = start.y;
    int toX = end.x, toY = end.y;

    return cost * (Math.abs(fromX - toX) + Math.abs(fromY - toY));
}

}

- Jh62

---

你有5个嵌套的if语句——我建议使用或条件或将它们全部放在返回布尔值的方法中。 - tehdoommarine

请添加有关地图的更多详细信息。根据地图类型，不同的距离度量可能或可能不正确地用作启发式方法。 - Abhinav Sarkar

只是一条评论 - 我认为将closedSet选择为ArrayList不够高效。每个contains()操作都是O(n)（其中n是关闭节点的数量）。您应该使用一个Set来获得更好的性能 - HashSet是一个明智的选择，如果您想保持插入顺序 - 您应该使用LinkedHashSet。（请注意，您将需要重写Node的equals()和hashCode()方法） - amit

Answer 1

我认为问题出在这个条件上：

if(n.getCost() < current.getCost()){

如果成本（g(node)+h(node)）正在降低，您不应该阻止前进。看看这个反例：（S是源，T是目标）

_________
|S |x1|x2|
----------
|x3|x4|x5|
---------
|x6|x7|T |
----------

现在假设您在S点，还没有移动，因此g(S) = 0，并且在曼哈顿距离启发式下，h(S) = 4，因此您得到f(S)=4

现在，看一下x1,x3：假设您对每个点走一步，它们将具有g(x1)=g(x3)=1，并且在相同的启发式下，两个点都会有h(x1)=h(x3)=3。这将导致f(x1)=f(x3)=4 - 您的if条件不会使任何一个“打开”，因此一旦您完成对S的迭代，您将不会将任何东西推送到open中-您的搜索将终止。

---

顺便提一下：
我认为选择closedSet作为ArrayList不够高效。每个contains()操作的时间复杂度是O(n)（其中n是关闭节点的数量）。您应该使用Set以获得更好的性能- HashSet是一个明智的选择，如果您想保持插入顺序- 您应该使用LinkedHashSet。（请注意，您将需要重写Node的equals()和hashCode()方法）

- amit

---

我现在不关心速度，这只是一个测试。我首先需要让它工作起来。无论如何，感谢您的建议。我一直在阅读相关资料。 - Jh62

@user1656222：答案中的主要问题仍然存在。所提到的条件是错误的，因此算法失败了。速度问题只是一个附注，您现在可以忽略它，专注于答案中提到的其他问题。 - amit

Answer 2

你的单位只能向上/下/左/右走，还是可以斜着走？

A*算法的一个要求是它必须是可接受的- 它永远不能过度估计实际路径长度。如果你的单位可以斜着走，那么曼哈顿距离会高估路径长度，因此无法保证A*算法的有效性。

- BlueRaja - Danny Pflughoeft

---

但是为什么没有找到路径呢？即使没有可接受的启发式函数，A仍然是完整的，只是不是最优的，所以我会怀疑它已经找到了一条路径——只是不是最短的路径。此外，如果允许对角线（假设对角线仍被计算为一步），欧几里得距离仍然不是可接受的——对于距离为1的情况，h=sqrt(2)，而h=1。 - amit

我的单位不能对角线移动。我已经上传了一张新图片，展示算法选择的路径、相邻节点和选定节点（目标）。 - Jh62