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

问题描述

我面临一个问题，我必须使用 A* 来搜索地图，而这张地图中有多个目标要达到.我的目标是扩展地图中的最少节点，关于如何设计此 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

推荐答案

假设多个目标"是指您想要达到任何一个，只需采用所有启发式中的最小值.假设您的启发式是一致，这是仍然是一致的启发式.

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-Complete.

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

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