使用 GoogleMap 的 TSP（旅行商问题）求解器
我们正在开发一个应用程序，我们将在其中在谷歌地图中显示一些可供出售的房屋。用户可以从地图上选择任何房屋，并可以找到他/她选择的所有房屋之间的最短路线。
谁能告诉我如何找到最短路线并在地图上显示出来？是否有任何基于 PHP 的 TSP 库可以帮助我们实现我们正在尝试的目标？
We are developing an application, in which we will show some available houses for sale in google map. User can select any houses from the map and can find the shortest driving route between all the houses he/she selected.
Can any one please tell me how we can find the shortest route and can show that on the map? Is there any PHP based TSP library, that can help us to achieve what we are trying?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
Google 搜索会显示许多结果。
http://scrivna.com/blog/travelling-salesman-problem/ - 强力 PHP 实现保证获得最佳答案。仅适用于有限数量的节点。
http://www.renownedmedia.com/blog/genic -algorithm-traveling-salesperson-php/ - 遗传算法 PHP 实现，将近似答案。适合大量节点。
您可以将两者结合起来，根据图表的大小选择运行哪一个。
正如 @Barbar 在评论中指出的那样，有一个 现有应用程序 可以完成您正在尝试的操作。有一篇博客文章解释了它是如何工作的。
A Google search shows many results.
http://scrivna.com/blog/travelling-salesman-problem/ - Brute force PHP implementation guaranteed to get the optimal answer. Only suitable for a limited number of nodes.
http://www.renownedmedia.com/blog/genetic-algorithm-traveling-salesperson-php/ - Genetic algorithm PHP implementation which will approximate the answer. Suitable for large numbers of nodes.
You could probably combine the two, choosing which to run based on the size of the graph.
As @Barbar points out in the comments, there is an existing app that does what you're attempting. There is a blog post explaining how it works.
它很旧，但可能对人们有用：
https://developers.google.com/maps/documentation/javascript/v2 /services#RoutesAndSteps
只需为每个房屋创建路径点，然后让谷歌为您进行数学计算...
Its old but it may be useful to people:
https://developers.google.com/maps/documentation/javascript/v2/services#RoutesAndSteps
just create waypoints for each house and let google do the math for you...
如果问题满足三角不等式，您可以尝试 Christofides 算法。
If the problem satisfy the triangle inequality you can try the Christofides algorithm.