Структуры данных и алгоритмы (1021739), страница 4
Текст из файла (страница 4)
В этом алгоритме сначала мы пытаемся раскрасить как можно больше вершин в один цвет, затем закрашиваем во второй цветтакже по возможности максимальное число оставшихся вершин, и т.д. При закраскевершин в новый цвет мы выполняем следующие действия.1.2.Выбираем произвольную незакрашенную вершину и назначаем ей новый цвет.Просматриваем список незакрашенных вершин и для каждой из них определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет.
Еслине соединена, то к этой вершине также применяется новый цвет.18ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВЭтот алгоритм назван "жадным" из-за того, что каждый цвет применяется кмаксимально большому числу вершин, без возможности пропуска некоторых изних или перекраски ранее закрашенных. Возможны ситуации, когда, будь алгоритм менее "жадным" и пропустил бы некоторые вершины при закраске новымцветом, мы получили бы раскраску графа меньшим количеством цветов. Например, для раскраски графа на рис.
1.3 можно было бы применить два цвета, закрасив вершину 1 в красный цвет, а затем, пропустив вершину 2, закрасить вкрасный цвет вершины 3 и 4. Но "жадный" алгоритм, основываясь на порядковой очередности вершин, закрасит в красный цвет вершины 1 и 2, для закраскиостальных вершин потребуются еще два цвета.Рис.
1.3. ГрафПрименим описанный алгоритм для закраски вершин графа нашей задачи(рис.1.2), при этом первой закрасим вершину АВ в синий цвет. Также можно закрасить в синий цвет вершины AC, AD и ВА, поскольку никакие из этих четырех вершин не имеют общих ребер. Вершину ВС нельзя закрасить в этот цвет, так как существует ребро между вершинами АВ и ВС. По этой же причине мы не можем закрасить в синий цвет вершины BD, DA и DB — все они имеют хотя бы по одномуребру, связывающему их с уже закрашенными в синий цвет вершинами.
Продолжаяперебор вершин, закрашиваем вершины DC и ED в синий цвет, а вершины ЕА, ЕВ иЕС оставляем незакрашенными.Теперь применим второй цвет, например красный. Закраску этим цветом начнемс вершины ВС. Вершину BD можно закрасить красным цветом, вершину DA — нельзя, так как есть ребро между вершинами BD и DA. Продолжаем перебор вершин:вершину DB нельзя закрасить красным цветом, вершина DC уже закрашена синимцветом, а вершину ЕА можно закрасить красным.
Остальные незакрашенные вершины имеют общие ребра с вершинами, окрашенными в красный цвет, поэтому к нимнельзя применить этот цвет.Рассмотрим незакрашенные вершины DA, DB, ЕВ и ЕС. Если вершину DA мызакрасим в зеленый цвет, то в этот цвет также можно закрасить и вершину DB,но вершины ЕВ и ЕС в зеленый цвет закрасить нельзя. К последним двум вершинам применим четвертый цвет, скажем, желтый. Назначенные вершинам цвета приведены в табл.
1.2. В этой таблице "дополнительные" повороты совместимы с соответствующими поворотами из столбца "Повороты", хотя алгоритмомони окрашены в разные цвета. При задании режимов работы светофоров, основанных на одном из цветов раскраски, вполне безопасно включить в эти режимыи дополнительные повороты.Данный алгоритм не всегда использует минимально возможное число цветов.Можно использовать результаты из общей теории графов для оценки качества полученного решения. В теории графов k-кликой называется множество из k вершин, вкотором каждая пара вершин соединена ребром. Очевидно, что для закраски fe-кликинеобходимо k цветов, поскольку в клике никакие две вершины не могут иметь одинаковый цвет.1.1.
ОТ ЗАДАЧИ К ПРОГРАММЕ•19-Таблица 1.2. Раскраска графа, представленного на рис. 1.2j:„.,• „ - . • „ •.''ЦветПоворотыСиний . , - .Красный :'Зеленый•rfR ;•:>.; iH;j s w '.1111ЖелтыйAB, AC, AD, BA, DC, ED"«'ЪДополнительные поворотыBC, BD, EAAA, ОС, EDDA,DBEB,ECAD, BA, DC, ED(„,;",BA, DC.EA, ED!;'}B графе рис. 1»2 множество из четырех вершин AC, DA, BD и ЕВ является 4кликой. Поэтому... ше существует раскраски этого графа тремя и менее цветами, и,следовательно, (решение; -представленное в табл. 1.2У является оптимальным в томсмысле, что иснольаует; минимально возможное количество цветов для раскраскиграфа.
В терминах исходной задачи это означает, что для управления перекрестком,доказанным на рис; 1.1, необходимо не менее четырех режимов работы светофоров../;• .Итак, для управления перекрестком построены четыре режима работы светофорами, которые'соответствуют четырем цветам раскраски графа (табл. 1.2). ППсевдоязык и пошаговая „кристаллизация" алгоритмов,у.~. Поскольку для решения исходной задачи мы применяем некую математическуюмодель, то:тем самым мржно формализовать алгоритм решения в терминах этой модели^ В начальных версиях алгоритма часто применяются обобщенные операторы,которые затем переопределяются в виде более мелких, четко определенных инструкций. Например, при описании рассмотренного выше алгоритма раскраски графа мыиспользовали такие выражения, как "выбрать произвольную незакрашенную вершину".
Мы надеемся, что читателю совершенно ясно, как надо понимать такие инструкции. Но для преобразования таких неформальных алгоритмов в компьютерныепрограммы необходимо пройти через несколько этапов формализации (этот процессможно назвать пошаговой кристаллизацией), пока мы не получим программу, полностью состоящую из формальных операторов языка программирования.Пример 1.2. Рассмотрим процесс преобразования "жадного" алгоритма раскраскиграфа в программу на языке Pascal.
Мы предполагаем, что есть граф G, вершины которого необходимо раскрасить. Программа greedy (жадный) определяет множество вершин, названное newclr (новый цвет), все вершины которого можно окрасить в новыйцвет. Эта программа будет вызываться на повторное выполнение столько раз, скольконеобходимо для закраски всех вершин исходного графа.
В самом первом грубом приближении программа greedy на псевдоязыке показана в следующем листинге.Листинг 1.1. Первое приближение программы greedyprocedure greedy ( var G: GRAPH; var newclr: SET ) ; P! » . . - : . ; . .{ greedy-присваивает переменной newclr множество вершин • «-.-.,; ;;.;;, -графа -G, которые можно окрасить в один цвет)• begin;!---, з• ;. ,)(1)>ат.';-> ••••:•• с newclr := 01; '(2);: Г'.г „for :дпя Каждой незакрашенной вершины v из G do(3) ; .-- -( ;if v не соединена с вершинами из ле&/с.1г then beginЙ:)пометить v цветом;(5)добавить v в newclr:>e n dend; { greedy }Символ 0 ^стандартное обозначение пустого множества.ГЛАВА 1.
ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ\В листинге 1.1 вы легко выделите средства нашего псевдоязыка. Мы применяемполужирное начертание для зарезервированных ключевых слов языка Pascal, которые имеют тот же смысл, что и в стандартном языке Pascal. Написание строчными1буквами таких слов, как GRAPH (Граф) и SET (Множество), указывает на имена абстрактных типов данных. Их можно определить с помощью объявления типовязыка Pascal и операторов, соответствующих абстрактным типам данных, которыезадаются посредством процедур языка Pascal (эти процедуры должны входить вокончательный вариант программы). Более детально абстрактные типы данных мырассмотрим в следующих двух разделах этой главы.Управляющие конструкции языка Pascal, такие как if, for и while, могут применяться в операторах псевдоязыка, но условные выражения в них (как в строке (3))могут быть неформальными, в отличие от строгих логических выражений Pascal.Также и в строке (1) в правой части оператора присваивания применяется неформальный символ.
Еще отметим, что оператор цикла for в строке (2) проводит повторные вычисления по элементам множества.Чтобы стать исполняемой, программа на псевдоязыке должна быть преобразована впрограмму на языке Pascal. В данном случае мы не будем приводить все этапы такогопреобразования, а покажем только пример преобразования оператора if (строка (3)) вболее традиционный код.Чтобы определить, имеет ли вершина и соединение с какой-либо вершиной изnewclr, мы рассмотрим каждый элемент w из newclr и по графу G проверим, существует ли ребро между вершинами v и w. Для этого используем новую булеву переменнуюfound (поиск), которая будет принимать значение true (истина), если такое ребро существует. Листинг 1.2 показывает частично преобразованную программу листинга 1.1.Листинг 1.2.
Частично преобразованная программа greedyprocedure greedy ( var G: GRAPH; var newclr: SET ) ;begin(1)newclr:= 0;(2)for для каждой незакрашенной вершины v из G do begin(3.1)found:= false;(3.2)for для каждой вершины w из newclr do(3.3)if существует ребро между v и w then(3.4)found:= true;(3.5)if found = false then begin{ v не соединена ни с одной вершиной из newclr }(4)пометить v цветом;(5)добавить v в newclrendendend; { greedy }Обратите внимание, что наш алгоритм работает с двумя множествами вершин.Внешний цикл (строки (2) - (5)) выполняется над множеством незакрашенных вершин графа G. Внутренний цикл (строки (3.2) - (3.4)) работает с текущим множеством вершин newclr. Оператор строки (5) добавляет новые вершины в это множество.Существуют различные способы представления множеств в языках программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
