Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания
Дискретная оптимизация и моделирование в условиях неопределенности данных
Перепелица В. А., Тебуева Ф. Б.,
3.7.3. Методы без использования принципа оптимальности Беллмана
Предложенная в работе [57] методика «последовательного анализа, конструирования и отсеивания вариантов» состоит в таком способе построения вариантов и вывода операторов их анализа, когда отсеиваются бесперспективные решения без их полного построения, как только эту бесперспективность удается выявить. По сравнению с динамическим программированием этот метод шире в том смысле, что не предполагает выполнения принципа оптимальности (Беллмана) для рассматриваемой задачи.
Суть метода заключается в том, что, исходя из специфики рассматриваемой задачи, находится (строится) некоторое правило доминирования. Это правило позволяет сравнивать две начальные подпоследовательности 
и 
, определенные на одном и том же множестве элементов 
. Смысл этого сравнения состоит в том, что мы можем сделать заключение вида «подпоследовательность 
“лучше” подпоследовательности 
». Это заключение означает, что варианты, содержащие , не могут быть оптимальными. В схеме динамического программирования такое правило доминирования очевидным образом задается, исходя их принципа оптимальности.
Если говорить о решении задачи коммивояжера алгоритмом последовательного анализа и отсеивания вариантов, то на 
- ом шаге рассматривается и анализируется в целях потенциально возможного отсеивания 
вариантов подпоследовательностей вида 
. Отсюда трудоемкость решения задачи коммивояжера этим методом составляет величину такого же порядка, как и трудоемкость алгоритма динамического программирования. Аналогичное замечание можно высказать по отношению к гораздо более широкому классу задач [57], для которого, однако, рассматриваются другие соотношения.
Применительно к NP-трудным задачам уместно упомянуть «метод ветвей и границ». Вычислительная схема решения задачи коммивояжера этим методом изложена в [51]. Верхняя оценка вычислительной сложности метода ветвей и границ также растет экспоненциально с ростом размерности задачи.