1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 34
Текст из файла (страница 34)
Получение графа несовместимости дрим ПОЛУЧЕНИЕ ГРАФА НЕСОВМЕСТИМОСТИ /(3) и, С, р, а, ]/, У, ЬК, П/. Согласно э 3.2 заключительным материалом для прямого определения несовместимости двух областей действии д и а являются множества В(д), В(д'), Т(г]) и Т(Й'), где В(д) — множество операторов, вырабатывающих величину х, сопоставленную области И, а Т(г]) — множество транзитных операторов всех маршрутов всех информационных пар, реализуемых величиной х (напомним, что сейчас мы имеем дело с каноническим распределением памяти). Т(гУ) в свою очередь получается пересечением двух множеств Е (А) и Ь (А), где Е (Н) — транзитивный образ множества В (И), ограниченный им же, а Ь Щ вЂ” транзитивный прообраз множества АЩ операторов, воспринимающих величину х, при этом сильно ограниченный множеством В(д).
Накомнпв эти факты, мы заодно перечислили основные внутренние объекты, возникающие при построении графа несовместимости. Поскольку отношение несовместимости должно быть вычислено попарно длв всех величин,.правда, с учетом симметрии, нам перед вычислением матрицы П нужно иметь В и Т для всех У величин. Поскольку пан~две множество — эго шкала длины и, мы приходим к описанию этих множеств в виде матриц цел массив В, Т(1: У, 1: и), а так~не получаем естественное структурирование задачи.
Итак (49) ПОЛУЧЕНИЕ ГРАФА НЕСОВМЕСТИМОСТИ: (цел массив В, Т]1: У, 1: и]; ВБ1ЧИСЛЕНИЕ В и Т /55/; ВБ1ЧИСЛЕНИЕ П) примВЫЧИСЛЕНИЕ 0 /и, У, П, В, Т/аналогично вычислению суммы трех произведений матриц: 0 = В' Х В -ф. В' Х Х Т + Т' Х В, где штрих означает транспонироваиив 4 «ль и олучение ГРАФА несовместимости 161 матрицы. Напомним, что элемент (4, Я матрицы произведения матрицы А на матрицу В равен скалярному произведению 4-й строки матрицы А на у-й столбец матрицы В, т. е.
сумме по- парных произведений их компонент. Так как нам нужно вычислить сумму трех произведений, в цикле суммирования мы можем складывать сразу три попарных произведения компонент нужных комбинаций строк н столбцов матриц Н н Т. Наконец, хотя нам нужна матрица «У, состоящая из нулей и единиц, мы можем заменить логические умножения и сложения арифметическими, нормализовав. впоследствии вычисленный элемент матрицы ХХ, заменяя любое его ненулевое значение на единицу.
Ко всему этому напомним, что мы будем вычислять фактически только «верхний треугольнике матрицы П, засылая вычисленный элемент ХУ как в позицию (у, у), так и в позицию (у, 4), и без вычислений полагая диагональные элементы матриц равными нулю. Итак (50) ВБ1ЧИСЛЕНИЕ ХУ: (ДИАГОНАЛЬНЫЕ ЭЛЕМЕНТБ1; ОСТАЛЬНБ1Е ЭЛЕМЕНТБ1 /52/) (51) ДЦ~ГОНАЛЬНБ1Е ЭЛЕМЕНТБ/: (цел 4; для й = 1 «паг 1 до У цикл 1/(Ь 4): = 0) (52) ОСТАЛБНЫЕ ЭЛЕМЕНТБ1: (цел 4; для 4': = 1 шаг 1 Ло У вЂ” 1 цикл (цел у; для у: = 4 + 1 шаг 1 до 1 цикл ВБ1ЧИСЛЕНХХЕ И ПОСТАНОВКА ) ) (53) ВБ1ЧИСЛЕНИЕ ХХ ПОСТАНОВКА: (цел и; ВЫЧИСЛЕНИЕ ЭЛЕМЕНТА; ХУ!Ь у): = (/[У, 4): = если и = Ото 0 иначе 1) (54) ВБ1ЧИСЛЕНИЕ. ЭЛЕМЕНТА: (и: = 0; (цел й; для Ук = 1 шаг 1 до и цикл и: = — и + Н!4, у«) Х Н(у, у«) + Н(у, у«) Х Т(у, Ь)+ Т(4, Ь) х Н(у, Ь))) прим ВЫЧИСЛЕНИЕ Н И Т /(49) и, С, р, д, У, 1, ЬК, Н, Т/.
Это вычисление мы будем вести по очереди для всех величин канонического распределения памяти. Итак (55) ВЫЧИСЛЕНИЕ Н И Т: (цел 4; для О = 1 шаг 1 до 1 цикл ОБРАБОТКА ОЧЕРЕДНОЙ ОБЛАСТИ) прим ОБРАБОТКА ОЧЕРЕДНОЙ ОБЛАСТИ /и, С, р, о, У, БК, Н, Т, 4/. Следуя комментарию к (49), получение Н(4)) предшествует получению Т(«У). Итак (50) ОБРАБОТКА ОЧЕРЕДНОЙ ОБЛАСТИ: (ПОЛУЧЕНИЕ Н; ПОЛУЧЕНИЕ Т /60/) прим ПОЛУЧЕНХХЬ' Н /и, р, д, У, ЬК, Я, 4/ представляет собой просмотр результатной части распределения памяти ЬК. При обнаружении в (р + у)-й позиции величины 4 направ- 163 ' гл. «.
Реализация ляется единица в р[р + у ]-ю компоненту [-й строки матрнцьг В. Перед просмотром 1-я строка «обнуляется». Итак (57) ПОЛУЧЕНИЕ В: [ОБНУЛЕНИЕ; ПРОСМОТР РЕЗУЛБТА ТОВ /59/) (58) ОБНУЛЕНИЕ /и, В, [/: (цел у; для у: = 1 шаг 1 до и цикл В[у, у1: = 0'; (59) ПРОСМОТР РЕЗУЛЬТАТОВ /(57) р, д, У, ЬК, В, В: (цел у; для у: = — 1 шаг 1 до о цикл если БК[р + у ) = 1 то ВП„ У[р -у- у11: =- 1) прим ПОЛУЧЕНИЕ Т /(56) п, С, р, Р, ЬК, В, Т, 1/ требует вычисления множеств Е и Х, которые, пересекаясь, дадут множество Т.
Итак (60) ПОЛУЧЕНИЕ Т: (цел массив Е, Б[1: п1; ВЫЧИСЛЕНИЕ Е И Ь /62/; ПЕРЕСЕЧЕНИЕ) (61) ПЕРЕСЕЧЕНИЕ /п, Т, [ Е, Б/: (цел у; для у: = 1 шаг 1 до и цикл Т[у, |1: = Е[у) х А[у)) (62) ВБ|ЧИСЛЕНИЕ Е |Х Ь /60/: (ВБ|ЧИСЛЕНИЕ Е; ВБ|ЧИСЛЕНИЕ Ь /69/) прям ВБ|ЧИСЛЕНИЕ Е /и, С, В, у, Е/ становится стандартной задачей нахождения транантивного ограниченного образа. Нам необходимо только ввести стартовое множество 3 с его. начальным значением, равным В, н задать начальное пустое аначение пополняемого множества Е.
Итак (63) ВЫЧИСЛЕНИЕ Е: (цел массне 8[1: и'1; ИНИЦИАЛИЗАЦ|ХЯ; ДВИЖЕНИЕ ПО ДУГАМ /65/) (64) ИНИЦИАЛИЗАЦИЯ /п, В, У, 3, Е/: (цел у; длп у: = 1 шаг 1 до п цикл (З[у]: = В[у, |1; Е)у] = 0)) прим ДВИЖЕНИЕ ПО ДУГАМ /(63) п, С, В, у, Е, 3/аналогично шагу (22) при построении канонического распределения памяти. Итак (65) ДВИЖЕНИЕ ПО ДУГАМ: (цел у; у: = 0; для у: = у + 1 пока НЕПУСТО (3, п) цикл ДВИЖЕНИЕ) (66) ДВИЖЕНИЕ /п, С, В, у, Е, 3/: (цел массив ГН: п); НАХОЖДЕНИЕ Г; ИСПОЛЬЗОВАНИЕ Г/68/) прим НАХОЖДЕНИЕГ/п, С, 3, Г/.
В качестве демонстрации. принципа экономии мышления мы перепишем в собранном виде формулы (29 — 34), репшющие такую же задачу. Итак (67) НАХОЖДЕНИЕ Г: ((цел й для У: = — 1 шаг 1 до и цикл Г)11: = 0); (цел у; для»: == 1 шаг 1 до п цикл если 8[1] ~ 0 $ аб. Получении ГРАФА несовместимости 163 то (цел /; для /: = 1 шаг 1 до п цикл если С[1„ /1 = 1! то Г[/1 = 1))) прим ИСПОЛБЗОВАНИЕ Г /(66) п, В, !, Е, 3, Г/ производится аналогично (35 — 39), за исключением того, что согласование отсутствует. Итак (68) ИСПОЛЬЗОВАНИЕ Г: (цел /; дая В = 1 шаг 1 до и цикл (ПЕРЕСЧЕТ СТАРТОВОГО: если Г[/1 = 0 то 3[/]: = 0 иначе если Е[/] Ф 0 !/ В [!, /] Ф 0 то 3 ]/1: = 0 иначе 3 1/1: = 1; ДОБАВЛЕНИЕ К ПОПОЛНЯЕМОМУ: если Г[/'1 ~ 0 то Е]/']: = 1)) прим ВЫЧИСЛЕНИЕ Ь /(62) и, С, р, г', ЬК, В, /, Ы является задачей вычисления сильно ограниченного транзитивного прообраза.
В качестве начального значения стартового множества берется мяожество А аргументов, которым в ЬК со- ~ поставлена величина !. Начальное значение пополняемого множества Б — пустое. Сильно ограничивающим множеством является !-я строка матрицы В. Итак (69) ВБ/ЧИСЛЕНИЕ Ь: (цел массив А [1: и); ((цел П для 1: = 1 шаг 1 до п цикл А[11: = Б[!1: = — О); НАХОЖДЕНИЕ А); ДВИЖЕНИЕ НАВСТРЕЧУ ДУГАМ /71/) прим НАХОЖДЕНИЕ А /р, У, ЬК, !, А/ производится движением'вдоль аргументной части распределения памяти ЬК[1: р]. Обнаруживая в /-й компоненте величину !, мы ставим единицу в Р!/ 1-ю компоненту множества А. Итак (70) НАХОЖДЕНИЕ А: (цел /; для у: = 1шаг1 до р циич если ЬК]/1 = / то А[У]/П: = 1) (71) ДВИЖЕНИЕ НАВСТРЕЧУ ДУГАМ /(69) п, С, В, 1, Ь, А/: (цел /; /: = 0; для /: = / + 1 пока НЕПУСТО (А, и) цикл ПРОДВИЖЕНИЕ) (72) ПРОДВИЖЕНИЕ /п, С, В, !, Ь, А/: (цел массив ГИ: и]; ВЫЧИСЛЕНИЕ Г; ПРЙМЕНЕНИЕ Г /74/) прим ВБ/ЧИСЛЕНИЕ Г /и, С, А, Г/.
При его вычислении надо помнить, что от элементов стартового множества мы переходим к его предшественникам, образующим столбцы матрицы С. Итак (73) ВБ/ЧИСЛЕНИЕ Г: ((цел !; для й = 1 шаг 1 до п цикл Г[11: = 0); (цел й для й = 1 шаг 1 до и цикл если А]1] ~ 0 то (цел/; для/: = 1 шаг 1 до ициклесли С[/, !1 = 1 то Г[у]:= 1И) прим ПРИМЕНЕНИЕ Г /(72) и, В, !, Ь, А, Г/ делается так же, как и в (68), но при добавлении к пополняемому нам можно гл.
ь. гвализлпия' добавлять только такой злемент из Г, который не принадлежит ограничивающему множеству. Итак (74) ПРИМЕНЕНИЕ Г: [цел у; для у: = 1 шаг 1 до п цикл (ПЕРЕСЧЕТ А: если Г[/) =- О то А[у): = О иначе если А[у) ~ О ~/ И [У,! ) чь О то АЦ): = О иначе А [у): =- 1; ДОБА ВЛЕУУИЕ К'Тл если Г[у) ~ О м Н[у, у) = О то Е[у): = 1)) в 4.6. Раскраска вершин графа прим РАСКРАСКА /(4) У, П, (У/. Прежде всего нам нужно опре- делить общую организацио алгоритма раскраски с учетом выбранных представлений для объектов и различных эвристик, предлагаемых в $ 3.4 Если исходный граф полный, то тогда с ним ничего не происходит, а реаультатом является тривиальная раскраска, при которой каждая вершина графа колучает свою краску. Тогда алгоритм раскраски структурируется на задание начальной тривиальной раскраски и цикл редукции графа (склеивания вершин на расстоянии 2), который повторяется, пока граф не будет редуцирован к полному (не повторяется ни разу, если исходный граф окааался полным).
При редукции происходит коррекция раскраски Гу, состоящая в замене всех вхождений краски у на краску 1(У( Х), где У и У вЂ” краски склеиваемых вершин. Прн редуцировании исходного графа номера вершин и их краски совпадают. Это удобно, и мы позаботимся о том, чтобы зто свойство сохранялось для любого промежуточного редуцируемого графа. В то же время для организации алгоритма важно, чтобы вершины графа были бы занумерованы подряд. Это оаначает, что при склеивании вершин у и / (у ( у) все вершины, начиная с (У + 1)-й, получают на единицу меньший номер. Такая же коррекция должна делаться и в текущем состоянии раскраски ~3 исходного графа.
Теперь надо сообразить, как доля;но выглядеть условие редукции графа. По правилам алгола ато должно быть логическое выражение (истинное, если граф неполный, и ложное в противном случае). Так как кроверку такого условия невозможно записать в виде выражения, содержащего только исходные операции алгола, мы организуем логическую процедуру-функцию ГРАФ НЕПОЛНЫЙ (и), где и-число вершин в графе, и работающую с графом У как с глобальным объектом, а заодно и вырабатывающую (если граф У не полный) номера 1 и У склеиваемых вершин. Такая организацчя алгоритма тем более удобна, что процесс редукции н перекраски отделяется от способа определения пары склеиваемых вершин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
