Мы разрабатываем приложение, в котором мы покажем некоторые доступные дома для продажи на карте Google. Пользователь может выбрать любые дома с карты и найти самый короткий маршрут движения между всеми домами, которые он выбрал.
Может ли кто-нибудь рассказать мне, как мы можем найти кратчайший маршрут и показать это на карте? Есть ли какая-либо PHP-библиотека TSP, которая может помочь нам достичь того, что мы пытаемся сделать?
Поиск в Google показывает много результатов.
http://scrivna.com/blog/travelling-salesman-problem/ – Вручную силу реализации PHP гарантированно получить оптимальный ответ. Подходит только для ограниченного числа узлов.
http://www.renownedmedia.com/blog/genetic-algorithm-traveling-salesperson-php/ – Генетический алгоритм PHP-реализации, который будет приближать ответ. Подходит для большого количества узлов.
Вероятно, вы могли бы объединить эти два, выбрав, которые запускать в зависимости от размера графика.
Как отмечает @Barbar в комментариях, существует существующее приложение, которое делает то, что вы пытаетесь. Существует сообщение в блоге, объясняющее, как это работает .
Его старый, но он может быть полезен людям: https://developers.google.com/maps/documentation/javascript/v2/services#RoutesAndSteps
просто создайте путевые точки для каждого дома и дайте Google сделать математику для вас …
Если проблема удовлетворяет неравенству треугольника, вы можете попробовать алгоритм Кристофидеса.