Java - 打印路线和费用

Question

我有一个用 Java 编写的 A* 搜索算法，我希望它能够打印旅行路线，以便用户可以看到它尝试过哪些路线以及哪条路线是最佳路线。目前它只打印最佳路线，这很好，我希望它这样做，但我也希望它打印路线列表，以便您可以看到每条路线的最坏情况和相关成本。 从下面的代码中，如果我打印 followedRoute 打印出每一次旅行，但我可以打印每一次旅行的费用吗？该算法通过查找每个完整的旅行和这些旅行的最低成本来工作，理想情况下我只想打印完整的旅行而不是 {0}、{0、3} 等。

下面是我认为相关的代码段，如果你还需要看的话请问:)

---

Cities aux = currentCities;
ArrayList followedRoute = new ArrayList();
followedRoute.add(aux.number);
while (aux.level != 0) {
    aux = aux.parent;
    followedRoute.add(0, aux.number);
}

if (currentCities.level == distances.getCitiesCount()) {
    solution = true;
    bestRoute = followedRoute;
    bestCost = currentCities.g;
} else {
    for (int i=0; i<distances.getCitiesCount(); i++) {
        // have we visited this city in the current followed route?
        boolean visited = followedRoute.contains(i);
        boolean isSolution = (followedRoute.size() == distances.getCitiesCount())&&(i == firstNode);

        if (!visited || isSolution) {
            Cities childCities = new Cities(i, currentCities.g + distances.getCost(currentCities.number, i), 
                    getHeuristicValue(currentCities.level + 1), currentCities.level + 1);
            childCities.parent = currentCities;
            opened.add(childCities);  
            System.out.println(followedRoute);
        }
    }                
}

---

非常感谢任何帮助!提前致谢:)

Answer 1

好吧，你将很难修改 A* 来这样做，而且效率会非常低¹。

事实上，没有已知的算法来做你想要的，它被称为 longest path problem , 它是 NP-Hard , 所以它没有已知的多项式解。

(凭直觉，为什么它是真的 - 想一想一种算法，它可以从顶点 v 找到最长的简单路径 - 给定这样的算法 - 可以很容易地确定是否存在来自 v，重复这个过程，检查图中是否有hamiltonian path。因为Hamiltonian Path Problem是NP-Hard，所以这道题也是。

找到最长路径的一种方法是使用蛮力(搜索所有可能的路径)。可以使用对 DFS 的修改来实现(忘记“访问过”的节点)，并递归检查图中的所有路径 - 直到所有路径都用完 - 并返回其中最长的路径。

对于令人失望的消息，我们深表歉意，但我希望它至少不会让您将时间花在(很可能)无法(高效)完成的事情上。

---

(1) Assuming P!=NP ，这是大多数 CS 研究人员的共同信念。