- •С.Н.Дроздов
- •Введение
- •1. Методы решения комбинаторных задач
- •1.1. Понятие об оценке эффективности алгоритмов и программ
- •1.2. Понятие комбинаторной задачи
- •1.3. Примеры комбинаторных задач
- •1.4. Организация исчерпывающего перебора
- •1.5. Сокращение перебора
- •1.6. Метод ветвей и границ
- •1.7. Метод динамического программирования
- •1.8. Метод a-b-отсечений для позиционных игр с полной информацией
- •1.9. Приближенные и эвристические методы решения задач комбинаторной оптимизации
- •2. Элементы теории сложности вычислений
- •2.1. Основные понятия и проблемы теории сложности вычислений
- •2.2. Полиномиальная сводимость задач
- •2.3. Недетерминированные машины Тьюринга и np-задачи
- •2.5. Теорема Кука
- •2.6. Примеры np-полных задач
- •2.6. Псевдополиномиальные задачи
- •2.7. Практическое значение результатов теории сложности вычислений
- •Литература
- •Дроздов Сергей Николаевич
2.6. Псевдополиномиальные задачи
Приведенный список NP-полных задач включает и рассмотренную нами ранее задачу о рюкзаке. Однако в п.1.7 была приведена оценка эффективности алгоритма Беллмана для этой задачи:T(n,B) = O(nB2). Это ведь полиномиальная оценка, причем очень невысокой степени. Практика также подтверждает высокую эффективность данного алгоритма. Так что же, не тот ли это самый случай полиномиального алгоритма дляNP-полной задачи, из которого должно проистечь столько хороших последствий?
Не все так просто.
В п.2.1 уже отмечалось, что в качестве аргумента оценок эффективности следует использовать не расплывчатое понятие «размерность задачи», а четко определенное «длина описания задачи». Однако как связан параметр объема рюкзака Bс длиной соответствующей задачи|z|? ПосколькуB– целое число, а длина любой разумной кодировки числа пропорциональна логарифму этого числа, то при фиксированномnимеем:|z| = O(log(B)), откуда получаем:B = O(2|z|). Значит, полиномиальная относительноBоценка эффективности алгоритма Беллмана является на самом деле экспоненциальной относительно|z|. Но если алгоритм экспоненциальный, то почему он столь эффективен? Дело в том, что существенное замедление работы алгоритма будет ощущаться только при очень больших значенияхB. Заметим, что увеличение длины описания задачи на каких-то 20 битов позволяет задать в 1000000 раз большее значениеB! Конечно, такая задача будет за пределами практической разрешимости.
Подобная ситуация, когда для задачи, имеющей числовые1параметры, известен алгоритм, проявляющий экспоненциальный характер только при очень больших значениях параметров, встречается не так уж редко. Подобные алгоритмы, как и решаемые ими задачи, носят названиепсевдополиномиальных.
Более строгое определение выглядит так. Пусть M(z)– некоторая функция, задающая значение числового параметра индивидуальной задачиz. Если таких параметров несколько, в качествеM(z)можно взять или максимальное, или среднее значение, а если задача вовсе не имеет числовых параметров (например, раскраска графа, шахматы и т.п.), тоM(z) = 0. Алгоритм называется псевдополиномиальным, если он имеет оценку трудоемкостиTмакс(z) = O(P(|z|, M(z))), гдеP– некоторый полином от двух переменных.
Ясно, что всякий полиномиальный алгоритм является также и псевдополиномиальным (с полиномом, не зависящим от второго аргумента), обратное же, как мы видели, не имеет места.
Псевдополиномиальные алгоритмы, формально относящиеся к экспоненциальным, на практике работают как полиномиальные во всех случаях, кроме очень больших значений числового параметра.
Отсюда, кстати говоря, следует, что экспоненциальная оценка – это еще не смертный приговор эффективности алгоритма. Даже если алгоритм имеет плохую оценку, может оказаться, что на самом деле он работает медленно только при каких-то маловероятных обстоятельствах, вроде огромного рюкзака.
Существуют NP-полные задачи с числовыми параметрами, для которых нет и не может быть псевдополиномиальных алгоритмов2. Такие задачи называютсяNP-полными в сильном смысле. К их числу относятся, например, задача о коммивояжере и задача о трех станках.