1

我正在编写程序的一小部分，我必须在其中编写寻路算法。该函数采用所谓的“路线”，每个路线都定义了二维空间中的起点和终点。该算法需要找到最短和最有效（在一定程度上）的路径（从原点开始）以通过这些路线，从而最大限度地减少总体行驶的总距离。

我做了一些研究，并开始了一条我认为可行的道路。到目前为止，我已经将路线转换为一个有向图，它全部链接起来，就好像它是一个理想化的路线图一样。然后，我尝试在此图上执行 A* 搜索。我使用的启发式计算了剩余的“路线”的总距离，而我使用的距起点 (G) 值的距离只是到达当前点的累积距离。这适用于某些输入，但其他输入根本没有返回路径，我似乎无法弄清楚原因。

我的启发式方法是否有可能是错误的，这会导致某处的计算错误，还是 A* 程序本身更可能是错误的？还是我在这里完全走错了路？

我将把 getPath 函数放在下面（用 Java 编写）以防万一。

提前致谢。

public ArrayList<Vector2> getPath()
{
    PriorityQueue<SearchNode> openList = new PriorityQueue<SearchNode>(10, new SearchNodeComparator());
    ArrayList<SearchNode> closedList = new ArrayList<SearchNode>();

    map.startJobs();
    searchDepth = 0;

    SearchNode start = searchableGraph.getNode(new Vector2(0, 0));
    int goalsLeft = map.getJobCount();

    start.setDistanceTraveled(0);

    openList.add(start);

    while (openList.size() > 0)
    {
        SearchNode current = openList.peek();
        searchDepth++;

        if (map.isJobEndPoint(current.getValue()))
        {
            map.completeJob(current.getValue());
            goalsLeft--;

        }

        if (reachedGoalState(current, searchableGraph.getNodes().size()))
        {
            return getFinalPath(current);
        }
        else
        {
            ArrayList<SearchNode> neighbours = getNeighbours(current);

            for (int i = 0; i < neighbours.size(); i++)
            {
                SearchNode node = neighbours.get(i);        
                System.out.print("Inspecting node" + node.getValue().toString());

                float distanceTraveled = current.getDistanceTraveled() + getDistance(current.getValue(), node.getValue());

                float heuristic = heuristic(node);

                if (!openList.contains(node) && !closedList.contains(node))
                {

                    node.setDistanceTraveled(distanceTraveled);

                    node.setDistanceToGoal(distanceTraveled + heuristic);

                    node.setParent(current);

                    openList.add(node);
                }
                else if(openList.contains(node))
                {
                    if (node.getDistanceTraveled() <= distanceTraveled)
                    {

                        node.setDistanceToGoal(distanceTraveled + heuristic);


                        node.setParent(current);
                    }

                }
            }

            openList.remove(current);
            closedList.add(current);
        }
    }

    return new ArrayList<Vector2>();
}
4

1 回答 1

0

The heuristic i used calculates the total distance of the 'routes' left to travel

The heuristic used by A* must be admissible; that is, it must never over​estimate the distance to the end.

If I understand your description correctly, your heuristic is not admissible, so is not guaranteed to work.

于 2013-04-29T15:47:32.990 回答