java - A* 实现中的逻辑缺陷

Question

我一直在使用其他人的 A* 寻路算法实现示例作为拐杖来帮助我编写我的第一个实现。在我发现的一个更具可读性的例子中，我在逻辑上遇到了一些麻烦。

我不是来这里拆解这段代码的，真的，我想弄清楚我是否正确，或者我是否误解了这里的机制。如果我需要回顾 A * 我会的，但如果这段代码不正确，我需要找到其他来源来学习。

在我看来，这里的逻辑有两个地方存在缺陷，都包含在这里:

for(Node neighbor : current.getNeighborList()) {
    neighborIsBetter;
    //if we have already searched this Node, don't bother and continue to the next 
    if (closedList.contains(neighbor))
        continue;

    //also just continue if the neighbor is an obstacle
    if (!neighbor.isObstacle) {

        // calculate how long the path is if we choose this neighbor as the next step in the path 
        float neighborDistanceFromStart = (current.getDistanceFromStart() + map.getDistanceBetween(current, neighbor));

        //add neighbor to the open list if it is not there
        if(!openList.contains(neighbor)) {
-->         openList.add(neighbor);
            neighborIsBetter = true;
            //if neighbor is closer to start it could also be better
-->     } else if(neighborDistanceFromStart < current.getDistanceFromStart()) {
            neighborIsBetter = true;
        } else {
            neighborIsBetter = false;
        }
        // set neighbors parameters if it is better
        if (neighborIsBetter) {
            neighbor.setPreviousNode(current);
            neighbor.setDistanceFromStart(neighborDistanceFromStart);
            neighbor.setHeuristicDistanceFromGoal(heuristic.getEstimatedDistanceToGoal(neighbor.getX(), neighbor.getY(), map.getGoalLocationX(), map.getGoalLocationY()));
        }
    }
}

source

我标记的第一行 (-->) 对我来说似乎不正确。如果您查看 implementation of the list being used (下图)它根据 heuristicDistanceFromGoal 排序在 .add 下面设置几行.

public int compareTo(Node otherNode) {
    float thisTotalDistanceFromGoal = heuristicDistanceFromGoal + distanceFromStart;
    float otherTotalDistanceFromGoal = otherNode.getHeuristicDistanceFromGoal() + otherNode.getDistanceFromStart();

    if (thisTotalDistanceFromGoal < otherTotalDistanceFromGoal) {
        return -1;
    } else if (thisTotalDistanceFromGoal > otherTotalDistanceFromGoal) {
        return 1;
    } else {
        return 0;
    }
}

我标记的第二行应该始终评估为 false。内容如下:

} else if(neighborDistanceFromStart < current.getDistanceFromStart()) {

可以简化为:

if((current.getDistanceFromStart() + map.getDistanceBetween(current, neighbor)) < current.getDistanceFromStart())

再一次:

if(map.getDistanceBetween(current, neighbor) < 0)

除了getDistanceBetween() 哪个都没问题应始终返回正值 ( see here )。

我是在轨道上还是在轨道上？

Answer 1

首先，您大部分都在正轨上。我强烈怀疑您发布的代码仍在开发中并且存在一些问题。但是，你对距离的假设仍然是积极的一般来说是不正确的。 A* 是一种图搜索算法，边通常也可以具有负权重。因此，我假设他们试图实现最一般的情况。 openList.add 对我来说似乎完全没问题。您的队列应该使用启发式距离进行排序。只需查看维基页面 https://en.wikipedia.org/wiki/A_star ，相关行是 f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)。而且，这背后的主要思想是，你总是低估了距离(可允许的启发式)；因此，如果找到目标，则没有一个未探索的节点是最优的。您可以在 http://en.wikipedia.org/wiki/Admissible_heuristic 阅读更多内容

其次，如果你想要一个稳定的 AI 代码库，你可以简单地使用 http://code.google.com/p/aima-java/ .是AIMA(Artificial Intelligence A Modern Approach)算法的实现