A*启发式：在多个点中经过一次的最短路径
我正在尝试为清晰地图的吃豆人游戏想出一个良好且快速的启发式方法。
我的启发式方法是尝试计算吃豆人到达地图上每个有食物的点所需的最小距离。 我当前的算法基本上是 Prim 的 MST，它使我的运行时间为 O(n logn)，但没有考虑吃豆人需要沿着边吃东西以及返回到前一个顶点的情况...
有什么吗更好的？
换句话说：不提笔连接几个点的最小成本是多少？
谢谢
I'm trying to come up with a good and fast heuristic for a clear-map pacman game.
My heuristic is trying to calculate the smallest distance possible that the pacman needs to travel to go to every points with food on the map. My current algorithm is basicly Prim's MST which gets me a O(n logn) running time, but doen't account for situations where the pacman needs to follow a edge to eat, and the return to the previous vertex...
Is there anything better?
Saying in another way: What is the minimum cost of connecting several dots without lifting my pen?
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
运行全对最短路径算法并识别带有食物的顶点后，这成为旅行推销员问题。 您无法有效地解决它，但您可以在多项式时间内构造任意好的近似解。 除非您可以预先计算所有内容，否则您可能需要使用近似值。 如果您可以预先计算事物（或者以其他方式保证您有足够的时间来找到精确的解决方案），那么一旦您获得了所有对最短路径，您就可以简单地找到所有可能的最小总步行长度您吃食物的顺序的排列。 通过注意两个食物块之间的最短路径何时穿过另一个食物块，这种蛮力方法可能会有所改进。
After running an all-pairs-shortest-path algorithm and identifying the vertices with food, this becomes the traveling salesman problem. You can't solve it efficiently, but you can construct arbitrarily good approximations to a solution in polynomial time. You'll probably want to use an approximation unless you can pre-compute everything. If you can pre-compute things (or otherwise guarantee that you have enough time to find an exact solution), then once you've got the all-pairs-shortest-paths, you can simply find the minimum total walk length over all possible permutations of the order in which you eat the food pieces. This brute-force method can probably be improved somewhat by watching out for when the shortest path between two food pieces crosses another food piece.