我有一个无向图,其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”,一个节点标记为“结束”,还有大约十几个标记为“必须通过”。我需要找到通过的最短路径...
我有一个无向图,其中有大约 100 个节点和大约 200 条边。一个节点标记为“开始”,一个节点标记为“结束”,还有大约十几个标记为“必须通过”。
我需要找到该图中最短的路径,该路径始于“开始”,终于“结束”, 并经过所有“必须通过”节点(以任何顺序)。
( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt 是所讨论的图表 - 它代表了宾夕法尼亚州兰开斯特的一个玉米迷宫)
实际上,您发布的问题类似于旅行商问题,但我认为更接近于简单的寻路问题。您不需要访问每个节点,而只需在尽可能短的时间(距离)内访问一组特定的节点即可。
原因在于,与旅行商问题不同,玉米迷宫不允许您直接从地图上的任何一个点前往任何其他点,而无需经过其他节点才能到达那里。
我实际上建议考虑使用 A* 寻路技术。通过确定哪些节点可以直接访问哪些其他节点,以及从特定节点每次跳跃的“成本”是多少,可以设置该技术。在这种情况下,由于节点之间的距离相对较近,因此每次“跳跃”的成本似乎相等。A* 可以使用此信息来查找任意两点之间成本最低的路径。由于您需要从 A 点到达 B 点,并在其间访问大约 12 个节点,因此即使使用寻路的蛮力方法也不会有任何损失。
只是一种可供选择的方案。它确实看起来 非常 像旅行商问题,而且这些都是值得一读的好论文,但仔细看看,你会发现它只会让事情变得过于复杂。^_^ 这来自一位曾经处理过这类事情的视频游戏程序员的想法。