3

已解决：对不起。我正在不正确地重建路径。我认为 closedSet 只有从开始到结束的所有航点，但它也有其他一些航点。我想念理解这个概念。现在它工作正常！

我仍然在 A* 上遇到一些麻烦。

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

我尝试遵循Wikipedia和A* Pathfinding for Beginner 的实现，但它们给了我相同的结果。我不知道是启发式还是算法本身，但有些不对劲。

这是单击两个不同节点的问题示例：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));
}

}

4

2 回答 2

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 条件将导致 none “打开”，因此一旦您完成迭代S- 您将不会推送任何内容open- 您的搜索将终止。

附带说明：
我认为选择closedSetasArrayList效率不高。每个contains()操作是O(n)（其中n是关闭节点的数量）。你应该使用 aSet以获得更好的性能 - AHashSet是一个明智的选择，如果你想保持插入顺序 - 你应该使用 a LinkedHashSet。（请注意，您必须覆盖equals()和hashCode()的方法Node）

于 2012-09-14T08:45:57.347 回答
0

你的单位是只走上/下/左/右，还是也可以走对角线？

A* 启发式的一个要求是它是可以接受的——它绝不能高估实际的路径长度。如果您的单位可以沿对角线行走，则 manhatten-distance 将高估路径长度，因此 A* 不能保证有效。

于 2012-09-14T06:11:04.420 回答