java - A* 算法的启发式

Question

我有一个问题要用 A* 解决，但我很难设计一个好的启发式方法。

我的问题是：

确定由垃圾收集车在已知地图上移动的城市中完成的最佳路线，以最大限度地增加负载并最大限度地减少旅行时间。

我有 4 种类型的节点：Geral Nodes、Dump Nodes、Garbage Nodes 和 Gas Nodes。

垃圾收集车可能会用完汽油，并有机会为车辆加油。也可能有超过 1 个垃圾箱需要运送。

解决此问题的最佳启发式方法是什么？

问候

Answer 1

一个好的首过搜索启发式方法是使用贪心算法。例如，在一般的路线规划算法（找到城市之间的最短路线）中，一个不错的启发式方法是使用贪婪算法，当乌鸦飞过时，你总是去离目的地最近的下一个城市；这是一种线性时间启发式算法，永远不会高估解决方案。在你的情况下，也许你可以使用一种贪心算法，垃圾车总是去下一个最近的垃圾节点，或者垃圾最多的垃圾节点；如果不知道您正在使用的四个节点的详细信息，我无法获得更具体的信息，但您明白了。任何不会高估解决方案的线性时间算法都可以，然后您可以在下一次通过时对其进行调整。（在大多数情况下，nlog(n) 启发式也是可以接受的；

Answer 2

A* 非常适合在 2 点之间找到最快/最短的路线。

但是，您的垃圾车问题可能是一个完全不同的问题：您需要通过订购一组点来找到最快/最短的路线。这基本上是旅行推销员问题（TSP）或车辆路线问题（VRP）的老大哥，两者都是NP-complete。

A* 无法处理 NP 完全问题，您需要元启发式等算法。寻找 TSP 和 VRP 问题的解决方案，例如 OptaPlanner（java，开源）中的 TSP 和 VRP 示例（如本视频所示）。