8.3 Быстрая сортировка.
8.4 Поиск в ширину.
8.5 Алгоритм Дейкстры.
NP-полные задачи
Для решения задачи о покрытии множества необходимо вычислить каждое возможное подмножество.
Вероятно, вы вспомнили задачу о коммивояжере из главы 1. В этой задаче коммивояжер должен был посетить пять разных городов.
Коммивояжер пытается найти кратчайший путь, который включит все пять городов. Чтобы найти кратчайший путь, сначала необходимо вычислить все возможные пути.
Сколько маршрутов необходимо вычислить для пяти городов?
Задача о коммивояжере — шаг за шагом
Начнем с малого. Допустим, городов всего два. Выбирать приходится всего из двух маршрутов.
Логично спросить: в задаче о коммивояжере существует ли конкретный город, с которого нужно начинать? Допустим, коммивояжер живет в Сан-Франциско и должен посетить еще четыре города. Сан-Франциско должен быть первым городом в маршруте.
Однако в каких-то ситуациях начальный город не задан. Допустим, вы работаете в курьерской службе FedEx и должны доставить пакет в пределах города. Пакет перевозится из Чикаго в один из 50 филиалов FedEx. Затем пакет будет перегружен в машину, которая разъезжает по разным местам и доставляет пакеты. В какой филиал отгрузить пакет? На этот раз начальная точка неизвестна, и в задаче о коммивояжере вам придется вычислить как оптимальный путь, так и начальную точку.
Время выполнения обеих версий одинаково. Однако отсутствие определенного начального города упрощает пример, поэтому я выберу эту версию.
Два города = два возможных маршрута.
Сколько маршрутов?
На первый взгляд может показаться, что это один маршрут. Разве расстояние СФ>Марин не совпадает с расстоянием Марин>СФ? Не всегда. В некоторых городах (в том числе и в Сан-Франциско) много улиц с односторонним движением, и тогда вам не удается вернуться по тому пути, по которому вы приехали. Иногда приходится проехать лишнюю пару миль, чтобы найти выезд на шоссе. Так что эти два маршрута не всегда совпадают.
Три города
Теперь добавим к двум городам еще один. Сколько возможных маршрутов существует в этой конфигурации?
Если начать в Беркли, вы можете посетить два города.
Всего шесть возможных маршрутов: по два для каждого города, с которого вы можете начать.
Итак, три города = шесть возможных маршрутов.
Четыре города
Добавим еще один город — Фремонт. Теперь допустим, что вы начали с Фремонта.
Мы знаем, что во Фремонте начинаются шесть возможных маршрутов. Ого! Да они очень похожи на шесть маршрутов, которые вы вычислили ранее, когда городов было всего три! Только теперь во всех маршрутах появился дополнительный город, Фремонт! Начинает проявляться закономерность. Предположим, из четырех городов выбирается начальный город Фремонт. Остается еще три города. И вы знаете, что для перемещения между тремя городами есть шесть разных маршрутов. Итак, если начать с Фремонта, существуют шесть возможных маршрутов. Также возможно начать с одного из других городов.
Четыре возможных начальных города, шесть возможных маршрутов для каждого начального города = 4 × 6 = 24 возможных маршрута.
Замечаете закономерность? Каждый раз, когда вы добавляете новый город, увеличивается количество вычисляемых маршрутов.
Сколько возможных маршрутов существует для шести городов? 720, говорите? Да, вы правы. 5040 для 7 городов, 40 320 для 8 городов.
Такая зависимость называется факториальной (помните, что об этом говорилось в главе 3?) Итак, 5! = 120. Допустим, есть 10 городов. Сколько существует возможных маршрутов? 10! = 3 628 800. Уже для 10 городов приходится вычислять более 3 миллионов возможных маршрутов. Как видите, количество возможных маршрутов стремительно растет! Вот почему невозможно вычислить «правильное» решение задачи о коммивояжере при очень большом количестве городов.
У задачи о коммивояжере и задаче покрытия множества есть кое-что общее: вы вычисляете каждое возможное решение и выбираете кратчайшее/минимальное. Обе эти задачи являются NP-полными.
Приближенное решение
Как выглядит хороший приближенный алгоритм для задачи о коммивояжере? Это должен быть простой алгоритм, находящий короткий путь. Попробуйте самостоятельно найти ответ, прежде чем продолжить чтение.