NEW BOT Телеграм, страница

Forwarded from Код и кофе | Анастасия Егорова

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

Задача коммивояжера (TSP, от английского Traveling Salesman Problem) — это классическая задача оптимизации в теории графов и комбинаторной оптимизации. Она заключается в том, чтобы найти кратчайший маршрут, который проходит через заданный набор городов и возвращается в исходный город, при этом каждый город должен быть посещён ровно один раз 🛍

Формулировка задачи:

• Дано: множество городов и расстояния между ними.

• Найти: кратчайший путь, который начинается и заканчивается в одном городе и проходит через все остальные города ровно один раз🏠

Пример:
Предположим, у нас есть 4 города A, B, C и D с расстояниями между ними. Задача состоит в том, чтобы определить самый короткий маршрут, например, A → B → C → D → A.

Давайте определим, какую сложность может иметь решение этой задачи, если решать ее методом перебора.

Допустим, у нас есть 4 города. Получается, коммивояжер может выбрать один из 6 вариантов дороги:
A → B → C → D → A
A → D → C → B → A

A → B → D → C → A
A → C → D → B → A

A → D → B → C → A
A → C → B → D → A

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

🔽

Как видите, первая и последняя точка никогда не меняется — это всегда A. Середина маршрута — различные перестановки вершин B, C и D.

Первая вершина всегда фиксирована и не участвует в перестановках, поэтому общее количество маршрутов для вершин равно (n — 1)! 😳

Если из каждой симметричной пары брать только один маршрут, то маршрутов станет вполовину меньше — (n — 1)!/2

В обоих случаях в нотации О-большое алгоритмическая сложность при решении задачи коммивояжера методом перебора оценивается как O(n!).

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

Please open Telegram to view this post

VIEW IN TELEGRAM

85 viewsМаша Даровская, 12:55