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

Если получен, то заканчиваем поиск.

Переход к этапу12.

Иначе переходим к следующему этапу.

Этап5.

Осуществим сортировку подмножеств по два, в соответствии с числом входов в вершину графа рёбер графа.

Этап6.

Выберем из отсортированного множества подмножеств по два графа N уг лучших подмножеств, в соответствии с числом входов в вершину графа для этих подмножеств.

Этап7.

Объединим каждое подмножество по два в подмножества по три или четыре в зависимости от условий задачи.

Так, как осуществляется склейка путей графа русским методом в задаче коммивояжера.

Определим число входов в вершину графа рёбер графа для данного множества вершин по три или четыре, которые запомним для этого подмножества.

Получим множество подмножеств по три или четыре.

Если множество подмножеств по три или по четыре оказывается пустым, то увеличиваем N уг, допустим на 1, и переходим к этапу3.

Определим, получен ли искомый результат или нет.

Если получен, то заканчиваем поиск.

Переход к этапу12.

Иначе переходим к следующему этапу.

Этап8.

Осуществим сортировку подмножеств вершин по три или четыре, в соответствии с числом входов в вершину графа рёбер графа, русского метода.

Этап9.

Выберем из отсортированного множества подмножеств вершин по три или четыре N уг лучших подмножеств, в соответствии с числом входов в вершину графа для этих подмножеств.

Этап10.

Объединим каждое подмножество вершин по три в подмножество вершин по шесть или пять.

Или подмножество вершин по четыре во множества подмножеств по восемь или семь.

В полном соответствии с правилами русского метода, указанными в задаче коммивояжера.

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

Определим, получен ли искомый результат или нет.

Если получен, то заканчиваем поиск.

Переход к этапу12.

Иначе переходим к следующему этапу.

Этап11.

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

Определим

N уг = N макс.

Если равен то переходим к этапу 12.

Иначе увеличиваем N уг, допустим, на 1 и переходим к этапу 3.

Этап12.

Анализ полученного результата.

Оценка полученного решения.

Если не удовлетворяет то уточняем N уг и N макс.

Переходим к этапу 2.

Иначе заканчиваем работу.

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

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

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

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

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

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

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

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.