0

我正在尝试编写（或扩展现有的）图搜索算法，考虑到无法保证节点将被连接，该算法将让我找到最接近目标节点的路径。

为了提供一个实际的应用，假设我需要从安大略省的布兰普顿到安大略省的汉密尔顿。我知道在我的起点我可能的选择是本地交通、GO 巴士或步行。我知道步行是到达目的地最不受欢迎的方式，所以我先看看 GO 巴士。我知道我可以将 GO 带到靠近汉密尔顿的一个点，但是在那一点上，GO 巴士转向另一个方向，在最近的点是我别无选择的地方（除了步行，但算法只会考虑步行对于短距离，否则它将认为该路线不可行）

使用同样的例子，如果算法发现我可以到达那里的方式更长但让我更接近目标节点（或可能在目标节点），这将是一个更高的加权路径（权重不在它的搜索过程中非常重要，只有当结果交付时，它才会按升序列出离目的地最近的路径）。例如，一辆 GO Bus 可以让我距离目的地节点 3 公里，而 3 辆公共交通巴士可以让我距离目标节点 500m

所以我的问题有两个方面：1）我应该从什么算法开始做类似的事情 2）我如何以编程方式解释如果节点不连接也没关系，这样它就不会只是从节点 A 跳转到节点 R。会从头开始并向后工作来完成这个

编辑：我忘了问如何瞄准最佳近似解决方案，因为特别是对于一个大图，这个问题可能会有数百万个解决方案。

谢谢，迈克尔

4

3 回答 3

4

阅读A* 算法。它是 Dijkstra 最短路径算法的推广，允许您指定启发式算法，它为两个顶点之间的距离提供下限。在您的情况下，启发式函数将简单地返回欧几里得距离。

运行算法并跟踪具有最佳特征值的顶点，您可以通过从源的图形距离和到目标的欧几里德距离以某种方式计算该顶点。唯一棘手的部分是确定何时终止（除非您想遍历整个图）。

于 2009-04-12T17:00:49.100 回答
2

为什么不能假设所有节点都已连接？在现实世界中，它们通常是，即你总是可以走路或叫出租车等？

在这种情况下，您可以通过以下方式简单地更改模型：每种运输方式都有一个图表。位于同一位置的节点与权重为 0 的边相连（即，如果您在机场或火车站乘汽车下车）。

然后，用运输类型标记每个顶点和边，您可以简单地使用现有的路由算法。哦，顺便说一句：A* 不能很好地扩展到真正的大型网络。要获得 Yahoo/Google/Microsoft Maps 等软件实际会使用的东西，请查看此处。该研究小组的工作包括DIMACS 最短路径挑战赛的获胜者。

于 2009-04-12T17:49:15.740 回答
-1

听起来很像带有额外节点特征的旅行推销员问题。请注意这种类型的问题是NP Complete并且您最好的选择是使用某种近似算法。

于 2009-04-12T17:01:58.443 回答