Составьте маршрут автомобильного путешествия по 61 городу, и у вас будет больше возможных вариантов для расчета, чем существует атомов во Вселенной. Звучит удручающе, не так ли? Вам наверняка кажется, что из, по сути ограниченного количества отрезков, невозможно создать бесконечное количество комбинаций? Но нет!
Этот экспоненциальный рост лежит в основе задачи коммивояжера и прекрасно иллюстрирует, почему найти кратчайший маршрут туда и обратно настолько сложно.
Задача коммивояжера - это классическая проблема оптимизации. Она проявляется, когда нужно найти кратчайший путь, посещая каждый из n городов ровно один раз и возвращаясь в исходный пункт.
Сложность заключается в математическом понятии, называемом комбинаторным взрывом. По мере добавления каждого нового пункта назначения в список количество возможных маршрутов не просто увеличивается, а умножается в факториал. Если путешественник посещает пять городов, то существует всего 12 уникальных маршрутов туда и обратно, которые нужно проверить.
Теперь увеличьте это число до 10 городов, и оно подскочит до 181 440. Попытка решить проблему методом «грубой силы» то есть когда компьютер проверяет каждый возможный маршрут, чтобы найти кратчайший быстро становится физически невозможной, даже для самых мощных суперкомпьютеров в мире.
Поскольку метод перебора неэффективен, специалисты по информатике и математики десятилетиями искали хитрый способ решения такой задачи. Нужен был алгоритм, который мог бы вычислить оптимальный маршрут, не рассматривая каждый неподходящий маршрут.
Однако задача коммивояжера относится к классу математических задач, известных как NP-трудные. Это означает, что, хотя вычислить общую протяженность одного конкретного маршрута очень легко, в настоящее время не существует известной формулы для эффективного нахождения абсолютно кратчайшего маршрута среди всех возможных.
Фактически, доказательство существования быстрого и абсолютно точного способа решения задачи коммивояжера связано с проблемой «P против NP», одной из величайших неразгаданных загадок математики.
Достоверное доказательство буквально изменило бы мир, мгновенно произведя революцию в таких областях, как криптография, логистика и искусственный интеллект, и принесло бы решателю премию тысячелетия от Института математики Клэя в размере 1 миллиона долларов.
Поскольку найти математически идеальный маршрут для больших наборов данных зачастую невозможно, логистические компании, занимающиеся доставкой посылок, а также инженеры, разрабатывающие микроскопические схемы на компьютерных чипах, полагаются на алгоритмы аппроксимации.
Эти практические решения используют умные эвристики для поиска маршрута, который является чрезвычайно эффективным с отклонением всего не более 1% или 2% от оптимального пути.
Они не могут математически доказать, что это абсолютно кратчайший маршрут, но для реальных задач он достаточно близок к оптимальному, чтобы обеспечить бесперебойную работу глобальной логистики.
П.с.: Кстати, предвкушаю вопросы в стиле - а почему 61, почему не 28 или не 79? Так вот, число может быть любым. Просто с увеличением количества городов сложность увеличивается. То есть «порог решения» - не конкретное число, а момент, когда время перебора превышает любые разумные ресурсы.
Не забывайте ставить лайки статье и подписываться! Это очень важно для развития проекта, а вы будете видеть ещё больше интересных статей в ленте! На канале есть премиум, где много интересного.