如何设计启发式的A *时，有在网格地图多重目标？ [英] How to design the heuristic for A* when there are multiple goals in the grid map?

问题描述

我现在面临一个问题，我必须使用*通过地图搜索，并且有在此映射多重目标达成。我的目标是扩大至少节点地图，如何设计启发式这个A *算法什么想法？谢谢

I am facing a problem that I have to use A* to search through the map, and there are multiple goals in this map to reach. My aim is to expand the least nodes in the map, any idea on how to design the heuristic for this A* algorithm? thanks

推荐答案

假设由多目标你的意思是你想达到的任何一个，只取最小的所有启发式的。假设你的试探一致，这是<一个href="http://gamedev.stackexchange.com/questions/56730/is-the-manhattan-distance-monotonic-when-used-as-heuristic-function/56755#comment98932_56755">still一致的启发式。

Assuming by "multiple goals" you mean you want to reach any one, just take the minimum of all the heuristics. Assuming your heuristic is consistent, this is still a consistent heuristic.

如果不是你想的是所有，这本质上是旅行商问题< /一>，这是NP完全问题。

If instead you're trying to reach all of them, this is essentially the traveling salesman problem, which is NP-Complete.

这篇关于如何设计启发式的A *时，有在网格地图多重目标？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！