Составители:
Рубрика:
что задача П является NP-полной, достаточно доказать, что
q
∝
∝
∝
П … П .
П
q1 2
Например, в [15] показано, что задача выполнимости к.н.ф
сводится к задаче о полном подграфе, которая в свою очередь
сводится к задаче о вершинном покрытии, а последняя - к задаче о
сложности д.н.ф. частичной булевой функции.
NP-трудные задачи
Задача Π называется NP-трудной, если Π - произвольная задача
(т.е. не обязательно, что Π∈NP) распознавания свойств, к которой
сводится некоторая NP-полная задача. К NP-трудным могут
относиться не только задачи распознавания свойств, но и другие
переборные задачи.
Точное решение NP-трудной (так же как и NP-полной) задачи в
общем случае может быть получено только за экспоненциальное
время. Следовательно, решать ее переборным алгоритмом
неэффективно при большом количестве вариантов перебора. Одним
из подходов к решению NP-трудных задач является сокращение
перебора по схеме ветвей и границ. Эта схема перебора позволяет
опознать бесперспективные частичные решения, в результате чего от
дерева поиска на одном шаге отсекается целая ветвь. Однако в
общем случае схема ветвей и границ не выводит рассматриваемые
задачи из класса NP-трудных.
Приведем примеры NP-трудных задач: задача коммивояжера и
задача построения сингулярной скобочной формы.
Задача коммивояжера. Эта задача, поставленная еще в 1934 г., является одной из
самых важнейших задач в теории графов. В области оптимизации дискретных задач задача
коммивояжера служит своеобразным полигоном, на котором испытываются все новые
методы.
Постановка задачи. Коммивояжер (бродячий торговец) должен
выйти из первого города, посетить по разу в неизвестном порядке
города 2, 3, …, n и вернуться в первый город. Расстояния между
всеми городами известны. В каком порядке следует обходить города,
чтобы замкнутый путь коммивояжера был кратчайшим? В терминах
теории графов: найти гамильтонов цикл в графе минимальной длины.
Задача построения сингулярной скобочной нормальной
180
Страницы
- « первая
- ‹ предыдущая
- …
- 94
- 95
- 96
- 97
- 98
- …
- следующая ›
- последняя »
