java - A* 算法的启发式

Question

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

我的问题是:

确定垃圾收集卡车在城市中完成的最佳路线，该城市在已知的 map 上移动以寻求最大化负载和最小化旅行时间。

我有 4 种类型的节点:通用节点、转储节点、垃圾节点和气体节点。

垃圾收集车可能没油了，有机会给车辆加满油。也可能有不止1个垃圾桶需要投递。

解决这个问题的最佳启发式是什么？

问候

Answer 1

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