3

我在 Java 中有一个 A* 搜索算法，我希望它能够打印旅行，以便用户可以看到它尝试了哪些路线以及哪些路线是最佳路线。此刻它只打印最佳路线，这很好，我希望它这样做，但我也希望它打印路线列表，以便您可以看到每条路线的最差和相关成本。从下面的代码中，如果我打印 followRoute 打印出每个旅行，但我可以打印每个旅行的费用吗？该算法通过查找每个完整的游览和其中最低的成本来工作，理想情况下我只想打印完整的游览而不是 {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);
        }
    }                
}

非常感谢任何帮助！提前致谢 ：）

4

1 回答 1

2

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

事实上，没有已知的算法可以做你所追求的，它被称为最长路径问题，它是NP-Hard，所以没有已知的多项式解决方案。

（直觉为什么它是正确的 - 考虑一种可以从顶点找到最长简单路径的v算法 - 给定这样的算法 - 可以轻松确定是否存在来自 的哈密顿路径v，重复该过程以检查是否存在任何哈密顿路径在图中。由于哈密顿路径问题是 NP-Hard，所以这个问题也是如此。

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

很抱歉这个令人失望的消息，但我希望至少它不会让你把时间花在（很可能）无法（有效地）完成的事情上。

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

于 2013-01-15T15:38:52.480 回答