Предисловие

Бродил я по хабрахабру и наткнулся на статью Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе, и вспомнил как в студенческие годы писал прогу на С++ для этого алгоритма. Решил поделится одной интересной темой — решением задачи коммивояжера (TSP), алгоритмом муравьиной колонии (ACS) и реализацией этого алгоритма при помощи Google Maps.

Пол года назад у меня была задача написать сервис для поиска оптимального пути с использованием Google Maps Api и я использовал задачу коммивояжера с алгоритмом муравьиной колонии. Описание задачи коммивояжера найдёте можете найти в Википедии.
Приведу и опишу сам алгоритм и в конце ссылка где я выложил демо-версию реализации алгоритма.

Алгоритм

Общая задача коммивояжера (traveling salesmen problem, TSP состоит в следующем: используя заданную систему транспортных соединений (дорог и т.п.) между пунктами (городами, фирмами и т.п.) в конкретной зоне обслуживания, посетить все пункты в такой последовательности, чтобы пройденный путь был минимальным.