algorithm - A *-图遍历启发式

我有一个代表城市的图表。我知道名胜古迹的位置(节点，这些节点具有重要性值)，我所住酒店的位置，节点之间的连接方式，节点之间的穿越时间以及经纬度。从时间到距离反之亦然没有问题。

目的是游览这座城市，以最大程度地提高每天的重要性，但将一天的旅行限制在10小时以内。在酒店开始和结束一天。我有一个工作正常的A *算法，该算法选择了最低值，但还没有启发式算法，我想目前它已成为BB。考虑到这一点:

因为我可以使用纬度/经度，所以我第一次尝试启发式搜索
只处理时间，是乌鸦飞翔的距离
在节点和酒店之间。这是可以接受的启发式方法吗？
它给了我尽可能短的距离和时间，所以不会
高估了。

现在，假设节点的重要性在1-4之间。为了考虑这一点，一个想法可能是g(邻居)= g(当前)+(edge_cost/重要度^ 2)。假设这是有效的(如果无效，为什么？):

但是现在启发式值将位于不同的单位中。一个简单的解决方案就是给酒店重要性= 1吗？如果值相同，是否仍然可以接受？编辑:由于规模的差异，我认为这最终将给我带来麻烦。

我仍然必须限制总时间。由于单位不同，每个节点是否应该跟踪花费的总时间以便与限制进行比较，并加上g()和h()值？

最后:

由于我必须在同一节点开始和结束，所以想到的是探索一个节点，是否应该找旅馆看看我是否还有时间探索邻居而不是回去。但是，如果我仍然有时间扩展到另一个节点，但是时间用完了，而且我无法从那里到达酒店，那么我假设我必须回溯到父节点。

我不禁看到与背包问题的相似之处。即使必须使用A *，我还能从中学到什么吗？

在这种情况下，我的试探法是否必须一致？如果是这样，为什么？

顺便说一句，这里的目的首先是寻路，然后是优化。

最佳答案

这实际上看起来像是旅行商问题(TSP)和背包问题(KP)的组合。在这方面，它是KP:背包容量为10(一天的可用总小时数)，位置是项目。项目值等于位置值。物品重量等于到达该地点所需的时间(加上该地点返回酒店的行程的一部分)。挑战来自于这样一个事实，即直到您解决了通过选定位置的最佳行程(进入TSP和寻路)之前，物品的重量都是未知的。

一种方法可能是主要使用寻路算法(例如A *，Bellman-Ford或Dijkstra的算法)来计算每个节点之间的距离矩阵。然后，在解决问题的TSP部分时，可以利用距离矩阵:遍历各个地点并以总时间作为权重。

下一步由您决定。如果您正在寻找一个近似的解决方案，那么TSP和KP都有许多启发式方法:请参见Christofides TSP Heuristic或Minimum TSP上的Maximum Knapsack和Compendium of NP Optimization problems条目。

另一方面，如果您寻求最佳解决方案，则可能不走运。我仍然建议您找到图论的副本。 Nicos Christofides的算法方法(ISBN-13:978-0121743505)。它为深度优先搜索中的早期回溯提供了启发式方法，从而加快了对几个NP-Complete问题的最佳解决方案的搜索。

关于algorithm - A *-图遍历启发式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29703936/