Алгоритм эластичной сети для решения задачи коммивояжёра (или TSP от англ. travelling salesman problem)
Задача коммивояжёра — классическая задача в области комбинаторной оптимизации, связанная с эффективными методами максимизации или минимизации функции многих независимых переменных. Учитывая расположение N городов, которые в простейшем случае лежат на плоскости, каков самый короткий закрытый тур, в котором каждый город можно посетить один раз?
- Метод грубой силы.
Полный перебор значений, который перебирает (n-1)! маршрутов для асимметричной и (n-1)!/2 маршрутов для симметричной задачи коммивояжёра. - Метод ветвления и границ с полным перебором.
- Метод динамического программирования.
Суть метода в том, что выбирается город, а затем для всех остальных городов в связке с ним строятся все возможные маршруты и выбирается самый короткий. Алгоритм рекурсивно применяется для всех оставшихся городов за вычетом выбранного на предыдущем этапе и так до тех пор, пока не выбранными остаются только два города. Для симметричной задачи часть маршрутов будет повторяться, а если результат сохранять отдельно, то его нужно рассчитать всего один раз. - Эвристики и другие возможные алгоритмы.
Изначальный путь выглядит как круг в центре масс всех городов, состоящий из большего количества точек, чем городов. Далее запускаются итерации до выполнения критерия остановки (геометрический параметр и максимальное количество итераций), где каждый шаг подстраивает сеть лучше к решению задачи. По выполнению критерия остановки получается тот путь, который изначально и было задачей найти.
Алгоритм построен на статье.
В ней можно увидеть более подробное математическое описание алгоритма и немного о метриках в использовании.