Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 23)
Сколько возможных маршрутов существует для шести городов? 720, говорите? Да, вы правы. 5040 для 7 городов, 40 320 для 8 городов.
Такая зависимость называется
У задачи о коммивояжере и задаче покрытия множества есть кое-что общее: вы вычисляете каждое возможное решение и выбираете кратчайшее/минимальное. Обе эти задачи являются
Приближенное решение
Как выглядит хороший приближенный алгоритм для задачи о коммивояжере? Это должен быть простой алгоритм, находящий короткий путь. Попробуйте самостоятельно найти ответ, прежде чем продолжить чтение.
Я бы сделал это примерно так: начальный город выбирается произвольно, после чего каждый раз, когда коммивояжер выбирает следующий город, он перемещается в ближайший город из тех, что он еще не посещал. Допустим, он начинает в Марине.
Суммарное расстояние — 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 Имеется задача поиска максимальной
8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?
Шпаргалка
• Жадные алгоритмы стремятся к локальной оптимизации в расчете на то, что в итоге будет достигнут глобальный оптимум.
• У NP-полных задач не существует известных быстрых решений.
• Если у вас имеется NP-полная задача, лучше всего воспользоваться приближенным алгоритмом.
• Жадные алгоритмы легко реализуются и быстро выполняются, поэтому из них получаются хорошие приближенные алгоритмы.
9. Динамическое программирование
В этой главе
• Вы освоите динамическое программирование — метод решения сложных задач, разбиваемых на подзадачи, которые решаются в первую очередь.
• Рассматриваются примеры, которые научат вас искать решения новых задач, основанные на методе динамического программирования.
Задача о рюкзаке
Вернемся к задаче о рюкзаке из главы 8. У вас есть рюкзак, в котором можно унести товары общим весом до 4 фунтов.
Есть три предмета, которые можно уложить в рюкзак.
Какие предметы следует положить в рюкзак, чтобы стоимость добычи была максимальной?
Простое решение
Простой алгоритм выглядит так: вы перебираете все возможные множества товаров и находите множество с максимальной стоимостью.
Такое решение работает, но очень медленно. Для 3 предметов приходится обработать 8 возможных множеств, для 4 — 16 и т.д. С каждым добавляемым предметом количество множеств удваивается! Этот алгоритм выполняется за время
Для любого сколько-нибудь значительного количества предметов это неприемлемо. В главе 8 вы видели, как вычисляются
Как же вычислить оптимальное решение?
Динамическое программирование
В задаче о рюкзаке начать следует с решения задачи для меньшего рюкзака (или «подрюкзака»), а потом на этой основе попытаться решить исходную задачу.
Для начала я покажу вам алгоритм в действии. После этого у вас наверняка появится много вопросов! Я постараюсь ответить на них.
Каждый алгоритм динамического программирования начинается с таблицы. Вот как выглядит таблица для задачи о рюкзаке.
Строки таблицы представляют предметы, а столбцы — емкость рюкзака от 1 до 4 фунтов. Все эти столбцы нужны, потому что они упрощают вычисление стоимостей «подрюкзаков».
В исходном состоянии таблица пуста. Нам предстоит заполнить каждую ячейку таблицы. После того как таблица будет заполнена, вы получите ответ на свою задачу. Пожалуйста, внимательно разберитесь в происходящем. Нарисуйте собственную таблицу, а мы вместе ее заполним.
Строка Гитара
Точная формула для вычисления значений в таблице будет приведена позднее, а пока ограничимся общим описанием. Начнем с первой строки.
Строка снабжена пометкой «гитара»; это означает, что вы пытаетесь уложить гитару в рюкзак. В каждой ячейке принимается простое решение: класть гитару в рюкзак или нет? Помните: мы пытаемся найти множество элементов с максимальной стоимостью.
В первой ячейке емкость рюкзака равна 1 фунту. Гитара также весит 1 фунт — значит, она поместится в рюкзак! Итак, стоимость этой ячейки составляет $1500, а в рюкзаке лежит гитара.
Начнем заполнять ячейку.
По тому же принципу каждая ячейка в таблице содержит список всех элементов, которые помещаются в рюкзаке на данный момент.
Посмотрим на следующую ячейку. На этот раз емкость рюкзака составляет 2 фунта. Понятно, что гитара здесь поместится!
Процедура повторяется для остальных ячеек строки. Вспомните, что текущей является первая строка, поэтому выбирать приходится
Возможно, к этому моменту вы слегка сбиты с толку. Почему все это делается для рюкзаков с емкостью 1, 2 и т.д., если в задаче речь идет о рюкзаке с емкостью 4 фунта? Помните, что я говорил ранее? Метод динамического программирования начинает с малых задач, а затем переходит к большой задаче. Вы решаете подзадачи, которые помогут в решении большой задачи. Читайте дальше, и ситуация постепенно прояснится.
После того как первая строка будет заполнена, таблица будет выглядеть так:
Помните, что мы стремимся обеспечить максимальную стоимость предметов в рюкзаке.