Я бы сделал это примерно так: начальный город выбирается произвольно, после чего каждый раз, когда коммивояжер выбирает следующий город, он перемещается в ближайший город из тех, что он еще не посещал. Допустим, он начинает в Марине.
Суммарное расстояние — 71 миля. Может, это не самый короткий путь, но он достаточно близок к нему.
Короткое объяснение NP-полноты: некоторые задачи прославились сложностью своего решения. Задача о коммивояжере и задача о покрытии множества — два классических примера. Многие эксперты считают, что написать быстрый алгоритм для решения таких задач невозможно.
Как определить, что задача является NP-полной?
Джон подбирает игроков для своей команды по американскому футболу. У него есть список нужных качеств: хорошо играет в нападении, хорошо играет в защите, хорошо играет под дождем, хорошо играет под давлением и т.д. Также имеется список игроков, в котором каждый игрок обладает определенными качествами.
Джон хочет подобрать команду, которая обладает полным набором качеств, но размер команды ограничен. «Минутку, — осознает Джон, — но ведь это задача покрытия множества!»
Для создания команды Джон может воспользоваться тем же приближенным алгоритмом:
1. Найти игрока с большинством качеств, которые еще не были реализованы.
2. Повторять до тех пор, пока не будут реализованы все качества (или пока не кончатся свободные места в команде).
NP-полные задачи встречаются очень часто. И было бы полезно, если бы вы могли понять, что решаемая задача является NP-полной. В этот момент можно прекратить поиски идеального решения и перейти к решению с применением приближенного алгоритма. Но определить, является ли ваша задача NP-полной, непросто. Обычно различия между легко решаемыми и NP-полными задачами весьма незначительны. Например, в предыдущих главах я много говорил о кратчайших путях. Вы знаете, как вычислить кратчайший путь из точки A в точку B.
Но если вы хотите найти кратчайший путь, соединяющий несколько точек, то это уже задача о коммивояжере, которая является NP-полной. Короче говоря, не существует простого способа определить, является ли задача, с которой вы работаете, NP-полной. Несколько характерных признаков:
• ваш алгоритм быстро работает при малом количестве элементов, но сильно замедляется при увеличении их числа;
• формулировка «все комбинации X» часто указывает на NP-полноту задачи;
• вам приходится вычислять все возможные варианты X, потому что задачу невозможно разбить на меньшие подзадачи? Такая задача может оказаться NP-полной;
• если в задаче встречается некоторая последовательность (например, последовательность городов, как в задаче о коммивояжере) и задача не имеет простого решения, она может оказаться NP-полной;
• если в задаче встречается некоторое множество (например, множество радиостанций) и задача не имеет простого решения, она может оказаться NP-полной;
• можно ли переформулировать задачу в условиях задачи покрытия множества или задачи о коммивояжере? В таком случае ваша задача определенно является NP-полной.
Упражнения
8.6 Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?
8.7 Имеется задача поиска максимальной клики в множестве людей (кликой называется множество людей, каждый из которых знаком со всеми остальными). Является ли эта задача NP-полной?
8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?
Шпаргалка
• Жадные алгоритмы стремятся к локальной оптимизации в расчете на то, что в итоге будет достигнут глобальный оптимум.
• У NP-полных задач не существует известных быстрых решений.
• Если у вас имеется NP-полная задача, лучше всего воспользоваться приближенным алгоритмом.
• Жадные алгоритмы легко реализуются и быстро выполняются, поэтому из них получаются хорошие приближенные алгоритмы.
9. Динамическое программирование
В этой главе