A* - 图遍历启发式算法

Question

我有一个表示城市的图。我知道感兴趣的地方（节点，具有重要性值）的位置，我住的酒店的位置，节点之间的连接方式，它们之间的遍历时间以及纬度和经度。在时间和距离之间转换没有问题。

目标是游览城市，最大限度地提高每天的重要性，但将一天的旅行限制为10小时。一天从酒店开始，结束。我有一个工作的A*算法，选择最低价值，但还没有启发式，我想这使它成为BB。考虑到这一点：

- 由于我可以访问Lat/Long，我的第一次尝试启发式，只涉及时间，将是节点与酒店之间直线距离。这是一种可接受的启发式吗？它给我最短的距离和时间，所以它不会高估。

现在假设节点的重要性在1-4之间。为了将其纳入考虑范围，一个想法可能是g(neighbor) = g(current) + (edge_cost / Importance^2)。假设这是有效的（如果不是，为什么？）：

- 现在启发式值将以不同的单位出现。解决这个问题的方法是简单地给酒店赋予重要性=1吗？如果值相同，它是否仍然是可接受的？编辑：我认为这最终会给我带来问题，因为比例的差异。 - 我仍然必须限制总时间。每个节点应该跟踪花费的总时间，以便与限制进行比较，再加上g()和h()值，因为单位不同吗？

最后：

- 由于我必须在同一个节点开始和结束，所以我想到的是探索一个节点，如果我找到酒店并且还有时间去探索邻居而不是返回，但是如果我还有时间扩展到另一个节点，但时间用完了并且我不能从那里到达酒店，我假设我必须回溯到父节点。 - 我忍不住看到与背包问题的相似之处。即使我必须使用A*，我能从中得到什么教训吗？ - 在这种情况下，我的启发式必须一致吗？如果是，为什么？

顺便说一下，这里的目的是首先进行路径规划，其次是优化。

- Crowley

---

这实际上是旅行商问题的概括 - 它是NP-完全问题。 A*算法的问题在于它不支持对路线本身的限制，它只设计用于从源到一组目标中找到最短路径，而这并不是您的情况（无论如何都需要修改）。 - amit

我负责这些修改。对于这个问题，我基本上只能使用A*算法，因此有这么多问题。 - Crowley

对我来说，使用A*算法完成这个任务有些奇怪，它似乎更像是一个优化问题而不是最短路径问题——因此，例如遗传算法或爬山算法在这里似乎更加合适。 - amit

我的感觉是这个问题有太多的子问题，不太适合广泛使用。我的建议是尝试将其分解。 - Richard

我不清楚如何识别正确的解决方案，所以我有以下问题： 一个正确的解决方案是几天的整体最优解，还是只有一天？...什么是最优解？将最重要的点压缩在10小时内的解决方案吗？...我们可以将景点之间的距离视为时间吗？如果不能，我们该如何转换？此外，我们是否假设在景点停留0时间；如果不是，需要多少时间？ - Topological Sort

Answer 1

这实际上看起来像是旅行商问题（TSP）和背包问题（KP）的结合。在这方面它类似于KP：背包容量为10（一天中可用的总时间），位置就是物品。物品价值等于位置价值。物品重量等于到达该位置所需的时间（加上返回酒店的路程所需的时间）。挑战在于，直到解决了通过选择的位置的最佳路径后，才能确定一个物品的重量——这时就需要TSP和路径规划了。

一种方法是使用路径规划算法（例如A*、Bellman-Ford或Dijkstra算法）主要计算每个节点之间的距离矩阵。然后可以利用距离矩阵来解决问题的TSP部分：找到通过位置的巡回路线，并将总时间作为重量。

下一步就看你了。如果你正在寻找近似解，TSP和KP都有许多启发式算法可供选择：请参见Christofides TSP Heuristic，或者在Compendium of NP Optimization problems中查看Minimum TSP和Maximum Knapsack条目。

另一方面，如果您正在寻找最优解，则可能运气不佳。但我仍建议您找到Nicos Christofides的《图论。算法方法》（ISBN-13：978-0121743505）的副本。它提供了用于早期回溯的启发式方法，在深度优先搜索中加快了对几个NP完全问题的最优解的搜索。

- Austin