在原点和目的地之间找到最短路径的问题(Netlogo)

问题描述 投票:0回答:1

我的研究是找到预定义的原点和目的地之间的最短路径。两者(原点和目的地)都是使用GIS扩展定位的,因为它们是通过形状文件获得的。我使用命令ask patches gis:intersecting shapefile创建了一个原籍人和目的地的学校。

我有10个起源,每个我有一个指定的目的地。我注意到当我使用Dijsktra的算法来找到最短路径时,对于某个原点,目的地不是相应的点而是最近的目的地。所以,我怀疑的是:Dijsktra是我问题的最佳算法还是我需要使用A *算法?

如果Dijkstra的算法是最好的,我如何在代码中通知对的起源和目的地?

如果A *算法是最好的,我如何在Netlogo 5.0版本中构建代码?

netlogo shortest-path
1个回答
0
投票

不确定netlogo,但由于你的问题没有在标签中引用它我会假设一个面向算法的答案是可以的。

Dijkstra和A *相似;两者都看起来并找到从一个点到另一个点的最短路径。当你有一个已知的预先目的地时,A *会更有效,因为它可以通过启发式最佳地寻找最短路径,而dijkstra通过搜索所有方向来扩展图形中的更多节点。

如果您发现Dijkstra返回的路径与您期望的目的地不同,则应考虑验证目的地检测:当您找到目的地时,应该结束dijkstra searcg,而不是任何目的地。

A *不会遭受如此多的相同,因为启发式会将它们指向正确的目的地,但在特殊情况下可以找到相同的问题(即,到正确目的地的最短路径通过不同的目的地)。

更确切地说,我需要一些代码 - 伪代码可以 - 你的结论,或图表上的细节。

© www.soinside.com 2019 - 2024. All rights reserved.