Решение NР-полной задачи

Для решения новой задачи всегда хочется придумать точный эффективный алгоритм. В книге Гэри и Джонсона приведен список известных NР -полных задач и может так оказаться, что наша задача есть в этом списке Что делать в этом случае? Или нашей задачи нет в списке, но мы думаем что она могла бы там быть. Доказательство того, что наша задача NP-полна не решает проблемы. С практической точки зрения мы должны изобрести новый алгоритм или использовать старый, даже если задача NP-полна. Если алгоритм полиномиален, но степень полинома больше 3, то этот алгоритм скорее всего, не достаточно эффективен. Дадим несколько советов.

1. Придумать новый алгоритм. Один из лучших примеров такого подхода симплекс-метод линейного программирования. Хотя симплекс-метод не является полиномиальным в худшем случае, он работает. Одной из главных проблем линейного программирования является вопрос: «Почему симплекс-метод работает так хорошо?» В формулировке задачи линейного программирования значения элементов матрицы А и векторов b и с произвольны Вероятно, в реальных задачах А, b, с удовлетворяют некоторым условия делающим симплекс-метод эффективным. '

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

3. Эвристический подход. Чтобы сформулировать эвристический подход для решения конкретной задачи, обычно испытывают несколько числовых примеров, на которых тренируют интуицию. Если эвристический алгоритм приводит к успеху только в некоторых случаях, мы должны описать эти случаи.

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

5. Использовать общие методы. Если у нас нет времени, и мы не хотим заниматься настоящими исследованиями, можно использовать общие подходы. Вот некоторые из них:

(1) поиск с возвращением,

(2) динамическое программирование,

(3) методы отсечений Гомори.

Специальные модификации даже таких методов, как поиск с возвращением, могут существенно повысить эффективность алгоритма, например, в игре на дереве. Метод отсечений Гомори предназначен для решения задач целочисленного линейного программирования. В некоторых случаях он хорошо зарекомендовал себя, но при решении многих других задач ведет себя крайне плохо.

Вообще говоря, нет систематического метода для создания новых комбинаторных алгоритмов.

Контрольные вопросы

1. Возможно ли в сети существование нескольких кратчайших путей между одними и теми же узлами?

2. Можно ли использовать алгоритм Дейкстры для задачи нахождения кратчайших путей между всеми парами узлов?

3. Можно ли использовать алгоритмы нахождения кратчайшего пути от одного узла до другого для решения задачи нахождения кратчайших путей между всеми парами узлов?

4. Можно ли использовать алгоритм Дейкстры в неориентированной сети с отрицательными весами дуг?

5. Справедливо ли следующее утверждение. В неориентированной сети с положительными расстояниями кратчайшая дуга всегда принадлежит дереву кратчайших путей.

6. Справедливо ли следующее утверждение. Если все длины дуг сети различны, то существует единственное дерево кратчайших путей из V ₀ во все другие узлы.

7. Справедливо ли следующее утверждение. Сложность алгоритма поиска «в ширину» в общем случае меньше чем сложность поиска «в глубину».

8. Можно ли получить одинаковые остовные деревья методом в ширину и глубину, если начало в одном и том же узле?

9. Можно ли получить одинаковые минимальные остовные деревья методом Прима и «жадным»?

10. Если разбить сеть на две части и построить для каждой части минимальное остовное дерево, затем связать эти части кратчайшей дугой, будет ли тогда результирующее дерево минимальным остовным деревом для всей сети?

11. Можно ли для графа построить полный с действительными кратчайшими расстояниями для добавленных ребер используя метод нахождения кратчайших путей между всеми узлами с тройственными операциями, при этом будет выполняться неравенство треугольника?

12. Можно ли получить различные маршруты коммивояжера с одинаковой протяженностью, если применять алгоритм «самой близкой вставки» от одного и того же начального узла?

13. Можно ли получить различные маршруты коммивояжера с разной протяженностью, если применять алгоритм «самой близкой вставки» от одного и того же начального узла?

14. Справедливо ли следующее утверждение. Маршрут коммивояжера найденный алгоритмом «самой близкой вставки» всегда лучше чем, маршрут полученный с помощью алгоритма «ближайшего соседа».

15. Может ли алгоритм «ближайшего соседа» найти оптимальный маршрут коммивояжера?

16. Используются ли данные полученные при решении задачи сетевого планирования о кратчайшем сроке для решения задачи о критическом пути? Если да, то какие?

17. Верно ли что, в критическом пути присутствуют все дуги сетевого графика у которых оба узла являются критическими событиями?

18. Верно ли что, если в задаче о максимальном потоке пропускные способности всех дуг различны, то существует единственный минимальный разрез, разделяющий источник и сток?

19. Верно ли что, если пропускные способности всех дуг различны, то существует единственное множество потоков через дуги, дающее максимальное значение потока?

20. Справедливо ли следующее утверждение. Если в сети больше одного источника, то алгоритм Форда–Фалкерсона для поиска максимального потока применить нельзя.

21. Справедливо ли следующее утверждение. При определении пропускной способности разреза сети учитываются все дуги входящие в разрез.

22. Справедливо ли следующее утверждение. В сети можно найти поток с величиной равной пропускной способности разреза с большей, чем у минимального разреза

23. Справедливо ли следующее утверждение. Для поиска минимального разреза можно использовать доказательство теоремы Форда-Фалкерсона.

24. Верно ли что, в задаче о максимальном потоке любой увеличивающий путь сети содержит только прямые дуги?

25. Верно ли что, в задаче о максимальном потоке использование обратных дуг уменьшает величину потока в сети?

26. Верно ли что, если в сети два разреза скрещиваются, то не существует других нескрещивающихся разрезов.

27. Справедливо ли следующее утверждение. В алгоритмах поиска максимального потока можно использовать принцип поиска в ширину и в глубину.

28. Справедливо ли следующее утверждение. В алгоритме поиска потока минимальной стоимости используется алгоритм Дейкстры.

29. Верно ли что, вершинно-непересекающиеся цепи и реберно-непересекающиеся цепи всегда различны?

30. Есть ли связь между теоремой Менгера и теорией о максимальных потоках?

31. Справедливо ли следующее утверждение. Наибольшее паросочетание – всегда четное число.

32. Возможно, ли чтобы максимальное паросочетание являлось бы и наибольшим?

33. Справедливо ли следующее утверждение. Для двудольного графа матрица смежности и матрица двудольного графа совпадают.

34. Справедливо ли следующее утверждение. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графа позволяет найти максимальное паросочетание.

35. В каких терминах можно сформулировать Теорему Холла?

36. При решении, каких задач можно использовать алгоритм выбора наибольшего сочетания в двудольном графе в качестве процедуры?

37. Какие задачи можно решать с помощью венгерского алгоритма?

38. Верно ли что, при малых размерностях входных данных задачи полиномиальный алгоритм работает быстрее чем экспоненциальный?

39. Верно ли что, понятия NP-полный и NP-трудный эквивалентны?

Литература

1. Ху Т.Ч., Шинг М.Т. Комбинаторные алгоритмы. Перевод с англ. В.Е. Алексеева, Н.Ю.Золотых и др. – Нижний Новгород. Изд-во Нижегородского госуниверситета им. Н.И.Лобочевского, 2004. –329 с.

2. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. – СПб.: Питер, 2008. -384 с.

3. Костюкова, Нина Ивановна. Графы и их применение. Комбинаторные алгоритмы для программистов: учебное пособие / Н. И. Костюкова.— М.: Интернет - Ун-т информ. технологий: БИНОМ. Лаб. знаний, 2007.— 310 с.

4. Логинов Б.М. Введение в дискретную математику. Лекции и упражнения по курсу «Введение в дискретную математику». – Моск. гос. техн. ун-т им. Н.Э.Баумана Калужский филиал. 1998 г. 423 с.

5. Garey M.R., Johnson D.S. Computers and Intractability. — Freeman Co.,1979.

ФИЛИППОВА Анна Сергеевна

Лекции по дисциплине

«комбинаторные алгоритмы»

Учебное издание

Редактор

Подписано в печать. Формат 60х84 1/16.

Бумага офсетная. Печать плоская.

Гарнитура Times New Roman Cyr. Усл. печ. л.. Усл. кр.-отт., Уч.-изд. л.. Тираж ….. зкз.

Заказ №

Уфимский государственный авиационный технический университет

Редакционно-издательский комплекс УГАТУ

450000, Уфа-центр, ул. К.Маркса, 12

^[1]РЕКГ-метод разработан в 1956 году корпорацией Lockheed Air Craft, консалтинговой компанией Booz, Allen & Hamilton и особым проектным бюро ВМС США в процессе создания ракетного комплекса Polaris. Вскоре этот метод стал повсеместно применяться для планирования проектов в вооруженных силах США.