Какие существуют методы решения задачи коммивояжера?

Некоторые методы решения задачи коммивояжёра:

• Полный перебор (метод «грубой силы», англ. «Brute Force»). ratcatcher.ru galyautdinov.ru Заключается в последовательном рассмотрении всех возможных маршрутов и выборе из них оптимального. ratcatcher.ru galyautdinov.ru Метод самый простой и точный, но неэффективный, при большом количестве городов его применение становится затруднительным. ratcatcher.ru galyautdinov.ru
• Случайный перебор. ratcatcher.ru galyautdinov.ru Вычисляются не все возможные варианты маршрута, а лишь некоторые, выбранные в случайном порядке (например, с помощью генератора случайных чисел). ratcatcher.ru galyautdinov.ru Из рассмотренных вариантов затем выбирается наилучший. ratcatcher.ru galyautdinov.ru
• Динамическое программирование. ratcatcher.ru galyautdinov.ru Заключается в вычислении и запоминании пройденного пути от исходного города до всех остальных, последующем прибавлении к нему расстояний от текущих городов до оставшихся, и так далее. ratcatcher.ru galyautdinov.ru По сравнению с полным перебором этот метод позволяет существенно сократить объём вычислений. ratcatcher.ru galyautdinov.ru
• Жадные алгоритмы (англ. «Greedy»). galyautdinov.ru Основаны на нахождении локально оптимальных решений на каждом этапе вычислений и допущении, что найденное таким образом итоговое решение будет глобально оптимальным. galyautdinov.ru Т. е. на каждой итерации выбирается лучший участок пути, который включается в итоговый маршрут. galyautdinov.ru
• Метод минимального остовного дерева. ratcatcher.ru galyautdinov.ru Поиск маршрута ведётся на графе. ratcatcher.ru galyautdinov.ru Для нахождения оптимального пути применяются различные инструменты: алгоритм Прима, алгоритм Краскала, алгоритм Борувки. ratcatcher.ru galyautdinov.ru
• Метод имитации отжига — один из численных методов Монте-Карло. ratcatcher.ru galyautdinov.ru
• Метод эластичной сети — каждый из возможных маршрутов рассматривается как отображение окружности на плоскость. ratcatcher.ru spravochnick.ru
• Муравьиный алгоритм — эвристический метод, основанный на моделировании поведения муравьёв, ищущих пути от своей колонии к источникам пищи. ratcatcher.ru galyautdinov.ru Этот метод позволяет относительно быстро найти хорошее, но не обязательно оптимальное решение. ratcatcher.ru galyautdinov.ru
• Генетический алгоритм — ещё один эвристический метод, заключающийся в случайном подборе и комбинировании исходных параметров с использованием механизмов, имитирующих естественный отбор в процессе эволюции (наследование, мутации, кроссинговер). ratcatcher.ru galyautdinov.ru