Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина

Геннадий Степанов

В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач.В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач.Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.

Задача о доминирующем множестве

В теории графов доминирующее множество для графаG = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.

Число доминирования γ (G) — это число вершин в наименьшем доминирующем множестве G.

Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ (G) ≤ K для заданного графа G и числа K.

Задача является классической NP — полной проблемой разрешимости в теории вычислительной сложности.

Таким образом, в настоящее время полагают, что не существует эффективного алгоритма для нахождения наименьшего доминирующего множества для заданного графа.

Точные алгоритмы

Минимальное доминирующее множество графа с nвершинами может быть найдено за время O (2nn) путём просмотра всех подмножеств вершин.

Конец ознакомительного фрагмента.