Решатель TSP (Задача коммивояжера) Использование GoogleMap

Question

Мы разрабатываем приложение, в котором мы покажем несколько доступных домов на продажу на карте Google.Пользователь может выбрать любой дом на карте и найти кратчайший маршрут движения между всеми выбранными им домами.

Может ли кто-нибудь сказать мне, как мы можем найти кратчайший маршрут и показать это на карте?Есть ли какая-нибудь библиотека TSP на основе PHP, которая может помочь нам достичь того, что мы пытаемся?

Answer 1

A Поиск Google показывает много результатов.

• http://scrivna.com/blog/travelling-salesman-problem/ - Реализация PHP методом грубой силы гарантированно получит оптимальный ответ.Подходит только для ограниченного числа узлов.

• http://www.renownedmedia.com/blog/genetic-algorithm-traveling-salesperson-php/ - Реализация PHP генетического алгоритма, которая приблизит ответ.Подходит для большого количества узлов.

Возможно, вы могли бы объединить два, выбирая, какой из них запускать, исходя из размера графика.

Как указывает @Barbar вкомментарии, существует существующее приложение , которое делает то, что вы пытаетесь.В блоге есть объяснение как это работает .

Answer 2

Это старое, но может быть полезно людям: https://developers.google.com/maps/documentation/javascript/v2/services#RoutesAndSteps

просто создайте путевые точки для каждого дома и позвольте Google сделать математику за вас ...

Answer 3

Если задача удовлетворяет неравенству треугольника, вы можете попробовать алгоритм Christofides.