我们正在开发一个应用程序，其中我们将在谷歌地图中显示一些可供出售的房屋。用户可以从地图中选择任何房屋，并可以找到他/她选择的所有房屋之间的最短行车路线。
谁能告诉我我们如何找到最短的路线并在地图上显示？是否有任何基于 PHP 的 TSP 库可以帮助我们实现我们正在尝试的目标？
问问题
10451 次
3 回答
12
谷歌搜索显示许多结果。
http://scrivna.com/blog/travelling-salesman-problem/ - 蛮力 PHP 实现保证获得最佳答案。仅适用于有限数量的节点。
http://www.renownedmedia.com/blog/genetic-algorithm-traveling-salesperson-php/ - 将近似答案的遗传算法 PHP 实现。适用于大量节点。
您可以将两者结合起来，根据图表的大小选择运行哪个。
正如@Barbar 在评论中指出的那样，有一个现有的应用程序可以执行您正在尝试的操作。有一篇博客文章解释了它是如何工作的。
于 2010-12-24T13:35:27.003 回答
2
它很旧，但可能对人们有用： https ://developers.google.com/maps/documentation/javascript/v2/services#RoutesAndSteps
只需为每个房子创建航点，让谷歌为你做数学......
于 2012-06-02T04:57:29.443 回答
0
如果问题满足三角不等式，您可以尝试 Christofides 算法。
于 2011-03-12T07:14:32.373 回答