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);
        }
    }                
}

非常感谢您的帮助！提前致谢:)

- thrash

---

我认为A*算法不是那样工作的。最多你只能得到每个决策的选择和成本，但这取决于直接连接的选择。 - Karthik T

我明白了，但是为了返回最佳旅游路线，它肯定会计算每个完成的旅游的成本，对吧？ - thrash

不是的，它根据启发式函数和下一跳的成本选择最佳路线，这意味着每次跳跃都会对下一跳做出决策，而不是在结束时对所有不同的路线做出决策。 - Karthik T

Answer 1

嗯，你要修改A*算法去实现这一点会很困难，而且效率很低¹。

事实上，目前没有已知的算法可以解决你的问题，它被称为最长路径问题，并且是NP-Hard问题，因此它没有已知的多项式解决方案。

（为了直观地理解这个问题，想象一个算法，可以找到从一个节点v到另一个节点的最长简单路径 - 如果有这样的算法，就可以轻松确定是否存在从v出发的哈密顿路径，重复此过程以检查图中是否存在任何哈密顿路径。由于哈密顿路径问题是NP-Hard问题，所以这个问题也是NP-Hard问题。）

找到最长路径的一种方法是使用暴力搜索（搜索所有可能的路径）。可以通过对DFS（忘记“已访问”节点）进行修改来实现，递归地检查图中的所有路径，直到全部耗尽，并返回其中最长的路径。

很抱歉带来了令人失望的消息，但我希望至少这不会让你浪费时间在那些（很可能）无法有效完成的事情上。

---

假设P≠NP，这是大多数计算机科学研究人员的共识。

- amit