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

Чтение книги онлайн.

СКАЧАТЬ следующий способ решения задачи о вершинном покрытии:

      Этап1.

      Выберем интервал изменения числа угадывания (N уг) для данной конкретной задачи. Этот интервал зависит от характеристик этой задачи.

      Он изменяется от 1 до определённого, предварительно, для этой задачи значения (N макс).

      Процесс изменения можно осуществлять, например, путём прибавления 1 к значению N уг.

      Это не является принципиально важным.

      Этап2.

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

      Этап3.

      Выберем из отсортированного множества вершин графа N уг «лучших» вершин (больше количество входов рёбер графа в вершину), в соответствии с числом входов в вершину графа рёбер графа.

      Этап4.

      Объединим каждую вершину графа с другой каждой вершиной графа во множества по две вершины.

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

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

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

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

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

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

      Этап5.

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

      Этап6.

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

      Этап7.

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

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

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

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

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

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

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

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

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

      Этап8.

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

      Этап9.

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

      Этап10.

      Объединим каждое подмножество вершин по три в подмножество вершин по шесть СКАЧАТЬ