По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
0 - - - - 1 0 - - - 2 1 0 - - 1 0 1 0 - 2 1 2 1 Еще пример 0 - - - - - - 1 0 - - - - - 2 1 0 - - - - 3 2 1 0 - - - 2 1 2 1 0 - - 1 2 3 2 1 0 - 2 3 4 3 2 1 0 Естественно, что хранить в памяти компьютера всю матрицу не следует. Достаточно одномерных массивов. 32. Двое играют в следующую игру: они разложили одноко- пеечные монетки в стопки (в разных стопках может быть раз- личное количество монет), а стопки расположили в ряд слева направо на столе перед собой. Затем игроки по очереди делают ходы. На каждом ходе участник берет слева несколько стопок (не меньше одной), но не больше, чем перед этим взял его про- тивник (первый игрок своим первым ходом берет не более стопок). Игра заканчивается, когда стопок не осталось. Требу- ется вычислить, какое максимальное число монет может запо- лучить первый игрок, если второй тоже старается ходить так, чтобы получить как можно больше. Входные данные. Во входном файле input.txt записано число стопок N (l и в конце число ограничивающее количе- ство стопок, которые допускается брать на первом ходе Выходные данные. В выходной файл out- put.txt выводится одно число — максималь- ное количество монет, которое заведомо мо- жет заполучить первый игрок, как бы ни играл второй. Указание. Суть решения отражена в сле- дующей процедуре и выводе результата 3. Перебор и методы его сокращения 139 А[1,К], где А — Array[l..MaxN+l, Of Вы- полните трассировку процедуры и разработайте программу ре- шения задачи. Procedure Solve; Var i , j : Integer; sum: Begin For DownTo 1 Do Begin + ; For j:=l К Do Begin A[i, If Then j] j ] , sum - A[i+j, функция определения максимального из двух чисел. *} End; End; End; 33. Задача о магических квадратах. В квадратной таблице записать числа 1, 2, 3, ..., N*N так, чтобы суммы по всем столбцам, строкам и главным диагоналям были одинаковы. Примеры магических квадратов. 2 9 4 7 5 3 6 1 8. 8 3 4 1 5 9 1 12 13 8 2 14 7 11 15 3 10 6 16 5 4 9 Указание. Задача имеет решение лишь для Сумма всех чисел квадрата равна Таким образом, искомая сумма равна )/2. Чудовищный алгоритм решения: вы- тягиваем квадрат в линейку, генерируем все перестановки чи- сел 1, 2, 3, ..., N*N и проверяем каждую перестановку на пред- мет её пригодности требованиям магичности квадрата. Не используется даже факт знания значения суммы чисел. Из 9! перестановок при только 8 перестановок удовлетворяют условиям задачи, а из - 7040 перестано- 140 3. Перебор и методы его сокращения Проверьте свой компьютер на выживаемость при Во время его счета оцените вручную временные затраты алгоритма (допускается прибавить к производительности вашего компью- тера несколько миллионов операций в секунду). После этого (при условии, что глава вами проработана достаточно тщатель- но) с помощью ряда эвристик, сокращающих перебор, вы быст- ро напишете новый вариант алгоритма и получите все решения при О дальнейшем продвижении в сторону увеличения значения iV позвольте умолчать. 4. Алгоритмы на графах Данная глава посвящена алгоритмам на графах, точнее при- кладным аспектам этой темы. Если при изложении материала избежать многочисленных дефиниций и доказательств (к чему стремился автор), то он, в силу своей наглядности и простоты, становится доступным и школьнику. Работа по этой проблема- тике значительно обогащает алгоритмическую культуру уча- щихся, совершенствует технику написания программ, так как алгоритмы являются неиссякаемым источником задач любого уровня 4.1. Представление графа в памяти компьютера Определим граф как конечное множество вершин V и набор Е неупорядоченных и упорядоченных пар вершин и обозначим Количество элементов в множествах V и Е будем обо- значать буквами N и М. Неупорядоченная пара вершин назы- вается ребром, а упорядоченная пара — дугой. Граф, содержа- щий только ребра, называется неориентированным; граф, содержащий только дуги, — ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Реб- ро и любая из его двух вершин называются инцидентными. Го- ворят, что ребро v) соединяет вершины и Каждый граф можно представить на плоскости множеством точек, соответст- вующих вершинам, которые соединены линиями, соответству- ющими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересе- каться. Способы описания. Выбор соответствующей структуры дан- ных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер. Матрица смежности — это двумерный массив размерности Алгоритмы на графах вершина с номером i смежна с вершиной с номером j вершина с номером не смежна с вершиной с номером j Для хранения перечня ребер необходим двумерный массив размерности М*2. Строка массива описывает ребро. 4.2. Поиск в графе 4.2.1. Поиск в глубину Идея метода. Поиск начинается с некоторой фиксирован- ной вершины v. Рассматривается вершина и, смежная с v. Она выбирается. Процесс повторяется с вершиной и. Если на оче- редном шаге мы работаем с вершиной q и нет вершин, смеж- ных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, ког- да это вершина процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа: : Of Boole- an. Пример. Пусть граф описан мат- рицей смежности А. Поиск начина- ется с первой вер- шины. На левом рисунке приведен исходный граф, а на правом рисун- ке у вершин в скобках указана та очередность, в которой вершины графа просматривались в процессе поиска в глубину. Логика. Procedure Nnew и А Var Begin Nnew[v]:=False; For j:=l To N Do If (A[v,j ]<>0) And Nnew[j] Then Pg (j) ; End; Фрагмент основной логики. 4. Алгоритмы на графах For i:=l To N Do If Then Pg(i) ; В силу важности данного алгоритма рассмотрим его нере- курсивную реализацию. Глобальные структуры данных преж- ние: А — матрица смежностей; Nnew — массив признаков. Но- мера просмотренных вершин графа запоминаются в стеке St, указатель стека — переменная yk. Procedure Var St:Array[l..N] Of Integer; t, Begin (St),0); yk:=0; While yk<>0 Do Begin стек не пуст. *} "самой верхней" вершины из *} Repeat If (A[t,j] <>0) And Then Else (j ) ; Until pp Or (j>=N); новая вершина или все вершины, связанные с данной вершиной, просмотрены. *} Then Begin (yk); номер вершины в стек. *} End Else Dec (yk); {*"Убираем" номер вершины из *} End; End; 4.2.2. Поиск в ширину Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины — выбирается та, кото- рая была раньше рассмотрена. Для реализации данного прин- ципа необходима структура данных очередь. 144 4. Алгоритмы на графах Пример. Исход- ный граф на левом рисунке. На правом рисунке рядом с вер- шинами в скобках указана очередность просмотра вершин графа. Приведем проце- дуру реализации данного метода обхода вершин графа. Логика просмотра вершин. Procedure Var Of *} очереди, - запись; yk2 - чтение. *} j -.Integer; Begin ,0) ; *} очередь вершину v. *} While yk2 элемент из очереди. For j : =1 N Do всех вершин, связанных с вершиной *} If (A[v,j]<>0) Then Begin {*Если вершина ранее не просмотрена, то заносим её номер в очередь. *} Inc End; End; End; 4.3. Деревья 4.3.1. Основные понятия. Стягивающие деревья Деревом называют произвольный связный неориентирован- ный граф без циклов. Его можно определить и по-другому: связный граф, содержащий вершин и N— 1 ребер. Для произ- вольного связного неориентированного графа G= 4. Алгоритмы на графах 145 остовом). Ребра такого дерева называют ветвями, а оста- льные ребра графа — хордами. Примечание Понятие цикла будет дано позже. В данной теме ограничимся его интуитивным пониманием. Число различных каркасов полного связного неориентиро- ванного помеченного графа с вершинами равно Пример. Граф и его каркасы. Поиск единственного стягивающего дерева Мето- ды просмотра вершин графа поиском в глубину и в ширину по- зволяют построить одиночный каркас. В вышеописанные про- граммы необходимо вставить запись данных по ребрам, связывающих текущую вершину с ранее не просмотренными в некую структуру данных, например, массив Tree (Ar- Of Integer). Пример. Граф и его каркасы, построенные методами поиска в глубину и в ширину. В круглых скобках указана очередность просмотра вершин графа при соответствующем поиске. 4.3.2. Порождение всех каркасов графа Дано. Связный неориентированный граф G= Все каркасы графа. Каркасы не запоминаются. Их необходимо перечислить. Для порождения очередного каркаса ранее построенные не при- влекаются, используется только последний. Множество всех каркасов графа G делится на два класса: содержащие выделен- ное ребро Каждый из графов и 146 4. Алгоритмы на графах меньше, чем G. Последовательное применение этого шага уменьшает графы до тех пор, пока не будет построен оче- редной каркас, либо графы станут несвязными и не имеющими каркасов. Для реализации идеи построения каркасов графа G исполь- зуются следующие структуры данных: • очередь — Turn Of Integer) с нижним (Down) и верхним (Up) указателями; • массив признаков • список ребер, образующих каркас, — Tree; • число ребер в строящемся каркасе — numb. Начальное значение переменных: Nnew[l]:=False; {*B очередь заносим первую *} Procedure ;{*v - номер вершины, из которой выходит q - номер вершины, начиная с которой следует искать очередное ребро каркаса . *} Var Begin If Down>=Up Then Exit; j •• While (j<=N) And Do Begin {*Просмотр ребер, выходящих из вершины с номером v.*} If (A[v,j]<>0) And Then Begin ребро, и вершины с номером j еще нет в каркасе. Включаем ребро в Nnew[j]:=False; вершину с номером j в очередь. *) {*Продолжаем построение каркаса. *} (numb); {*Исключаем ребро из каркаса. *} End; Inc(j) ; End; 4. Алгоритмы на графах 147 If numb=N-l Then Begin <вывод Exit End; {*Все ребра, выходящие из вершины с номером v, просмотрены. Переходим к следующей вершине из очереди и так до тех пока не будет построен каркас. *} If j=N+l Then Begin End; End; Логика работы процедуры достаточно сложно понимается — двойной рекурсив- ный вызов. Для этого лучше всего выпол- нить трассировку работы процедуры на ка- ком-либо примере. Рассмотрим граф, приведенный на рисунке. Первый каркас строится обычным поиском в ширину. Затем исключаем последнее ребро <4,3> и вновь строим каркас. Пер- вые каркасы, в которых есть ребра <1,4> и <1,5>, приведены на следующем рисунке. При исключении ребра <1,5> получа- ются 8 каркасов. 148 4. Алгоритмы на графах 4.3.3. Каркас минимального веса. Метод Дж. Краскала Дано. Связный неориентированный граф Ребра имеют вес. Граф описывается перечнем ребер с указанием их веса. Массив Р Div 2] Of Integer). Резу- льтат. Каркас с минимальным суммарным весом где Пример. Граф и процесс построения каркаса по методу Крас- кала. Шаг 1. Начать с графа Q, содержащего N вершин и не имею- щего ребер. Шаг 2. Упорядочить ребра графа G в порядке неубывания их весов. Шаг 3. На- чав с первого ребра в этом перечне, до- бавлять ребра в граф Q, со- блюдая усло- вие: добавле- ние не должно приводить к появлению цикла в Q. Затем наступает очередь ребра <1,4> и вновь 8 каркасов. 4. Алгоритмы графах 149 Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в Q не станет равным N-1. Получившееся дерево является каркасом минимального веса. Какие структуры данных требуются для реализации шага 3? Стандартным в программировании методом является введение массива меток вершин графа Of Integer). Начальные значения элементов массива равны номерам соот- ветствующих вершин для i от 1 до N). Ребро выби- рается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. В этом случае циклы не образу- ются. Для примера, приведенного выше, процесс изменения Mark показан в таблице. Номер итерации Начальное значение 1 2 3 4 Ребро - <1,4> <4,5> <2,5> Значения элементов [1,2,3,4,5] [1,2,3,1,5] [1,2,3,1,1] [1,2,2,1,1] И логика этого фрагмента. Procedure Mark глобальный. *} Var Begin If m End; For i:=l To N Do If Then Mark [i] End; Фрагмент основной части логики. Program Tree; Const Var P:Array[1..3,l..N*(N-l) Div 2] Of Integer; Of Integer; ребер графа. *} Begin <ввод описания графа - массив Р>; <сортировка массива Р по значениям весов ребер>; For i =2 N Do Mark [i ] : =i ; While k i : =1 150 4. Алгоритмы на графах While And And (P[l,i]<>0) Do Inc(i) ; Inc(k) ; ребра каркаса>; ,i]]); End; End; 4.3.4. Каркас минимального веса. Метод Р. Прима Дано. Связный неориентированный граф Ребра имеют вес. Граф описывается матрицей смежности A (Ar- ray [ 1 Of Integer). Элемент матрицы, не равный нулю, определяет вес ребра. Результат. Каркас с минимальным сум- марным весом где Отличие от метода Краскала заключается в том, что на каж- дом шаге строится дерево, а не ациклический граф, т. е. добав- ляется ребро с минимальным весом, одна вершина которого принадлежит каркасу, а другая нет. Такой принцип «добавле- ния» исключает возможность появления циклов. Для реализа- ции метода необходимы две величины множественного типа SM и SP (Set Of 1..N). Первона- чально значением являют- ся все вершины графа, a SP пу- сто. Если ребро включается в Т, то один из но- меров вершин i и исключает- ся из SM и добавляется в SP (кроме первого шага, на кото- ром оба номера переносятся в SP). Пример. Граф и его каркас. 4. Алгоритмы на графах 151 Логика построения каркаса. Procedure Tree; { *А - глобальная данных. *} Var SM,SP:Set Of 1..N; Begin первое в каркас. *} For Do For To N Do If And (A[i,j]<>0) Then Begin End; <выводим или запоминаем ребро <1, t » ; *} While SM<>[] Do Begin For To N Do If Not (i In SP) Then For To N Do If (j In SP) And (A[i,j] Then Begin =SM- <выводим или запоминаем ребро End; End; 4.4. Связность 4.4.1. Достижимость Путем (или ориентированным маршрутом) ориентированно- го графа называется последовательность дуг, в которой конеч- ная вершина всякой дуги, отличной от последней, является на- чальной вершиной следующей. Простой путь — это путь, в котором каждая дуга используется не более одного раза. Эле- 152 4. Алгоритмы на графах ментарный путь — это путь, в котором каждая вершина испо- льзуется не более одного раза. Если существует путь из верши- ны графа v в вершину и, то говорят, что достижима из v. Матрицу достижимостей R определим следующим образом: Множество R(v) — это множество та- ких вершин графа G, каждая из кото- рых может быть достигнута из вершины v. Обозначим через множество та- ких вершин графа G, которые достижи- мы из с использованием путей длины 1. — это т. е. с использо- ванием путей длины 2 и так далее. В этом случае: При этом р — некоторое конечное значение, возможно, до- статочно большое. Пример (для рисунка). Выполняя эти действия для каждой вершины графа, мы полу- чаем матрицу достижимостей R. Procedure Reach; матрицы R, глобальной переменной. Исходные данные - матрица смежности А, глобальная *} Var S,T:Set Of 1. Begin FillChar (R) ,0) ; For i:=l To N Do Begin из вершины с номером i . *} T: [i] ; Repeat For To N Do If 1 In S Then{ *По строкам матрицы А, принадлежащим множеству S. *} For N Do If Then T:=T+[j]; Until { *Если Т не изменилось, то найдены все вершины графа, достижимые из вершины с номером 4. Алгоритмы на графах 153 F o r j :=1 N Do If j In T Then End; End; Матрицу контрдостижимостей определим следующим об- разом: Дополнения. 1. Граф называется транзитивным, если из существования дуг (v,u) и следует существование дуги (v,t). Транзитивным замыканием графа является граф где Е' — минимально возможное множество дуг, необходимых для того, чтобы граф был транзитивным. Разработать программу для нахождения транзитивного замыкания произвольного гра- фа G. 2. R(v) — множество вершин, достижимых из v, a — множество вершин, из которых можно ДОСТИГНУТЬ и. Опреде- лить, что представляет из себя множество Разрабо- тать программу нахождения этого типа множеств. 4.4.2. Определение связности Определения. Неориентированный граф G связен, если суще- ствует хотя бы один путь в G между каждой парой вершин i и j. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один ориентированный путь из i в и по крайней мере один из Множеством графа G является множество таких вер- шин, что из любой его вершины можно достигнуть вершины Из определения следует, что столбец v матрицы Q совпадает со строкой v матрицы R, т. е. где — матрица, транспони- рованная к матрице достижимостей R. Для примера на рисунке матрицы A, R и имеют вид: 154 4. Алгоритмы на графах в i. Максимальный связный подграф графа G называется связ- ной компонентой графа G. Максимальный сильно связный под- граф называется сильно связной компонентой. Рассмотрим алгоритм нахождения сильно связных компо- нент графа. Идея достаточна проста. Для вышеприведенного примера значение а Пересечение этих множеств дает множе- ство вершин графа G, образующих сильную ком- поненту, которой принадлежит вершина графа с номером 1. Продолжим рассмотрение: и Итак, мы нашли сильные компоненты графа G. Граф определим так: каждая его вершина представляет множество вершин некоторой си- льной компоненты графа G, дуга j*) существует в G* тогда и только тогда, когда в G существует дуга такая, что при- надлежит компоненте, соответствующей вершине i*, j — ком- поненте, соответствующей вершине j * . Граф G* называется конденсацией графа G. Некоторые факты по изложенному ма- териалу. G* не содержит циклов. В ориентированном графе каждая вершина i может принадлежать только одной сильной компоненте. В графе есть множество вершин Р, из которых до- стижима любая вершина графа и которое является минималь- ным в том смысле, что не существует подмножества в Р, обла- дающего таким свойством достижимости. Это множество вершин называется базой графа. В Р нет двух вершин, которые принадлежат одной и той же сильной компоненте графа G. Лю- бые две базы графа G имеют одно и то же число вершин. Разработать программу нахождения базы графа. Схема ре- шения. База конденсации графа G состоит из таких вер- шин графа в которые не заходят ребра. Следовательно, базы графа G можно строить так: из каждой сильной компонен- ты графа G, соответствующей вершине базы Р* G*, надо взять по одной вершине — это и будет базой графа G. 4.4.3. Двусвязность Иногда недостаточно знать, что граф связен. Может возник- нуть вопрос, насколько «сильно связен» связный граф. Напри- мер, в графе может существовать вершина, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения, или разделяющей вершиной. Граф, содержащий точку сочленения, 4. Алгоритмы на графах 155 называется разделимым. Граф без точек сочленения называет- ся двусвязным, или неразделимым. Максимальный двусвяз- ный подграф графа называется компонентой, или Пример. Разделимый граф и его двусвязные компоненты. Точки сочленения вершины с номерами 4, 5 и 7. Точку сочленения можно определить иначе. Вершина t яв- ляется точкой сочленения, если существуют вершины и от- личные от t, такие, что каждый путь из в (предполагаем, что существует по крайней мере один) проходит через вершину с номером t. Наша задача — найти точки сочленения и двусвязные ком- поненты графа. Основная идея. Есть двусвязные компоненты и и точки сочле- нения 1, 2, 3. Осуществляем поиск в глубину из вершины t, принад- лежащей Мы можем перейти из в проходя через вершину 1. Но по свойству поиска в глуби- ну все ребра должны быть пройдены до того, как мы вернем- ся в Поэтому в сти из ребер, которые проходятся между заходами в вершину 1. Для других чуть сложнее. Из попа- даем в затем в и Преды- сторию процесса прохождения ре- бер будем хранить в стеке. Тогда при возвращении в из через вершину 3 все ребра будут на верху стека. После их удаления, т. е. вывода двусвязной компоненты из стека, на вер- ху стека будут ребра и в момент прохождения вершины 2 мы можем их опять вывести. Таким образом, если распознать точки сочленения, то, применяя поиск в глубину и храня ребра в стеке в той очередности, в какой они проходятся, можно 156 Алгоритмы на графах определить двусвязные компоненты. Ребра, находящиеся на верху стека в момент обратного прохода через точ- ку сочленения, образуют двусвязную компоненту. Итак, проблема с точками сочле- нения. Рассмотрим граф. В процессе просмотра в глубину все ребра разби- ваются на те, которые составляют де- рево (каркас), и множество обратных ребер. Обратные ребра выделены на рисунке более жирными Что нам это дает? Пусть очередность просмотра вершин в процессе поиска в глубину фиксируется метками в массиве Num. Для нашего примера Num — (1,2,3,4,5,6,7,9,8). Если мы рассматриваем обратное ребро (v,u), и не предок и, то инфор- мацию о том, что Num[v] больше Num[u], можно использо- вать для пометки вершин v и и как вершин, принадлежащих одной компоненте двусвязности. Массив Num использовать для этих целей нельзя, поэтому введем другой массив и по- стараемся пометить вершины графа, принадлежащие одной компоненте двусвязности, одним значением метки в этом мас- сиве. Первоначальное значение метки совпадает со значением соответствующего элемента массива Num. При нахождении об- ратного ребра (v,u) естественной выглядит операция: — изменения значения метки вершины v, так как вершины одной компоненты двусвязности. К этой логике необходимо добавить смену значе- ния метки у вершины v ребра на выходе из просмотра в глубину в том случае, если значение метки вершины и меньше, чем метка вершины v Для нашего примера массив меток Lowpg имеет вид: (1,1,1,2,4,4,4,9,8). Осталось определить момент вывода компо- ненты двусвязности. Мы рассматриваем ребро и оказыва- ется, что значение больше или равно значению Num[v]. Это говорит о том, что при просмотре в глубину меж- ду вершинами v и и не было обратных ребер. Вершина v — точ- ка сочленения, и необходимо вывести очередную компоненту двусвязности, начинающуюся с вершины Итак, логика. Procedure p - предок вершины v. Массивы A, Num, Lowpg и переменная пт - глобальные.*} |