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

Задача коммивояжера (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!).

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

Узнайте, как внутренний CTF помогает прокачивать навыки сотрудников и создавать культуру обучения на вебинаре 20 марта. Пройдёт онлайн с 12:00 до 13:00.

На вебинаре вы узнаете как соревнования Capture the flag помогают:
🔴Прокачать навыки специалистов
🔴Вовлечь сотрудников IT-направлений в сферу информационной безопасности
🔴Протестировать навыки сотрудников и их уровень компетенции
🔴Имитировать процессы кибер атак и понять, как вы с ними справляетесь

Приглашают HR-специалистов, DevRel-команды, руководителей и всех, заинтересованных в повышении компетенций сотрудников и росте бизнеса.

👉 Регистрируйтесь сейчас и получите доступ к уникальным материалам!

Хакатоны.рус продолжают серию вебинаров «IT-мероприятия как драйвер роста».