java如何在并非所有节点都使用*算法连接的情况下找到最短路径？

Question

我正在尝试使用A*算法寻找从公交车站A到公交车站B的最短路径/最佳路径，其中包含车站A的公交路线和包含车站B的公交路线可能没有公共公交车站

（我还想改变搬家的费用，以便尽可能少地乘坐公交车到达目的地）

MyBusRoute类包含一个公交站点的链接列表，每个站点都有一个名称、纬度和经度

我用来表示*中的状态的节点类：

public class Node
{
    double gCost;
    double hHeuristic;
    double f;//f=g+h
    Node parent;
    BusStation station;//contains lat,lng name
    String reached;//is either "Bus" or "Walking" , how i reached this node
    int busRouteId;//via which route i reached this station
}

gCost是两个站点之间的Havesine距离

hHeuristic是当前电台和目标之间的正弦距离

我不断扩展优先级队列中f值最低的节点，直到它有了目标站

这是我从当前节点生成所有可能转换的部分：

ArrayList<Node> posibleMoves=getPosibleMoves(current);
    for(Node p:posibleMoves){
        if(!visitedNodes.contains(p) ) {
            double predictedDistance = calculateHeuristic(p, goal);
            double cost;
            if (p.getReached().equals("Walking")) {
                cost=(10* havesineDistance(current.getLat(), current.getLng(), p.getLat(), p.getLng())) + current.getgCost();
            } else { //Reached using a bus
                cost=havesineDistance(current.getLat(), current.getLng(), p.getLat(), p.getLng()) + current.getgCost();
            }
            p.setgCost(cost);
            p.sethHeuristic(predictedDistance);
            p.setF(cost + predictedDistance);
            p.setParent(current);
            priorityQueue.add(p);
        }
    }
}

getPossibleMoves(current)查找包含此站点的所有公交线路，并将每个找到的线路中的下一个站点添加到arraylist中

之后，它会向不包含该站点的其他每一条公交线路添加“步行”节点，尝试以这种方式将这些线路连接起来。 （它查找从每条路线到当前车站最近的车站）

我将步行到达的节点的成本设置为成本的10倍，因为人的速度大约是公共汽车的10倍

运行该程序后，我没有得到预期的结果，它要么改变了太多的公交车，要么似乎是无缘无故地走路。 此外，在检查优先级队列后，有时它不会轮询f值最低的节点

这是解决这个问题的好办法吗？我错过什么了吗

Answer 1

大多数编程初学者低估了实现路径规划算法的难度。A*不是一项容易的任务，特别是当它与其他约束一起使用时。它必须定义为中等规模的软件项目。我猜一个普通的a*算法需要500行代码，而带有优先级队列和启发式的OP的扩展变体需要1000行代码。在软件工程中，使用UML图表来描述不同类的交互是一个很好的实践。所以我的建议是，从互联网上下载dia软件，在图表中画出大约10个类来解A*算法。在没有任何UML图表的情况下编程pathplanner，并希望用一种小方法来实现，这是一种盲目的飞行

这里有两个用于路径规划应用程序的示例UML图表：[1][2]它们不能开箱即用，但它们显示了项目应该朝哪个方向发展。它们有大约10-15个框与边缘连接，这些框描述了一个包含大量类和方法的复杂软件项目。否则，复杂程度无法处理