Читаем Грокаем алгоритмы полностью

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. Динамическое программирование

В этой главе

• Вы освоите динамическое программирование — метод решения сложных задач, разбиваемых на подзадачи, которые решаются в первую очередь.

• Рассматриваются примеры, которые научат вас искать решения новых задач, основанные на методе динамического программирования.

Задача о рюкзаке

Вернемся к задаче о рюкзаке из главы 8. У вас есть рюкзак, в котором можно унести товары общим весом до 4 фунтов.

Есть три предмета, которые можно уложить в рюкзак.

Какие предметы следует положить в рюкзак, чтобы стоимость добычи была максимальной?


Простое решение

Простой алгоритм выглядит так: вы перебираете все возможные множества товаров и находите множество с максимальной стоимостью.

Такое решение работает, но очень медленно. Для 3 предметов приходится обработать 8 возможных множеств, для 4 — 16 и т.д. С каждым добавляемым предметом количество множеств удваивается! Этот алгоритм выполняется за время O(2^n

), что очень, очень медленно.

Для любого сколько-нибудь значительного количества предметов это неприемлемо. В главе 8 вы видели, как вычисляются приближенные решения. Такие решения близки к оптимальным, но могут не совпадать с ними.

Как же вычислить оптимальное решение?


Динамическое программирование

Ответ: с помощью динамического программирования! Давайте посмотрим, как работает этот метод. Процедура начинается с решения подзадач с постепенным переходом к решению полной задачи.

В задаче о рюкзаке начать следует с решения задачи для меньшего рюкзака (или «подрюкзака»), а потом на этой основе попытаться решить исходную задачу.


Динамическое программирование — достаточно сложная концепция; не огорчайтесь, если после первого прочтения что-то останется непонятным. Примеры помогут вам разобраться в теме.

Для начала я покажу вам алгоритм в действии. После этого у вас наверняка появится много вопросов! Я постараюсь ответить на них.

Перейти на страницу:

Все книги серии Библиотека программиста

Программист-фанатик
Программист-фанатик

В этой книге вы не найдете описания конкретных технологий, алгоритмов и языков программирования — ценность ее не в этом. Она представляет собой сборник практических советов и рекомендаций, касающихся ситуаций, с которыми порой сталкивается любой разработчик: отсутствие мотивации, выбор приоритетов, психология программирования, отношения с руководством и коллегами и многие другие. Подобные знания обычно приходят лишь в результате многолетнего опыта реальной работы. По большому счету перед вами — ярко и увлекательно написанное руководство, которое поможет быстро сделать карьеру в индустрии разработки ПО любому, кто поставил себе такую цель. Конечно, опытные программисты могут найти некоторые идеи автора достаточно очевидными, но и для таких найдутся темы, которые позволят пересмотреть устоявшиеся взгляды и выйти на новый уровень мастерства. Для тех же, кто только в самом начале своего пути как разработчика, чтение данной книги, несомненно, откроет широчайшие перспективы. Издательство выражает благодарность Шувалову А. В. и Курышеву А. И. за помощь в работе над книгой.

Чед Фаулер

Программирование, программы, базы данных / Программирование / Книги по IT

Похожие книги

Язык программирования C++. Пятое издание
Язык программирования C++. Пятое издание

Лучшее руководство по программированию и справочник по языку, полностью пересмотренное и обновленное под стандарт С++11!Р'С‹ держите в руках новое издание популярного и исчерпывающего бестселлера по языку программирования С++, которое было полностью пересмотрено и обновлено под стандарт С++11. Оно поможет вам быстро изучить язык и использовать его весьма эффективными и передовыми способами. Р' соответствии с самыми передовыми и современными методиками изложения материала авторы демонстрируют использование базового языка и его стандартной библиотеки для разработки эффективного, читабельного и мощного кода.С самого начала этой книги читатель знакомится со стандартной библиотекой С++, ее самыми популярными функциями и средствами, что позволяет сразу же приступить к написанию полезных программ, еще не овладев всеми нюансами языка. Большинство примеров из книги было пересмотрено так, чтобы использовать новые средства языка и продемонстрировать РёС… наилучшие СЃРїРѕСЃРѕР±С‹ применения. Эта книга — не только проверенное руководство для новичков в С++, она содержит также авторитетное обсуждение базовых концепций и методик языка С++ и является ценным ресурсом для опытных программистов, особенно желающих побыстрей узнать об усовершенствованиях С++11.Стенли Р'. Липпман работал старшим консультантом в Jet Propulsion Laboratory, архитектором РіСЂСѓРїРїС‹ Visual С++ корпорации Microsoft, техническим сотрудником Bell Laboratories и главным инженером- программистом по анимации в кинокомпаниях Disney, DreamWorks, Pixar и PDI.Р–РѕР·и Лажойе, работающий ныне в кинокомпании Pixar, был членом канадской РіСЂСѓРїРїС‹ разработчиков компилятора C/C++ корпорации IBM, а также возглавлял рабочую группу базового языка С++ в составе международной организации по стандартизации ANSI/ISO.Барбара Э. Му имеет почти тридцатилетний опыт программирования. На протяжении пятнадцати лет она работала в компании AT&T, сотрудничая с Бьярне Страуструпом, автором языка С++, и несколько лет руководила РіСЂСѓРїРїРѕР№ разработчиков С++.• Узнайте, как использовать новые средства языка С++11 и стандартной библиотеки для быстрого создания надежных программ, а также ознакомьтесь с высокоуровневым программированием• Учитесь на примерах, в которых показаны передовые стили программирования и методики проектирования• Р

Барбара Э. Му , Жози Лажойе , Стенли Б. Липпман

Программирование, программы, базы данных