Научная электронная библиотека
Монографии, изданные в издательстве Российской Академии Естествознания

3.7.3. Методы без использования принципа оптимальности Беллмана

Предложенная в работе [57] методика «последовательного анализа, конструирования и отсеивания вариантов» состоит в таком способе построения вариантов и вывода операторов их анализа, когда отсеиваются бесперспективные решения без их полного построения, как только эту бесперспективность удается выявить. По сравнению с динамическим программированием этот метод шире в том смысле, что не предполагает выполнения принципа оптимальности (Беллмана) для рассматриваемой задачи.

Суть метода заключается в том, что, исходя из специфики рассматриваемой задачи, находится (строится) некоторое правило доминирования. Это правило позволяет сравнивать две начальные подпоследовательности  и , определенные на одном и том же множестве элементов . Смысл этого сравнения состоит в том, что мы можем сделать заключение вида «подпоследовательность  “лучше” подпоследовательности ». Это заключение означает, что варианты, содержащие , не могут быть оптимальными. В схеме динамического программирования такое правило доминирования очевидным образом задается, исходя их принципа оптимальности.

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

Применительно к NP-трудным задачам уместно упомянуть «метод ветвей и границ». Вычислительная схема решения задачи коммивояжера этим методом изложена в [51]. Верхняя оценка вычислительной сложности метода ветвей и границ также растет экспоненциально с ростом размерности задачи.


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074