我在编写一个类似《精英》的简单游戏时，遇到了编写AI路径查找程序的问题。

游戏中的世界由几个通过“虫洞”连接的“系统”组成，飞船每回合可以从当前所在的系统跳跃到任何与之相连的系统。AI只能知道它应该知道的事情；它不知道未去过的系统有哪些连接（尽管它可以通过已经访问过的系统推断出来，因为连接是双向的）。AI的其他部分根据飞船库存中的货物以及它记得在经过的系统中货物的价值，来决定飞船需要到达哪个系统。

问题是，我不知道如何解决寻找目标系统路径的问题。我不能使用A*算法；在没有路径的情况下无法确定到另一个系统的‘距离’。此外，我需要这个算法高效，因为每次玩家行动时，它需要运行大约100次。

有谁知道合适的算法吗？

回答：

我最终实现了一个双向、贪婪版本的广度优先搜索，这足以满足需求。简单来说，我只是让程序查看起始节点连接的每个节点，然后是这些节点连接的节点，再然后是这些节点连接的节点……直到找到目标节点。

通常，人们会构建一个合适路径的列表并选择最短的路径，但我尝试了一种不同的方法；我让程序并行运行两个搜索，一个从起点开始，另一个从终点开始。当‘从’搜索找到‘到’搜索的最后一个节点时，就认为路径找到了。

然后它通过检查路径上的每个节点是否连接到路径上更靠前的节点，并删除它们之间的每个节点来优化路径。

这种古怪的算法是否真的比直接的广度优先搜索更好，还有待观察。