1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

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

Пусть У = (у„..., у,). Рассмотрим некоторое ребро графа (ум уз)~И'. По условию задачи оно должно изображать несовместимость двух областей действия у» и уп Отношение несовместимости требует непустоты множества гл. з. алгогитмнзлция Л(У~) () П(Уп) 0 Т(Уг) Й Л(У~) 0 Л(У~) П Т(Уп). Придумать фрагмент операторной схемы, который обеспечивал бы непустоту такого множества, нетрудно.

Важно, однако, сделать это как можно проще, единообразно, а главное, так, чтобы в результирующей операторной схеме построенные фрагменты не мешали бы друг другу и не создали бы какие-то производные неконтролируемые несовместимости, не предусмотренные в исходном графе Т. По принципу экономии мьпнления естественнее всего создать несовместимость, введя в схему оператор Я с двумя результатами, одному из которых сопоставляется величина лм а другому лт (тем самым у нас сразу появляется память Х = х„..., л, — по одной величине х1 на каждую требуемую область действия у;). Заметим, что при таком построении в схеме для каждой области действия у, окажется столько операторов ~гу, со сколькими другими вершинами уп смежна вершина у,, или, выражаясь языком теории графов, скольким ребрам'инцидентна вершина ум Если у; — изолированная вершина графа Т, для нее нужно все равно завести область действия, но не связанную ни с какой другой.

Для этого достаточно заиметь оператор ~г с одним результатом ам От каждого оператора ~ц-должны вести дуги, приводящие в конце концов на какие-то операторы, воспринимающие х~ и лп При этом важно, чтобы все результаты, которым сопоставлен лм попали бы в одну компоненту связности информационного графа. Опять-таки этого проще всего добиться, заведя для каждой'у; по одному оператору уг с одним аргументом, которому сопоставляется величина хм Поскольку, как нам кажется, введя операторы ~Ц, мы улпе Рсдрп зппп Т Упппапп3анные 5сршпны г~афп " '7-%'-"- ' рис.

3.5. Любой неервеигированнмй граф Т может омть графом несовмести- мости. обеспечили несовместимость, у нас нет необходимости вводить в схему транзитные операторы, а сразу провести дуги от оператора ~ц к операторам ф и уу. В результате у нас получается конфигурация, изображенная на рис. 3.5. Формально, это уже вполне правильная операторная схема, хотя и не имеющая привычных— % 33. РАСКРАСКА ВЕРШИН ГРАФА.ОБШЕЕ ИССЛЕДОВАНИЕ одного входного н одного выходного — операторов.

Правда„ пристроить их ничего не стоит, что и показано на примере, конкретизирующем наше построение на рис. 3.6. Строго говоря, наше построение требует обратного рассуждения, доказывающего его правильность, однако автор надеется, что читатель сможег это сделать самостоятельно. Рнс. 3.6.

Пример построения операторной схемы вс заданному графу весов- местимсств. а) Граф. с) Схема. Оценки сложности алгоритмов. Снова столкнувшись с необходимостью рассматривать задачу раскраски вершин графа в ее полной всеобщности в поисках более аффективного алгоритма нахождения минимальной раскраски, мы должны установить себе определенные рамки этого поиска. Поясним, чтб мы имеем в виду. Мы установили, что для решения задачи «в лоб» нам нужно построить и раскрасок и на каждую раскраску потратить еще какое-то количество операций, чтобы определить ее правильность и подсчитать число использованных красок.

Это количество операций будет заведомо не более высокого порядка, чем па. Таким образом, общее количество «элементарных» операций при полном переборе будет порядка пап), если считать элементарной операцией простую манипуляцию с одной вершиной или одним ребром графа е). (Заметим, что множитель яа перед и! почти ничего не значит по сравнению с и), так как и) Х и Х п ~ (и+ 2)): можно сказать, что этот множитель равносилен построению раскрасок для графа, содержащего на две вершины больше, чем исходный.) е) Ниже мы поговорим об «алемевтарвых» операциях белее подробно.

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

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

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

За два шага, т. е. выполняя две операции, мы можем реализовать, как показано, функцию не более чем трех переменных (если же мы подставим в четыре возможных аргумента двух операций четыре независимые переменные, то мы не сможем связать друг с другом зги операции: рис. 3.7, б)). Выполняя три шага, мы можем реализовать функцию четырех переменных, при этом двумя способами, как показано на рис. 3.7, в). Мы выберем вариант симметричного каскада, так как он сразу' подсказывает общее построение й-ярусного дерева информационных свявей, обеспечивающего вычисление функции 2х переменных не менее, чем аа 1+ 2 -(-...

+ 2а '+ 2ь-'= = 2" — 1 шагов (рнс. 3.7, г)). Уже этот почти тривиальный результат дает нам некоторый намек на возможный источник высокой сложности алгоритма поиска минимальной раскраски: если у нас нет другой возможности выявить минимальную раскраску графа из и вершин, как сравнив ее с е" другими раскрасками, нам для этого придется выполнить не менее е" операций, даже если считать сравнение двух раскрасок за одну операцию. % а.з. РАскРАскА ВВРшин ГРАФА. евшее исследоВАште $)7 Итак, мы пришли к печальному итогу, что точное решение задачи о минимальной раскраске вершин графа не может быть получено иначе как «полным перебором», т.

е. за число шагов, сравнимое с общим количеством всех возможных правильных раскрасок. Термин «полный перебор» используется в свяаи с тем, что для данной задачи, как и для многих других комбинаторных задач, ее формулировка может быть сведена к следующей общей 6айинюг Фяаг 2"'аоа нан. (о-2»~ючн. аА б югеааию сг жуюсюоа)уг 2 аннан«на Й аРзуненпа) у оперная Р ааагпеною) г) Рис. 3.7. Каскадная реализация фуииции 2» переменных. а] Одна операция. 6! Две операции. н) Три операции. г) Общая конструкция. проблеме: дано некоторое конечное множество (в данном случае множество всех раскрасок), найти в нем некоторый элемент с заданным свойством (в данном случае минимальную раскраску).

Задача реигается полным перебором, если для нахождения требуемого элемента надо затратить число шагов, сравнимое с мощностью множества. Задача о сечениях. Не надо думать, что все комбинаторные задачи обладают таким неприятным свойством, как требовать полного перебора. У автора в запасе есть хорошая задача, имеющая. гл. з.ллгогитмиздция 118 кстати, прямое отношение к общей проблеме, обсуждаемой в первой части книги. Вернемся к обсуждению примеров 6 и 7 главы 1, в которых вычислялось х'е. Обе программы вычисляли х" по формуле (((х)~ха) Х((х))е Х (((хе)))) К ((Их))))), однако порядок вычислений был различным.

Различие порядка вычислений существенно влияло на объем требуемой памяти,, который, как мы выяснили, для линейных программ равен максимальной ширине сечения информационных связей. Освежим в памяти вид сечений в кан'дой из программ (рис. 3.8), а заодно а) е7 Ф/ Рис. 8.8. Линейная программа как упорядочеяяе дерева формулы у = „ее е) дерево формуяы. б) Неэкономяое упорядочение. в) Миняиальное упо- рядочение. изобразим информационные связи в самой формуле, получив каскадную конструкцию, аналогичную рис. 3.7, г) (для простоты будем считать вычисление 8-й, 16-й и 32-й степеней элементарными операциями).

Назовем конструкцию, изображающую формулу, каскадным информационным графом. Он отличается от обычного информационного графа тем, что на нем, кроме полюсов и информационных связей, изображены операторы и указано соответствие полюсов операторам (отображение К в определении, операторной схемы). Будем рассматривать операторы как вершины каскадного инфбрмационного графа. Тогда этот ориентированный граф яв- 3 3.3.

РАСКРАСКА ВЕРШИН ГРАФА ОВШЕЕ ИССЛЕДОВАНИЕ 419 ляется графом особого вида, называемого деревом. Он имеет одну вершину, не нмеющу3о исходящей дуги и называемую корнем дерева. Он имеет также серию висячих вершин, не имеющих входящих дуг. Все вершины, кроме корня, имеют по одной исходящей дуге. Наконец, для каждой висячей вершины есть один и только один путь к корню. Этн три свойства полностью характеризуют графы, являющиеся деревом в). Взяв вместе с каждой вершиной п дерева ее обратное транзитизное аамыкание, получим подграф Т(и), который тоже является деревом с корнем Р.

Характеристики

Список файлов книги