Главная Промышленная автоматика.

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

Таблица 1.1. Таблица несовместимьк цоворотов

Таким образом, поиск оптимального рещения задачи раскраски графа требует больших вычислительных затрат. В этой ситуации можно воспользоваться одним из следующих трех подходов. Если граф небольшой, можно попытаться найти оптимальное рещение, перебрав все возможные варианты раскраски. Однако этот подход не приемлем для больших графов, так как программно трудно организовать эффективный перебор всех вариантов. Второй подход предполагает использование дополнительной информации об исходной задаче. Желательно найти какие-то особые свойства графа, которые исключали бы необходимость полного перебора всех вариантов раскраски для нахождения оптимального рещения. В третьем подходе мы немного изменяем постановку задачи и ищем не оптимальное рещение, а близкое к оптимальному. Если мы откажемся от требования минимального количества цветов раскраски графа, то можно построить алгоритмы раскраски, которые работают значительно быстрее, чем алгоритмы полного перебора. Алгоритмы, которые быстро находят "подходящее", но не оптимальное рещение, называются эвристическими.

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

1. Выбираем произвольную незакрашенную вершину и назначаем ей новый цвет.

2. Просматриваем список незакрашенных верщин и для каждой из них определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет. Если не соединена, то к этой вершине также применяется новый цвет.



Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально большому числу вершин, без возможности пропуска некоторых из них или перекраски ранее закрашенных. Возможны ситуации, когда, будь алгоритм менее "жадным" и пропустил бы некоторые вершины при закраске новым цветом, мы получили бы раскраску графа меньшим количеством цветов. Например, для раскраски графа на рис. 1.3 можно было бы применить два цвета, закрасив вершину 1 в красный цвет, а затем, пропустив вершину 2, закрасить в красный цвет вершины 3 и 4. Но "жадный" алгоритм, основываясь на порядковой очередности вершин, закрасит в красный цвет вершины 1 и 2, для закраски остальных вершин потребуются еще два цвета.


Рис. 1.3. Граф

Применим описанный алгоритм для закраски вершин графа нашей задачи (рис.1.2), при этом первой закрасим вершину АВ в синий цвет. Также можно закрасить в синий цвет вершины АС, AD и ВА, поскольку никакие из этих четырех вершин не имеют общих ребер. Вершину ВС нельзя закрасить в этот цвет, так как существует ребро между верщинами АВ и ВС. По этой же причине мы не можем закрасить в синий цвет верщины BD, DA и DB - все они имеют хотя бы по одному ребру, связывающему их с уже закрашенными в синий цвет верщинами. Продолжая перебор вершин, закрашиваем вершины DC и ED в синий цвет, а вершины ЕА, ЕВ и ЕС оставляем незакрашенными.

Теперь применим второй цвет, например красный. Закраску этим цветом начнем с верщины ВС. Вершину BD можно закрасить красным цветом, вершину DA - нельзя, так как есть ребро между верщинами BD и DA. Продолжаем перебор вершин: вершину DB нельзя закрасить красным цветом, вершина DC уже закрашена синим цветом, а вершину ЕА можно закрасить красным. Остальные незакрашенные верщины имеют общие ребра с верщинами, окрашенными в красный цвет, поэтому к ним нельзя применить этот цвет.

Рассмотрим незакрашенные вершины DA, DB, ЕВ и ЕС. Если вершину DA мы закрасим в зеленый цвет, то в этот цвет также можно закрасить и вершину DB, но верщины ЕВ и ЕС в зеленый цвет закрасить нельзя. К последним двум вершинам применим четвертый цвет, скажем, желтый. Назначенные вершинам цвета приведены в табл. 1.2. В этой таблице "дополнительные" повороты совместимы с соответствующими поворотами из столбца "Повороты", хотя алгоритмом они окрашены в разные цвета. При задании режимов работы светофоров, основанных на одном из цветов раскраски, вполне безопасно включить в эти режимы и дополнительные повороты.

Данный алгоритм не всегда использует минимально возможное число цветов. Можно использовать результаты из общей теории графов для оценки качества полученного решения. В теории графов к-кликой называется множество из к вершин, в котором каждая пара вершин соединена ребром. Очевидно, что для закраски fe-клики необходимо к цветов, поскольку в клике никакие две вершины не могут иметь одинаковый цвет.



Таблица 1.2. Раскраска графа, цредставленного на рис. Т .2

Цвет

Повороты

Дополнительные повороты

Синий

АВ, АС, AD, ВА, DC, ED

Красный

ВС, BD, ЕА

ВА. ОС, ED

Зеленый

DA, DB

AD, ВА, DC, ED

Желтый

ЕВ, ЕС

ВА, DC, ЕА. ED

В графе рис. Ii2 множество из четырех вершин АС, DA, BD и ЕВ является 4-кликой. Поэтому не существует раскраски этого графа тремя и менее цветами, и, следовательно, решение, -представленное в табл. 1.2, является оптимальным в том смысле, что использует минимально возможное количество цветов для раскраски графа. В терминах исходной задачи это означает, что для управления перекрестком, показанным на рис. 1.1, необходимо не менее четырех режимов работы светофоров.

Итак, для управления перекрестком построены четыре режима работы светофорами, которые соответствуют четырем цветам раскраски графа (табл. 1.2). □

Псевдоязык и пошаговая „кристаллизация" алгоритмов

Поскольку для решения исходной задачи мы применяем некую математическую модель, то тем самым мржно формализовать алгоритм решения в терминах этой модели. В начальных версиях алгоритма часто применяются обобщенные операторы, которые затем переопределяются в виде более мелких, четко определенных инструкций. Например, при описании рассмотренного выше алгоритма раскраски графа мы использовали такие выражения, как "выбрать произвольную незакрашенную вершину". Мы надеемся, что читателю совершенно ясно, как надо понимать такие инструкции. Но для преобразования таких неформальных алгоритмов в компьютерные программы необходимо пройти через несколько этапов формализации (этот процесс можно назвать пошаговой кристаллизацией), пока мы не получим программу, полностью состоящую из формальных операторов языка программирования.

Пример 1.2 Рассмотрим процесс преобразования "жадного" алгоритма раскраски графа в программу на языке Pascal. Мы предполагаем, что есть граф G, вершины которого необходимо раскрасить. Программа greedy (жадный) определяет множество вершин, названное newclr (новый цвет), все вершины которого можно окрасить в новый цвет. Эта программа будет вызываться на повторное выполнение столько раз, сколько необходимо для закраски всех вершин исходного графа. В самом первом грубом приближении программа greedy на псевдоязыке показана в следующем листинге.

Листинг 1.1. Первое приближение программы greedy

procedure greedy ( var G: GRAPH; var newclr: SET );P

.{ greedy присваивает переменной newclr множество вершин графа G, которые можно окрасить в один цвет) • begin з

<1);, newclr:= 0\-

(2) for для каждой незакрашенной вершины v из G do

(3) - . if V не соединена вершинами из nevicliJa.eD. begin

(4) пометить v цветом;

(5) добавить v в newclr end

end; { greedy ]

Символ О - стандартное обозначение пустого множества. 20 ГЛАВА 1. ПОСГРОЬНИЕ И АНАЛИЗ АЛГОРИТМОВ





0 1 [2] 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0019