Главная страница
Навигация по странице:

  • в ре- шение (из решения) имеет вид

  • Проверка, сформировано ли решение, заключается в том, чтобы просмотреть массив и определить, все ли его элементы равны истине.

  • Для примера, приведенного выше, массив Gr имеет вид: Gr[l]=Gr[3]=Gr[5]=l; Gr[6]=3. Фрагмент основной логики.

  • Поиск цвета раскраски для одной вершины можно реализо- вать с помощью следующей функции

  • Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    АнкорОкулов.Программирование.в.алгоритмах.pdf
    Дата26.04.2017
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаОкулов.Программирование.в.алгоритмах.pdf
    ТипДокументы
    #5718
    страница12 из 26
    1   ...   8   9   10   11   12   13   14   15   ...   26
    От
    [ ]
    [ ]
    Gg
    [1..5]
    [4,5]
    Ss
    (1)
    (1,4)
    Примечания
    Выбираем первую вершину
    Вершины 2, 3 исключаются из списка кандидатов, остаются вершины с номерами 4,5
    Первое уточнение «черного ящика А».
    If
    [] Then
    Gg с учетом ранее
    использованных вершин>
    Else
    Его суть в том, что если выбирать из ранее использованных вершин нечего, то множество кандидатов совпадает со значени- ем Qp, и далее по логике мы «тупо» выбираем первую вершину из Qp. Переходим к следующему вызову процедуры Find.
    3 2
    [ ]
    [5]
    [ ]
    [4]
    [ ]
    [5]
    (1,4)
    (1,5)
    Вывод первого максимального независимого множества и выход в предыдущую копию Find
    Исключаем вершину 4 из Qp и включаем ее
    Продолжает работу цикл While процедуры Find с парамет- ром k, равным 2. Выбираем следующую вершину — это верши- на 5. И вызываем процедуры Find с другими значениями пара- метров.
    3 2
    [ ]
    [ ]
    [ ]
    [4,5]
    [ ]
    [ ]
    (1,5)
    Вывод второго максимального независимого множества
    Цикл While закончен, выход в предыдущую копию процедуры Find

    172
    Алгоритмы на графах
    Уточнение «черного ящика Б». Первое: необходимо исклю- чить вершину i из Qp и включить ее в
    Второе: следует от- корректировать множество Gg. Выбор на этом шаге вершин, не смежных с i, приведет к генерации повторяющихся максималь- ных независимых множеств, поэтому следует выбирать верши- ны из пересечения множеств Qp и A[i]. Итак, «черный ящик
    Б».
    =Qp- [i ]
    [i ] ;
    ;
    Следующий шаг — выход в предыдущую версию при этом значение
    1 1
    2 3
    4 3
    2 1
    2
    [2..5]
    [3,5]
    [5]
    [ ]
    [ ]
    [5]
    [3..5]
    [5]
    [1]
    [1]
    [ ]
    [ ]
    [ ]
    [5]
    [3]
    [1.2]
    [2]
    [1-5]
    [2..3]
    [3,5]
    [5]
    [ ]
    [ ]
    [ ]
    [2,3]
    (2)
    (2,3)
    (2,3,5)
    (3)
    Однако после работы «черного ящика Б» имеем следующие значения переменных
    Вывод третьего максимального независимого множества
    Согласно логике «черного ящика
    Б» множество кандидатов Gg
    становится пустым
    Итак, мы первый раз попадаем в процедуру Find, и множество при этом не пусто
    Должна работать логика «черного ящика А» при непустом значении
    Замечание 1. Если существует вершина при- надлежащая такая, что пересечение A[j] и Qp пусто, то да- льнейшее построение максимального независимого множества бессмысленно — вершины из A[j] не попадут в него (в нашем примере как раз этот случай). Замечание 2. Если нет вершин из удовлетворяющих первому замечанию, то какую вер- шину из Qp следует выбирать? Ответ: вершину для некоторого значения причем мощность пересечения множеств минимальна. Данный выбор позволяет со- кратить перебор. Итак, окончательная логика «черного ящика
    А».
    Begin
    For
    To N Do

    4. Алгоритмы на графах
    173
    j In
    Then
    If Number
    Then Begin
    End;
    Gg:=Qp*A[i]
    End
    Закончим трассировку примера.
    2
    1
    [5]
    [1,2,3]
    [ ]
    [ ]
    Выход в основную программу
    Независимые максимальные множества графа найдены.
    4.7.3. Доминирующие множества
    Для графа доминирующее множество вершин есть множество вершин такое, что для каждой вершины j, не входящей в S, существует ребро, идущее из некоторой верши- ны множества в вершину Доминирующее множество назы- вается минимальным, если нет другого доминирующего множе- ства, содержащегося в нем.
    Пример.
    Доминирующие множества (1, 2,
    3), (4, 5, 6, 7, 8, 9), (1,2, 3, 8, 9), (1,
    2, 3, 7) и т. д. Множества
    2, 3),
    (4, 5, 6, 7, 8, 9) являются минималь- ными. Если Q — семейство всех ми- нимальных доминирующих мно- жеств графа, то число называется числом доминирования графа, а множество S*, на котором этот минимум достигается, называется наименьшим доминирующим множеством. Для нашего примера
    Задача. Пусть город можно изобразить как квадрат, разде- ленный на районов. Считается, что опорный пункт мили- ции, расположенный в каком-либо районе, может контролиро- вать не только этот район, но и граничащие с ним районы.
    Требуется найти наименьшее количество пунктов милиции и места их размещения, такие, чтобы контролировался весь го- род.
    Представим каждый район вершиной графа и ребрами сое- диним только те вершины, которые соответствуют соседним районам. Нам необходимо найти число доминирования графа и

    174 4. Алгоритмы на графах хотя бы одно наимень- шее доминирующее мно- жество. Для данной зада- чи и наименьших множеств есть (3, 5, 12, 14). Эти вершины выделены на рисунке.
    4.7.4. Задача о наименьшем покрытии
    Рассмотрим граф. На рисунке показана его матрица смежно- сти А и транспонированная матрица смежности с единичными диагональными элементами А*. Задача определения доминиру- ющего множества графа G эквивалентна задаче нахождения та- кого наименьшего множества столбцов в матрице А*, что каж- дая строка матрицы содержит единицу хотя бы в одном из выбранных столбцов. Задачу о поиске наименьшего множества столбцов, «покрывающего» все строки матрицы, называют за- дачей о наименьшем покрытии. В общем случае матрица не обязательно является квадратной, кроме того, вершинам графа
    (столбцам) может быть приписан вес, в этом случае необходимо найти покрытие с наименьшей общей стоимостью. Если введе- но дополнительное ограничение, суть которого в том, чтобы любая пара столбцов не имела общих единиц в одних и тех же строках, то задачу называют задачей о наименьшем разбиении.
    Предварительные замечания. 1. Если некоторая строка мат- рицы А* имеет единицу в единственном столбце, т. е. больше нет столбцов, содержащих единицу в этой строке, то данный столбец следует включать в любое решение.
    2. Рассмотрим множество столбцов матрицы А*, имеющих единицы в конкретной строке. Для нашего примера:
    6,

    4. Алгоритмы на графах
    175 7,
    2, 5,
    3, 5),
    4),
    3, 4, 5),
    6),
    7),
    Видим, что Из этого сле- дует, что 5-ю строку можно не рассматривать, поскольку любое множество столбцов, покрывающее 4-ю строку, должно покры- вать и 5-ю. Четвертая строка доминирует над пятой.
    4.7.5. Метод решения задачи о наименьшем разбиении
    Попытаемся осознать метод решения задачи, рассматривая,
    как обычно, пример. У нас есть ориентированный граф, его матрица смежности и транспонированная матрица смежности с единичными диагональными элементами. Исследуем структуру матрицы А*. Нас интересует, какие столбцы содержат единицу в первой строке, какие столбцы содержат единицу во второй строке и не содержат в первой и так далее. С этой целью можно было бы переставлять столбцы в матрице А*, но оставим ее «в покое». Будем использовать дополнительную матрицу ее тип: Type
    = Array
    l..MaxN+l] Of Integer; Var
    Bl:Pr; где MaxN — максимальная размерность задачи. Почему плюс единица (технический прием — «барьер»), будет ясно из последующего изложения (процедура Press).
    При инициализации матрица должна иметь вид: в первой строке —
    3 . . N 0], а все остальные элементы равны нулю.
    Наше исходное предположение заключается в том, что все столбцы матрицы имеют единицы в первой строке. Прове- рим его. Будем просматривать элементы очередной строки (i)
    матрицы
    Если то со значением Bl[i,j], как номе- ром столбца матрицы А*, проверим соответствующий элемент
    А*. При его неравенстве нулю элемент остается на своем мес- те, иначе он переписывается в следующую строку матрицы а элементы текущей строки сдвигаются вправо, сжимаются
    (Press). Итак, для N-1 строки матрицы
    Для нашего приме- ра матрица после этого преобразования будет иметь вид:

    176 4. Алгоритмы на графах
    В задаче заданы стоимости вершин графа или стоимости столбцов матрицы А*, и необходимо найти разбиение наимень- шей стоимости. Пусть стоимости описываются в массиве Price
    Of Integer) и для примера на рисунке имеют значения [15 13 43 8 9 10]. Осталась чисто техническая де- таль — отсортировать элементы каждой строки матрицы по возрастанию стоимости соответствующих столбцов матрицы
    А*. Результирующая матрица имеет вид:
    а логика формирования приведена ниже по тексту (Blocs).
    Procedure
    блоков, В1 -
    глобальная
    *}
    Procedure Sort;
    Begin
    End;
    Procedure
    элементы
    строки с номером i, начиная с позиции
    (столбца)
    на одну позицию вправо.*}
    Var
    Begin
    k:=j;
    While
    Do Begin { *Поэтому размерность
    матрицы с плюс
    В последнем
    столбце строки всегда записан 0. *}
    Bl[i,k]:=Bl[i,k+l];
    (k) ;
    End;
    End;
    Var
    Begin

    Алгоритмы на графах 177
    (B1)
    ;
    For i:=l
    N Do
    что
    в первом блоке все столбцы. *}
    For i:=l
    Do Begin
    While
    Do Begin
    If
    Then
    не
    в этом блоке.
    (cnt) ;
    в следующую
    строку. *}
    Press (i,j);
    Dec(j)
    End;
    Inc(j);
    End;
    End;
    Sort;
    End;
    Изменим чуть-чуть
    Какой вид бу- дет иметь матрица
    После этой предварительной работы мы имеем вполне «при- личную» организацию данных для решения задачи путем пере- бора вариантов. Матрица Bl разбита на блоки, и необходимо выбрать по одному элементу (если соответствующие строки ещё
    не покрыты) из каждого блока. Процесс выбора следует про- должать до тех пор, пока не будут включены в «покрытие» все строки или окажется, что некоторую строку нельзя включить.
    Продолжим рассмотрение метода. Если при поиске незави- симых множеств мы шли «сверху вниз», последовательно уточ- няя логику, то сейчас попробуем идти «снизу вверх», склады- окончательное решение из сделанных «кирпичиков». Как обычно, следует начать со структур данных. Во-первых, мы ищем лучшее решение, т. е. то множество столбцов, которое удовлетворяет условиям задачи (не пересечение и «покрытие»
    всего множества строк), и суммарная стоимость этого множест- ва минимальна. Значит, необходима структура данных для хранения этого множества и значения наилучшей стоимости и,
    соответственно, структуры данных для хранения текущего
    (очередного) решения и его стоимости. Во-вторых, в решении строка может быть или не быть. Следовательно, нам требуется как-то фиксировать эту информацию. Итак, данные.

    Алгоритмы на графах
    Type
    Of Boolean;
    Var
    решение. *}
    решение. *}
    - признак того, что
    строка i "покрыта" текущим решением. *}
    Логика включения (исключения) столбца с номером k в ре-
    шение (из решения) имеет вид:
    Procedure Include
    {*Включить столбец
    в
    *}
    Var j
    Begin
    цена решения. *}
    с номером к в решение.
    For
    N Do
    If
    Then
    "покрытые" столбцом к.*}
    Ends-
    Procedure
    столбец
    из
    *}
    Var
    Begin
    For
    To N Do
    If (A*[j,k]=l) And R[j] Then R[j]
    End;
    Проверка, сформировано ли решение, заключается в том,
    чтобы просмотреть массив
    и определить, все ли его элементы
    равны истине.
    Function
    Var
    Begin
    j:=l;
    While
    And R[j] Do Inc(j);
    End;
    Кроме перечисленных действий, нам необходимо уметь опре- делять — «можно ли столбец с номером k включать в решение».
    Для этого следует просмотреть столбец с номером k матрицы и проверить, нет ли совпадений единичных элементов со значе- нием True соответствующих элементов массива R.

    Алгоритмы на графах 179
    Function Cross
    -.Boolean;
    столбца с частичным решением, сформированным
    Var
    Begin
    While
    And Not(R[j] And (A*[j,k]=l)) Do Inc(j) ;
    End;
    Заключительная логика поиска (Find) имеет в качестве па- раметров номер блока (строки матрицы Bl) — переменная Ыос
    и номер позиции в строке. Первый вызов —
    Procedure Find (Ыос, jnd: Integer) ;
    Begin
    If Result Then Begin
    If P
    Pbetter:=P;
    Sbetter:=S;
    End;
    End
    Else If
    [bloc, jnd] =0 Then Exit
    Else If
    ) Then Begin
    Include
    );
    Find(bloc+l,l);
    );
    End
    Else If R[bloc] Then
    Else
    End;
    Будет ли правильно работать процедура Find при изменен- ной матрице А* (изменение приведено выше по тексту)? Испра- вьте неточность.
    Нам осталось дать общую логику, но после выполненной ра- боты она не вызывает затруднений.
    Program
    .;
    Type . . .
    Var . . .
    Procedure
    и инициализация данных.
    Begin
    End;

    180 4. Алгоритмы на графах
    Procedure
    *}
    Begin
    End;
    {*Процедуры и функции, рассмотренные ранее по тексту. *}
    Begin
    логика.
    Blocs;
    Find (1,1) ;
    Print;
    End.
    4.8. Раскраски
    4.8.1. Правильные раскраски
    Пусть
    — неориентированный граф. Произвольная функция где принадлежит множеству натура- льных чисел, называется вершинной fc-раскраской графа G.
    Раскраска называется правильной, если для любых смежных вершин и и v. Граф, для которого существует прави- льная называется fe-раскрашиваемым. Минималь- ное число при котором граф G является называется хроматическим числом графа и обозначается
    Пример. Меньшим количеством цветов граф пра- вильно раскрасить нельзя из-за наличия треугольников.
    Рядом с «кружками» — вер- шинами графа — указаны но- мера цветов.
    Метод получения правиль- ной раскраски достаточно прост — закрашиваем очеред- ную вершину в минимально возможный цвет. Введем следую- щие структуры данных.
    Const
    количество вершин
    *}
    Type
    Of V;
    Of V;
    Var
    MyAr ray; {*Gr - каждой вершине графа
    определяется номер цвета. *}

    4. Алгоритмы на графах 181
    Для примера, приведенного выше, массив Gr имеет вид:
    Gr[l]=Gr[3]=Gr[5]=l;
    Gr[6]=3.
    Фрагмент основной логики.
    описания графа>;
    For i:=l
    N Do Gr[i] : = [Color (i ,0) ] ;
    <вывод
    Поиск цвета раскраски для одной вершины можно реализо-
    вать с помощью следующей функции:
    Function
    - номер
    окрашиваемой вершины, t - номер цвета,
    с которого следует искать раскраску данной
    вершины, А - матрица смежности, Gr -
    результирующий массив. *}
    Var
    Begin
    ];
    For j:=l To
    Do If
    Then
    ;
    множество цветов, в которые
    окрашены смежные вершины с меньшими
    *}
    j:=t;
    Repeat
    минимального номера цвета,
    в который можно окрасить данную
    *}
    Inc(j) ;
    Until
    In Ws)
    End;
    Пример. Получаем правильную рас- краску: Gr[l]=l,
    Gr[3]=3,
    Gr[5]=4. Однако минимальной раскрас- кой является: Gr[l]=l,
    и и хроматическое число графа равно трем.
    4.8.2. Поиск минимальной раскраски вершин графа
    Метод основан на простой идее [16], и в некоторых случаях он дает точный результат. Пусть получена правильная раскрас- ка графа, q — количество цветов в этой раскраске. Если суще- ствует раскраска, использующая только q— 1 цветов, то все вер- шины, окрашенные в цвет q, должны быть окрашены в цвет g,

    182 4. Алгоритмы на графах меньший q. Согласно логике формирования правильной рас- краски вершина была окрашена в цвет q, потому что не могла быть окрашена в цвет с меньшим номером. Следовательно, не- обходимо попробовать изменить цвет у вершин, смежных с рас- сматриваемой. Но как это сделать? Найдем вершину с минима- льным номером, окрашенную в цвет q, и просмотрим вершины,
    смежные с найденной. Попытаемся окрашивать смежные вер- шины не в минимально возможный цвет. Для этого находим очередную смежную вершину и стараемся окрасить ее в другой цвет. Если это получается, то перекрашиваем вершины с боль- шими номерами по методу правильной раскраски. При неуда- че, когда изменить цвет не удалось или правильная раскраска не уменьшила количества цветов, переходим к следующей вер- шине. И так, пока не будут просмотрены все смежные верши- ны.
    Опишем логику, используя функцию Color предыдущего па- раграфа.
    Var
    i : V;
    Procedure MaxMin (Var c,t:V) ;
    Begin
    End;
    Procedure
    Begin
    End;
    Begin
    <ввод данных, инициализация
    For
    N Do
    правильная
    *}
    Repeat
    <найти вершину с минимальным номером
    ,
    имеющую максимальный цвет раскраски
    -
    >;
    цвет раскраски в соответствии
    с описанной идеей - процедура
    Until
    [MinNum] ;{ *До тех пор, пока метод
    улучшает раскраску. *}
    <вывод минимальной (или почти минимальной!)
    раскраски>;
    End.

    Алгоритмы на графах 183
    Если работа процедуры достаточно очевидна, то
    Change требует дальнейшего уточнения.
    Procedure Change
    V) ;
    r,q:V;
    Function
    смежную
    с 1 вершину с наибольшим номером и
    не принадлежащую множеству
    *}
    Var
    Begin
    While
    And (i In Rs) And
    Do Begin
    If
    Then
    Dec(i) ;
    End
    End;
    Begin
    Ws: = [] ;
    q:=MaxCon (t,Ws) ;
    While q<>0 Do Begin
    If r
    с номерами, большими t, по методу
    правильной
    Else Ws:=Ws+[q];
    End;
    End;
    Осталось заметить, что при изменении цвета у вершин с но- мерами, большими значения t, по методу правильной раскрас- ки следует запоминать в рабочих переменных значения Gr и
    МахС, так как при неудаче (раскраску не улучшим) их необхо- димо восстанавливать, и на этом закончить уточнение логики.
    При любом упорядочении вершин допустимые цвета для вершины с номером i удовлетворяют условию Это очевидно,
    так как вершине i предшествует i— 1 вершина, и, следователь- но, никакой цвет не использовался. Итак, для вершины 1
    допустимый цвет 1, для 2 — цвет 1 и 2 и так далее. С точки зрения скорости вычислений вершины следует помечать (при- сваивать номера) так, чтобы первые q вершин образовывали наибольшую клику графа G. Это приведет к тому, что каждая из этих вершин имеет один допустимый цвет и процесс возвра-

    184 4. Алгоритмы на графах та в алгоритме можно будет заканчивать при достижении вер- шины из этого множества.
    В алгоритме рассматриваются только вершины, смежные с вершиной, окрашенной в максимальный цвет. Однако следует работать и с вершинами, являющимися смежными для смеж- ных. На рисунке приведены примеры графов и их раскраски.
    Первая цифра в круглых скобках обозначает значение цвета при правильной раскраске, вторая — при минимальной.
    Для графов на первом и третьем рисунках алго- ритм дает правильный результат. Для графа на втором рисунке при изме- нении цвета вершины с номером 6 необходимо просматривать вершины,
    смежные к смежным с шестой вершиной. Рас- смотренный алгоритм требует очередной моди- фикации. Самый интересный случай на последнем рисунке. Мы не можем получить минимальную раскраску с помощью рас- смотренного алгоритма (даже если будем рассматривать все вер-

    4. Алгоритмы на графах
    185
    шины, смежные к смежным), хотя она, конечно, существует и совпадает с предыдущей. Итак, результат работы алгоритма за- висит от нумерации вершин графа, а таких способов — способов нумерации N!.
    4.8.3. Использование задачи о наименьшем покрытии при раскраске вершин графа
    При любой правильной раскраске графа G множество вершин,
    окрашиваемых в один и тот же цвет, является независимым мно- жеством. Поэтому раскраску можно понимать как разбиение вер- шин графа на независимые множества. Если рассматривать толь- ко максимальные независимые множества, то раскраска — это не что иное, как покрытие вершин графа G множествами этого типа.
    В том случае, когда вершина принадлежит не одному максималь- ному независимому множеству, допустимы различные раскраски с одним и тем же количеством цветов. Эту вершину можно окра- шивать в цвета тех множеств, которым она принадлежит.
    Исходным положением метода является получение всех максимальных независимых множеств и хранение их в неко- торой матрице где W — количество максимальных независимых множеств. Элемент матрицы M[i,j] равен едини- це, если вершина с номером i принадлежит множеству с номе- ром у, и нулю в противном случае. Если затем каждому столбцу поставить в соответствие единичную стоимость, то задача рас- краски не что иное, как поиск минимального количества столб- цов в матрице М, покрывающих все ее строки. Каждый стол- бец соответствует определенному цвету.
    Пример. Имеем пять максимальных независимых множеств и два варианта решения задачи о покрытии (строки А
    В). В
    обоих случаях вершина 4 может быть Окрашена как во второй,
    так и в третий цвета.
    1   ...   8   9   10   11   12   13   14   15   ...   26


    написать администратору сайта