 |
 |
 |
|
|||||||||
|
 | |||||||||||
|
 |
||||||||
|
МЕНЮ
|
БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Алгоритмы на графах. Кратчайшие расстояния на графахАлгоритмы на графах. Кратчайшие расстояния на графахМинистерство образования Республики Беларусь Учреждение образования "Гомельский государственный университет им. Ф. Скорины" Математический факультет Кафедра МПУ Алгоритмы на графах. Поиск в глубину Курсовая работа Исполнитель: Студентка группы М-43 Полякова А.Ю. Научный руководитель: Канд. физ-мат. наук, доцент Зверева Т.Е. Гомель 2006 Содержание Введение 1 Поиск в глубину 2 Задача "Дороги" 3 Задача "Перекрестки" 4 Задача "Скрудж Мак-Дак" Заключение Литература ВведениеПрежде всего, несколько слов о том, как возникает понятие графа из естественных условий задач. Приведем несколько примеров.Пусть мы имеем карту дорог, в которой для каждого города указано расстояние до всех соседних с ним. Здесь два города называются соседними, если существует дорога, соединяющая непосредственно эти два города.Аналогично, можно рассмотреть улицы и перекрестки внутри одного города. Заметим, что могут быть улицы с односторонним движением.Сеть компьютеров, соединенных проводными линиями связи.Набор слов, каждое из которых начинается на определенную букву и заканчивается на эту же или другую букву.Множество костей домино. Каждая кость имеет 2 числа: левую и правую половину кости.Устройство, состоящее из микросхем, соединенных друг с другом наборами проводников.Генеалогические деревья, указывающие родственные отношения между людьми.И, наконец, собственно графы, указывающие отношения между какими либо абстрактными понятиями, например, числами.Итак, неформально, граф можно определить как набор вершин (города, перекрестки, компьютеры, буквы, цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами; улицы между перекрестками; проводные линии связи между компьютерами; слова, начинающиеся на одну букву и закачивающиеся на другую или эту же букву; проводники, соединяющие микросхемы; родственные отношения, например, Алексей - сын Петра. Двунаправленные связи, например, дороги с двусторонним движением, принято называть ребрами графа; а однонаправленные связи, например, дороги с односторонним движением, принято называть дугами графа. Граф, в котором вершины соединяются ребрами, принято называть неориентированным графом, а граф, в котором хотя бы некоторые вершины соединяются дугами, принято называть ориентированным графом. 1. Поиск в глубинуНиже приведен пример неориентированного графа с шестью вершинами.При компьютерной обработке граф может задаваться списком ребер (дуг) для каждой вершины. Например, для графа, приведенного на примере, этот список выглядит такДля хранения этой информации в памяти компьютера можно воспользоваться двумерным массивом G[1..N,1..M], где N - число вершин в графе, M - максимально возможное число ребер (дуг) у одной вершины графа. Для удобства обработки этой информации можно также иметь одномерный массив kG[1..N] - количества ребер (дуг) вершин графа.Тогда для обработки списка связей текущей вершины U можно написатьfor i:=1 to kG[U]beginV:=G[U,i];end; Тем самым, мы получаем обработку дуги, связывающей вершины U и V для всех вершин, непосредственно связанных с U.Для обработки ВСЕХ связей всех вершин можно использовать поиск в глубину (DFS - Depth-First Search):for U:=1 to N do Color[U]:=WHITE;for U:=1 to N doif color[U]=WHITE then DFS(U);Procedure DFS(U:longint);varj : longint;begincolor[U]:=GRAY;for j:=1 to kG[U] do DFS(G[U,j]);end;ЗдесьColor[U] = цвет вершиныWHITE (константа=1) - белый, если мы еще не посещали эту вершинуGRAY (константа=2) - серый, если мы посещали данную вершинуDFS(U) - рекурсивная процедура, которая вызывает себя для всех вершин, потомков данной вершины.То есть, для обеспечения поиска в глубину на заданном графе G[1..N,1..M] с количествами дуг из вершин G[1..N], вначале мы устанавливаем всем вершинам цвет WHITE, а затем для всех вершин, которые еще не посещались (Color[G[U,j]]=WHITE) вызываем рекурсивную процедуру DFS.Таким способом формируются все возможные маршруты в графе. При этом нет ограничений на количество раз использования дуг и заходов в вершины.Если же по условиям задачи потребуется посещать каждую вершину не более одного раза, чтобы формировать маршруты из несовпадающих вершин, то это может быть обеспечено в процедуре DFS условным вызовом:Procedure DFS(U:longint);varj : longint;begincolor[U]:=GRAY;for j:=1 to kG[U] doif color[G[U,j]]=WHITE then DFS(G[U,j]);end;Если по условиям задачи требуется каждую дугу использовать не более одного раза, то можно ввести расцветку дуг:Color[1..N,1..M] - со значениями FREE или DONE где, как и ранееN - число вершин в графе,M - максимально возможное число ребер (дуг) у одной вершины графа.А процедура DFS формирования маршрутов так, что бы каждая дуга использовалась в маршруте не более одного раза, будет выглядеть следующим образом:procedure DFS(v:byte);var j : byte;beginfor j:=1 to kG[v] doif (color[v,j]=FREE)thenbegincolor[v,j]:=DONE;DFS(G[v,j]);color[v,j]:=FREE;end;end;Здесь вводятся пометки на дугиColor[v,j] = FREE,если дуга еще не обработана, и DONE, если она включена в текущий путь.Если в задаче требуется вывести найденный путь, то для его хранения заводится специальный массив SLED [1..Q], где Q - максимальное количество ребер в пути и вершины текущего пути заносятся в этот массив и удаляются из него в процессе обхода графа:procedure DFS(v:byte);var j : byte;beginfor j:=1 to kG[v] dobegininc(ks); sled[ks]:=G[v,j];DFS(G[v,j]);dec(ks);end;end;Приведенная теоретическая информация иллюстрируется далее примерами решения конкретных задач. 2 Задача "Дороги"Республиканская олимпиада по информатике 1997гДана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.Входные данные задаются в файле с именем PATH.IN следующим образом. В первой строке находится натуральное N(N<=50) - количество городов (города нумеруются от 1 до N). Во второй строке находится натуральное M(M<=100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M+3)-й строке находятся номера городов А, В и С.Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1. Кратко идея решения может быть изложена следующим образом:Поиск в глубину.Если встречаем вершину B, устанавливаем соответствующий флаг.Если встречаем вершину C и флаг B установлен - выводим результат и завершаем работу.После завершения поиска (требуемый маршрут не найден) выводим -1.Изложим решение более подробно.Ввод исходных данных осуществляется следующим образом:read(N,M);for i:=1 to M dobeginread(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;end;read(A,B,C);Здесь, как и прежде,kG[i] - количество дуг из вершины iG[i,j] - (для j от 1 до kG[j]) - вершины, с которыми вершина i связана соответствующей дугойКроме того, введен цвет дуги FREE - свободна (DONE - занята, FREE/DONE - константы)Главная программа фактически включает только следующие операторы:LabC:=0; { Установить метку - вершину C еще не посещали}DFS(A); { Поиск в глубину от вершины A }writeln(-1); { Вывод признака отсутствия требуемого пути} Рекурсивная процедура поиска в глубину от вершины V выглядит следующим образом:procedure DFS(v:byte);var j : byte;beginfor j:=1 to kG[v] doif (color[v,j]=FREE)thenbeginif (G[v,j]=B) and (LabC=1)then begin OutRes; halt; end;if G[v,j]=C then LabC:=1;color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];DFS(G[v,j]);color[v,j]:=FREE; sled[ks]:=0; dec(ks);if G[v,j]=C then LabC:=0;end;end;То есть для всех еще необработанных (color[v,j]=FREE) дуг от текущей вершины выясняем - если она ведет в конечный пункт, а город C уже проходили - вызов процедуры вывода результата и останов.Если текущая дуга ведет в город С, устанавливаем соответствующую метку (LabC=1).Помечаем дугу как обработанную, заносим ее в массив SLED, который содержит текущий обрабатываемый путь, KS - количество элементов в нем.Вызываем процедуру DFS от вершины (G[v,j]), в которую ведет текущая дуга.Перед выходом из процедуры DFS восстанавливаем состояние, "исходное" перед ее вызовом: снимаем отметку обработки с дуги ( color[v,j]:=FREE), удаляем ее из массива SLED (dec(ks), оператор sled[ks]:=0; делать необязательно, но он предоставляет удобства отладки - что бы в масcиве SLED ненулевыми были только реально входящие в путь элементы).И, наконец, процедура вывода результата:procedure OutRes;beginwriteln(ks+2);writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);end;Поскольку по алгоритму построения начальный (A) и конечный (B) города не заносились в массив SLED, то они выводятся отдельно, а количество городов в пути (KS) перед выводом увеличивается на 2.Полный текст программы приводится ниже.program by97d2s3;constFREE=1;DONE=2;varG,color : array[1..50,1..100] of byte;D : array[1..50] of longint;kG,sled : array[1..50] of byte;path : array[1..100] of byte;MinD,is : longint;i,j,x,y,A,B,C,N,M,ks,LabC : byte;Yes : boolean;procedure OutRes;beginwriteln(ks+2);writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);end;procedure DFS(v:byte);var j : byte;beginfor j:=1 to kG[v] doif (color[v,j]=FREE)thenbeginif (G[v,j]=B) and (LabC=1)then begin OutRes; halt; end;if G[v,j]=C then LabC:=1;color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];DFS(G[v,j]);color[v,j]:=FREE; sled[ks]:=0; dec(ks);if G[v,j]=C then LabC:=0;end;end;beginassign(input,'path.in'); reset(input);assign(output,'path.out'); rewrite(output);read(N,M);for i:=1 to M dobeginread(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;end;read(A,B,C);LabC:=0;DFS(A);writeln(-1);close(input); close(output);end.3 Задача "Перекрестки"(Автор - Котов В.М.)Республиканская олимпиада по информатике 1998гДаны декартовы координаты N перекрестков города, которые пронумерованы от 1 до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках. Для каждой дороги известно время, которое требуется для проезда по ней от одного перекрестка до другого.Необходимо проехать от перекрестка с номером А до перекрестка с номером В за минимальное время.Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы поворачиваете налево, то время ожидания равно D*К, где D равно количеству дорог, пересекающихся на перекрестке C, а К - некоторая константа. Если вы не поворачиваете налево, то время ожидания равно нулю.Написать программу, которая определяет самый быстрый маршрут.Спецификация входных данных.Входные данные находятся в текстовом файле с именем PER.IN и имеют следующую структуру:- в первой строке находится число N (натуральное, <=1000);- во второй строке - количество дорог M (натуральное, <=1000);- в третьей строке - константа K (натуральное число, <=1000);- в каждой из N следующих стpок находится паpа чисел х и у, разделенных пробелом, где x, y - кооpдинаты перекрестка (целые числа, не пpевышающие по модулю 1000);- в каждой из M следующих строк находится 3 числа p, r, t, разделенные пробелом, где p и r - номера перекрестков, которые соединяет дорога, а t (натуральное, <=1000) - время проезда по ней;- в последней строке находятся номера начального А и конечного В перекрестков.Спецификация выходных данных.Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:- в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;- в каждой из следующих строк находится одно число - номер очередного перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).Кратко идея решения может быть изложена следующим образом.Алгоритм Дейкстры напрямую не применим, поскольку:а) оптимальное решение в следующей вершине не является суммой оптимального решения для предыдущей вершины и веса текущего ребраб) вес текущего ребра - непостоянная величина, зависящая от того, каким поворотом мы вышли из вершины.Поэтому предлагается решение поиском в глубину. При этом разрешается использовать каждую вершину столько раз, сколько у нее есть ребер. Отсекаются решения хуже текущего оптимального.Можно еще ускорить решение, если обеспечивать перебор, начиная с правых поворотов (отсечения работали бы более эффективно).Замечание:В тексте задачи явно не указано, но авторы оригинальных тестов к задаче полагали, что поворот на 180 градусов - это левый поворот (как в армии: поворот на 180 градусов - "через левое плечо").Рассмотрим решение более подробно:Ввод исходных данных осуществляется следующим образом:read(N,M,K);for i:=1 to N do readln(x[i],y[i]);for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;for i:=1 to M dobeginreadln(p,r,t); inc(kG[p]); inc(kG[r]);G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);end;readln(vA,vB);Здесь kG[i] - количество дуг из вершины iG[i,j,1] - вершина, с которой соединена вершина i дугой с номером j в списке всех дуг из вершины i.G[i,j,2] - время проезда от вершины i до вершины, с которой она соединена дугой j в списке всех дуг из вершины i.D[i] - количество дорог, пересекающихся на перекрестке i (то есть суммарное количество дуг, исходящих из вершины i и входящик в нее), vA и vB указывают, откуда и куда нужно добираться.Поскольку по условиям задачи дороги двусторонние, то, для каждой введенной дороги, мы добавляем в граф две дуги.Основной алгоритм выглядит следующим образом: for i:=1 to N dobeginfor j:=1 to kG[i] do Color[i,j]:=WHITE; { все дуги свободны }Time[i]:=maxlongint; { время маршрута до I - максимально }end;OptT:=Maxlongint; { Оптимальное время - максимально}Sled[1]:=vA; { Заносим в маршрут вершину vA}kv:=1; { Количество вершин в маршруте = 1}Time[vA]:=0; { Оптимальное время до вершины vA =0}DFS(vA); { Поиск в глубину от вершины vA }вывод ответаРекурсивная процедура DFS(i) обеспечивает выполнение следующей работы:Procedure DFS(i)beginfor j:=1 to kG[i] doif G[i,j,1]<>vBthenbeginif color[i,j]=FREEthenbeginпродолжение пути с вызовом DFSendendelsebeginсравнение пути с текущим оптимальнымend;end;Если текущая вершина - конечная (vB), то делаем " ... сравнение пути с оптимальным"Иначе проверяем, если текущая дуга еще не использовась (color[i,j]=FREE) то делаем "... продолжение пути с вызовом DFS".При этом, перед входом в DFS помечаем дугу как использованную (color[i,j]:=DONE), а после выхода - как вновь свободную (color[i,j]:=FREE);"... продолжение пути с вызовом DFS" включает в себя следующие операторы:inc(kv); sled[kv]:=G[i,j,1]; { помещаем в путь новую вершину }NewTime:=Time[i]+G[i,j,2]+CountTime; {вычисляем новое время}if NewTime<OptT {если новое время меньше оптимального}then {то продолжаем,иначе - отсекаем}begincolor[i,j]:=DONE; { Помечаем - ребро использовано }RetTime:=Time[G[i,j,1]]; { Сохраняем старое время }Time[G[i,j,1]]:=NewTime; { Устанавливаем новое время }DFS(G[i,j,1]); { Вызываем поиск от G[i,j,1] }Time[G[i,j,1]]:=RetTime; { Восстанавливаем старое время }color[i,j]:=FREE; { Помечаем - ребро свободно }end;Sled[kv]:=0; dec(kv); { Удаляем вершину из пути } Для вычисления нового времени здесь используется функция CounTime с параметром kv - номер последней вершины в стеке.Эта функция делает следующее: Восстанавливает номера вершин, прохода через перекресток "из i1 через i2 в i3":if kv=2 then begin CountTime:=0; exit; end;i1 := sled[kv-2];i2 := sled[kv-1];i3 := sled[kv];if i3=i1 then begin CountTime:=K*D[i2]; exit; end;Попутно, выясняетсяа) если вершин в пути всего 2, то есть не было никакого поворота - это шаг из начальной вершины и CountTime=0.б) если i1=i3 то это поворот на 180 градусов и авторы задачи считают, что это тоже левый поворот, CountTime=K*D[i2]; где, K - коэффициент который вводится, i2 - перекресток, D[i2] - количество дорог, входящих в этот перекресток.Затем из массивов координат перекрестков выбираются координаты текущих перекрестков: (x1,y1) (откуда); (x2,y2) (через какой); (x3,y3) (куда).x1 := x[i1]; x2:=x[i2]; x3:=x[i3];y1 := y[i1]; y2:=y[i2]; y3:=y[i3];Вычисляется уравнение прямой по точкам (x1,y1) и (x2,y2)A := y2-y1;B := x1-x2;C := y1*(x2-x1)-x1*(y2-y1); Подстановкой координат (x3,y3) в уравнение прямой Ax+By+C=0, построенной по первым двум точкам (x1,y1) и (x2,y2) и с учетом крайних случаев, когда прямая параллельна осям координат, вычисляем, был ли поворот левым или правым и соответственно устанавливаем значение функции CountTime.Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or(((x2<x1) and ((A*x3+B*y3+C)<0))) or(((y2=y1) and (x1>x2) and (y3<y1))) or(((y2=y1) and (x1<x2) and (y3>y1))) or(((x2=x1) and (y1>y2) and (x3>x1))) or(((x2=x1) and (y1<y2) and (x3<x1))) ;if Left then CountTime:=K*D[i2]else CountTime:=0;"Сравнение пути с оптимальным" выполняется следующим образом:inc(kv); sled[kv]:=G[i,j,1];T := Time[i]+G[i,j,2] + CountTime;if T < OptTthen beginOptT:=T;OptKv:=kv; OptSled:=Sled;end;Sled[kv]:=0; dec(kv);Таким образом, оптимальное время хранится в переменной OptT а оптимальный путь храниться в массиве OptSled с количеством элементов OptKv. И потому, вывод результатов выглядит так: writeln(OptT);for i:=1 to OptKv do writeln(OptSled[i]);Полный текст программы приводится нижеprogram by98d2s2;ConstFREE = 1;DONE = 2;Typeint1000 = 0..1000;int3 = 1..3;varG : array[1..1000,1..10,1..2] of int1000;Time,D : array[1..1000] of longint;x,y,kG,Sled,OptSled,pred : array[1..1000] of int1000;Color : array[1..100,1..10] of int3;N,M,K,i,p,r,t,vA,vB,v,kv,OptKv,j : int1000;OptT : longint;function CountTime(i:int1000):longint;varLeft : boolean;i1,i2,i3 : int1000;x1,x2,x3,y1,y2,y3,A,B,C : longint;beginif kv=2 then begin CountTime:=0; exit; end;i1 := sled[kv-2];i2 := sled[kv-1];i3 := sled[kv];if i3=i1 then begin CountTime:=K*D[i2]; exit; end;x1 := x[i1]; x2:=x[i2]; x3:=x[i3];y1 := y[i1]; y2:=y[i2]; y3:=y[i3];A := y2-y1;B := x1-x2;C := y1*(x2-x1)-x1*(y2-y1);Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or(((x2<x1) and ((A*x3+B*y3+C)<0))) or(((y2=y1) and (x1>x2) and (y3<y1))) or(((y2=y1) and (x1<x2) and (y3>y1))) or(((x2=x1) and (y1>y2) and (x3>x1))) or(((x2=x1) and (y1<y2) and (x3<x1))) ;if Leftthen CountTime:=K*D[i2]else CountTime:=0;end;Procedure DFS(i:int1000);varj : byte;T : longint;RetSled,RetPred,RetTime :longint;beginfor j:=1 to kG[i] doif G[i,j,1]<>vBthenbeginif color[i,j]=FREEthenbegininc(kv); sled[kv]:=G[i,j,1];NewTime:=Time[i]+G[i,j,2]+CountTime;if NewTime<OptTthenbegincolor[i,j]:=DONE;RetTime:=Time[G[i,j,1]];Time[G[i,j,1]]:=NewTime;DFS(G[i,j,1]);Time[G[i,j,1]]:=RetTime;color[i,j]:=FREE;end;Sled[kv]:=0; dec(kv);endendelsebegininc(kv); sled[kv]:=G[i,j,1];T := Time[i]+G[i,j,2] + CountTime;if T < OptTthen beginOptT:=T;OptKv:=kv; OptSled:=Sled;end;Sled[kv]:=0; dec(kv);end;end;beginassign(input,'PER.in'); reset(input);assign(output,'PER.out'); rewrite(output);read(N,M,K);for i:=1 to N do readln(x[i],y[i]);for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;for i:=1 to M dobeginreadln(p,r,t); inc(kG[p]); inc(kG[r]);G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);end;readln(vA,vB);for i:=1 to N dobeginfor j:=1 to kG[i] do Color[i,j]:=FREE;Time[i]:=maxlongint;end;Time[vA]:=0; kv:=1; Sled[1]:=vA; OptT:=Maxlongint;DFS(vA);writeln(OptT);for i:=1 to OptKv do writeln(OptSled[i]);close(input); close(output);end.4 Задача "Скрудж Мак-Дак"(Автор - Котов В.М.)Республиканская олимпиада по информатике 1995гСкрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна.Его механик Винт Р. сделал устройство, вычисляющее эту функцию в несколько этапов с использование промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производится в любое время. После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза и любой параметр используется не более одного раза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функций.Входной файл INPUT.TXTФормат ввода:1 строка> <общее количество функций N>2 строка> <имя функции, которую необходимо вычислить>3 строка> <имя функции> <кол-во параметров>[<список имен параметров>]...N+2 строка> <имя функции> <кол-во параметров>[<список имен параметров>]Выходной файл OUTPUT.TXTФормат вывода:Размер памяти (в ячейках)имя 1-й вычисляемой функцииимя 2-й вычисляемой функции....имя функции, которую необходимо вычислитьПримечание: имя функции есть натуральное число от 1 до N.Пример. В кратком изложении в данной задаче требуется сделать следующее:- найти S - максимальную степень среди тех вершин, что подлежат обходу (поиск в глубину DFS1)- необходимая память вычисляется по формулеMaxS = S + k -1где S - найдено на предыдущем шаге (DFS1),а k - максимальное количество вершин одного уровня вложенности с такой же степенью S.Для вычисления k совершается обход повторным поиском в глубину DFS2- третьим поиском в глубину DFS3 находим и помещаем в очередь V все вершины, степень которых равна S.- последним, четвертым поиском в глубину обходим данное дерево в порядке вершин в очереди V. То есть, в первую очередь вычисляем те функции, для которых требуется максимальная память.Рассмотрим реализацию алгоритма более подробно.Ввод исходных данных осуществляется следующим образом:read(N,FC);for i:=1 to N dobeginread(f,kG[f]);for j:=1 to kG[f] do read(G[f,j]);end;ЗдесьN - исходное количество вершин,FC - номер функции, которую нужно вычислитьkG[i] - количество параметров для вычисления функции iG[i,j] - j-тый параметр, требуемый для вычисления функции iТело главной программы выглядит так :for i:=1 to N do color[i]:=WHITE;{пометить свободными все вершины}DFS1(FC);{находим S - максимальную степень вершин используемых для вычисления функции FC}MaxS:=S;DFS2(FC);{Вычисляем K - количество вершин со степенью S в текущем слое и MaxS - максимальная из значений по слоям величина S+K-1}kv:=0;DFS3(FC); {Поместить в массив V все вершины, степень которых равна S, количество таких вершин - в переменной kv}kr:=0;for i:=1 to kv do DFS4(v[i]);{Обход графа поиском в глубину начиная с вершин с максимальной степенью из массива V. Найденные вершины заносить в массив r}writeln(MaxS); {вывод количества ячеек памяти}for i:=1 to kr do writeln(r[i]);{вывод порядка вычисления функций}Полное решение задачи приводится нижеprogram by95d2t1;constWHITE = 1;GRAY = 2;BLACK = 3;varG : array [1..100,1..100] of longint;kG,v,color,r : array [1..100] of longint;N,FC,i,j,s,f,kv,MaxS,kr : longint;procedure DFS1(u:longint);vari,k : longint;beginif s<kG[u] then s:=kG[u];for i:=1 to kG[u] do DFS1(G[u,i]);end;procedure DFS2(u:longint);vari,k : longint;begink:=0;for i:=1 to kG[u] doif kG[G[i,j]]=s then inc(k);if MaxS<s+k-1 then MaxS:=s+k-1;for i:=1 to kG[u] do DFS2(G[u,i]);end;procedure DFS3(u:longint);vari,k : longint;beginif kG[u]=sthenbeginfor i:=1 to kG[u] do DFS3(G[u,i]);inc(kv); v[kv]:=u;end;end;procedure DFS4(u:longint);vari : longint;begincolor[u]:=GRAY;if kG[u]<>0thenfor i:=1 to kG[u] doif color[G[u,i]]<>GRAYthen DFS4(G[u,i]);inc(kr); r[kr]:=u;end;beginassign(input,'input.txt'); reset(input);assign(output,'output.txt'); rewrite(output);read(N,FC);for i:=1 to N dobeginread(f,kG[f]);for j:=1 to kG[f] do read(G[f,j]);end;for i:=1 to N do color[i]:=WHITE;DFS1(FC);MaxS:=s; DFS2(FC);kv:=0; DFS3(FC);kr:=0; for i:=1 to kv do DFS4(v[i]);writeln(MaxS);for i:=1 to kr do writeln(r[i]);close(input); close(output);end. ЗаключениеСуществует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.Необходимо отметить, что данный материал в существенной степени опирается на наличие у ученика определенных навыков в использовании рекурсивных функций и рекуррентных соотношений, которые, в частности, могут появиться при работе над предыдущими главами этой книги. Литература1. Абдеев Р.Ф. Философия информационной цивилизации. - М.: Владос, 1994.2. Адамар Ж. Исследование психологии процесса изобретения в области математики. - М.: Сов. радио, 1970.3. Болтянский В.Г. Информатика и преподавание математики// Математика в школе. 1989. № 4.-С.86-904. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. - М.: Радио и связь, 1982.5. Вирт Н. Алгоритмы+Структуры данных=Программа. - М.:Мир, 19896. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977.7. Громов Г.Р. Очерки информационной технологии. - М.: ИнфоАрт, 1993.8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.9. Ильенков Э. В. Философия и культура. - М.: Полит. лит., 1991.10. Йодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979.11. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980.12. Махмутов М.И. Организация проблемного обучения в школе. - М., 1986. |
РЕКЛАМА
|
|||||||||||||||||
| |||||||||||||||||||
| БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА | ||
 |
© 2010 | |