Практическое значение результатов теории сложности вычислений

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

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

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

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

Если же окажется, что данная задача является одной из NP-полных – что делать тогда? Прежде всего, не терять мужества. Если отбросить непрактичные попытки срочно найти полиномиальный алгоритм для NP-полной задачи, то остаются два возможных пути.

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

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

Литература

1. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476с.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536с.

3. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981. 366с.

4. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368с.

5. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352с.

6. Адельсон-Вельский Г.М., Арлазаров В.Л., Донской М.В. Программирование игр. М.: Наука, 1978. 256с.

7. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416с.

8. Кристофидес Н. Теория графов. Алгоритмический подход . М.: Мир, 1978. 432с.

9. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976. 736с.

Дроздов Сергей Николаевич

Комбинаторные задачи