Computer Science на языке Java 2022 Дэвид Копец Классические задачи Computer Science на языке Java 2022 ббк

250
Глава 9.
Другие задачи
Несмотря.на.то.что.поставленная.задача.кажется.довольно.простой,.не.существует.
алгоритма,.который.мог.бы.быстро.решить.ее.для.произвольного.числа.городов..Что.
я.подразумеваю,.говоря.«быстро»?.Я.имею.в.виду,.что.есть.проблема:.перед.нами.
НП-трудная задача
..НП-трудная.(недетерминированная.полиномиальная.трудная).
задача.—.это.задача,.для.которой.не.существует.алгоритма.полиномиального.времени..
(Требуемое.время.—.это.полиномиальная.функция.от.размера.входных.данных.).По.
мере.увеличения.числа.городов,.которые.должен.посетить.коммивояжер,.сложность.
задачи.растет.исключительно.быстро..Решить.задачу.для.двадцати.городов.намного.
труднее,.чем.для.десяти..Решить.задачу.идеально.(оптимально).для.нескольких.
миллионов.городов.за.разумное.время.невозможно.(насколько.нам.известно).
ПРИМЕЧАНИЕ
Наивный.подход.к.решению.задачи.коммивояжера.имеет.сложность.O(n!)..Почему.
это.так,.говорится.в.подразделе.9.2.2..Перед.тем.как.читать.его,.рекомендую.прочесть.
подраздел.9.2.1,.потому.что.после.попытки.реализации.наивного.решения.задачи.ее.
сложность.станет.очевидной.
9.2.1. Наивный подход
Наивный.подход.к.решению.задачи.—.просто.перепробовать.все.возможные.
перестановки.городов..Попробуем.использовать.наивный.подход,.чтобы.проил-
люстрировать.сложность.задачи.и.непригодность.такого.решения.для.применения.
в.более.крупных.масштабах.
Тестовые данные
В.нашей.версии.задачи.коммивояжер.заинтересован.в.посещении.пяти.крупных.
городов.штата.Вермонт..Мы.не.будем.указывать.начальный.(следовательно,.
конечный).город..На.рис..9.2.показаны.пять.городов.и.расстояния.между.ними..
Обратите.внимание.на.то,.что.для.построения.маршрута.указано.расстояние.
между.каждой.парой.городов.
Возможно,.вам.уже.встречались.таблицы.расстояний..В.них.легко.найти.рассто-
яние.между.любыми.двумя.городами..В.табл..9.2.перечислены.расстояния.для.
пяти.городов,.используемых.в.задаче.