Министерствообразования Республики Беларусь
Учреждениеобразования
«Гомельскийгосударственный университет им. Ф. Скорины»
Математическийфакультет
Кафедра МПУ
Алгоритмы награфах. Поиск в глубину
Курсоваяработа
Исполнитель:
Студентка группы М-43 Полякова А.Ю.
Научный руководитель:
Канд. физ-мат. наук, доцент ЗвереваТ.Е.
Гомель 2006
Содержание
Введение
1 Поиск в глубину
2 Задача «Дороги»
3 Задача «Перекрестки»
4 Задача «Скрудж Мак-Дак»
Заключение
Литература
Введение
Прежде всего, несколькослов о том, как возникает понятие графа из естественных условий задач. Приведемнесколько примеров.
Пусть мы имеем картудорог, в которой для каждого города указано расстояние до всех соседних с ним.Здесь два города называются соседними, если существует дорога, соединяющаянепосредственно эти два города.
Аналогично, можнорассмотреть улицы и перекрестки внутри одного города. Заметим, что могут бытьулицы с односторонним движением.
Сеть компьютеров,соединенных проводными линиями связи.
Набор слов, каждое изкоторых начинается на определенную букву и заканчивается на эту же или другуюбукву.
Множество костей домино.Каждая кость имеет 2 числа: левую и правую половину кости.
Устройство, состоящее измикросхем, соединенных друг с другом наборами проводников.
Генеалогические деревья,указывающие родственные отношения между людьми.
И, наконец, собственнографы, указывающие отношения между какими либо абстрактными понятиями,например, числами.
Итак, неформально, графможно определить как набор вершин (города, перекрестки, компьютеры, буквы,цифры кости домино, микросхемы, люди) и связей между ними: дороги между городами;улицы между перекрестками; проводные линии связи между компьютерами; слова,начинающиеся на одну букву и закачивающиеся на другую или эту же букву;проводники, соединяющие микросхемы; родственные отношения, например, Алексей — сын Петра. Двунаправленные связи, например, дороги с двусторонним движением,принято называть ребрами графа; а однонаправленные связи, например, дороги содносторонним движением, принято называть дугами графа. Граф, в котором вершинысоединяются ребрами, принято называть неориентированным графом, а граф, вкотором хотя бы некоторые вершины соединяются дугами, принято называтьориентированным графом.
1. Поиск в глубину
Ниже приведен примернеориентированного графа с шестью вершинами.
/>
При компьютернойобработке граф может задаваться списком ребер (дуг) для каждой вершины.Например, для графа, приведенного на примере, этот список выглядит так
/>
Для хранения этойинформации в памяти компьютера можно воспользоваться двумерным массивомG[1..N,1..M], где N — число вершин в графе, M — максимально возможное числоребер (дуг) у одной вершины графа. Для удобства обработки этой информации можнотакже иметь одномерный массив kG[1..N] — количества ребер (дуг) вершин графа.
Тогда для обработкисписка связей текущей вершины U можно написать
for i:=1 tokG[U]
begin
V:=G[U,i];
end;
Тем самым, мы получаемобработку дуги, связывающей вершины U и V для всех вершин, непосредственносвязанных с U.
Для обработки ВСЕХ связейвсех вершин можно использовать поиск в глубину (DFS — Depth-First Search):
for U:=1 to Ndo Color[U]:=WHITE;
for U:=1 to Ndo
ifcolor[U]=WHITE then DFS(U);
ProcedureDFS(U:longint);
var
j: longint;
begin
color[U]:=GRAY;
for j:=1 tokG[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 условным вызовом:
ProcedureDFS(U:longint);
var
j: longint;
begin
color[U]:=GRAY;
for j:=1 tokG[U] do
ifcolor[G[U,j]]=WHITE then DFS(G[U,j]);
end;
Если по условиям задачитребуется каждую дугу использовать не более одного раза, то можно ввестирасцветку дуг:
Color[1..N,1..M] — созначениями FREE или DONE где, как и ранее
N — число вершин в графе,
M — максимально возможноечисло ребер (дуг) у одной вершины графа.
А процедура DFSформирования маршрутов так, что бы каждая дуга использовалась в маршруте неболее одного раза, будет выглядеть следующим образом:
procedureDFS(v:byte);
var j: byte;
begin
for j:=1 tokG[v] do
if(color[v,j]=FREE)
then
begin
color[v,j]:=DONE;
DFS(G[v,j]);
color[v,j]:=FREE;
end;
end;
Здесь вводятся пометки надуги
Color[v,j] = FREE,
если дуга еще необработана, и DONE, если она включена в текущий путь.
Если в задаче требуетсявывести найденный путь, то для его хранения заводится специальный массив SLED[1..Q], где Q — максимальное количество ребер в пути и вершины текущего путизаносятся в этот массив и удаляются из него в процессе обхода графа:
procedureDFS(v:byte);
var j: byte;
begin
for j:=1 tokG[v] do
begin
inc(ks);sled[ks]:=G[v,j];
DFS(G[v,j]);
dec(ks);
end;
end;
Приведенная теоретическаяинформация иллюстрируется далее примерами решения конкретных задач.
2 Задача «Дороги»
Республиканская олимпиадапо информатике 1997г
Дана система одностороннихдорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, чтоиз города i можно проехать в город j, но это не значит, что можно проехать в обратномнаправлении.
Необходимо определить, можноли проехать из заданного города А в заданный город В таким образом, чтобыпосетить город С и не проезжать ни по какой дороге более одного раза.
Входные данные задаются вфайле с именем PATH.IN следующим образом. В первой строке находится натуральноеN(N
Ответом являетсяпоследовательность городов, начинающаяся городом А и заканчивающаяся городом В,удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT ввиде последовательности номеров городов по одному номеру в строке. Перваястрока файла должна содержать количество городов в последовательности. Приотсутствии пути записать в первую строку файла число -1.
/>
Кратко идея решения можетбыть изложена следующим образом:
Поиск в глубину.
Если встречаем вершину B,устанавливаем соответствующий флаг.
Если встречаем вершину Cи флаг B установлен — выводим результат и завершаем работу.
После завершения поиска(требуемый маршрут не найден) выводим -1.
Изложим решение болееподробно.
Ввод исходных данныхосуществляется следующим образом:
read(N,M);
for i:=1 to Mdo
begin
read(x,y);inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
end;
read(A,B,C);
Здесь, как и прежде,
kG[i] — количество дуг извершины i
G[i,j] — (для j от 1 доkG[j]) — вершины, с которыми вершина i связана соответствующей дугой
Кроме того, введен цветдуги FREE — свободна (DONE — занята, FREE/DONE — константы)
Главная программафактически включает только следующие операторы:
LabC:=0; { Установитьметку — вершину C еще не посещали}
DFS(A); { Поиск в глубинуот вершины A }
writeln(-1); { Выводпризнака отсутствия требуемого пути}
Рекурсивная процедурапоиска в глубину от вершины V выглядит следующим образом:
procedureDFS(v:byte);
var j: byte;
begin
for j:=1 tokG[v] do
if(color[v,j]=FREE)
then
begin
if (G[v,j]=B)and (LabC=1)
then beginOutRes; halt; end;
if G[v,j]=Cthen 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]=Cthen 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 ненулевыми были только реальновходящие в путь элементы).
И, наконец, процедуравывода результата:
procedureOutRes;
begin
writeln(ks+2);
writeln(A);for i:=1 to ks do writeln(sled[i]); writeln(B);
end;
Поскольку по алгоритмупостроения начальный (A) и конечный (B) города не заносились в массив SLED, тоони выводятся отдельно, а количество городов в пути (KS) перед выводомувеличивается на 2.
Полный текст программыприводится ниже.
programby97d2s3;
const
FREE=1;
DONE=2;
var
G,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;
procedureOutRes;
begin
writeln(ks+2);
writeln(A);for i:=1 to ks do writeln(sled[i]); writeln(B);
end;
procedureDFS(v:byte);
var j: byte;
begin
for j:=1 tokG[v] do
if(color[v,j]=FREE)
then
begin
if (G[v,j]=B)and (LabC=1)
then beginOutRes; halt; end;
if G[v,j]=Cthen 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]=Cthen LabC:=0;
end;
end;
begin
assign(input,'path.in');reset(input);
assign(output,'path.out');rewrite(output);
read(N,M);
for i:=1 to Mdo
begin
read(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 (натуральное,
— во второй строке — количество дорог M (натуральное,
— в третьей строке — константа K (натуральное число,
— в каждой из N следующихстpок находится паpа чисел х и у, разделенных пробелом, где x, y — кооpдинатыперекрестка (целые числа, не пpевышающие по модулю 1000);
— в каждой из M следующихстрок находится 3 числа p, r, t, разделенные пробелом, где p и r — номераперекрестков, которые соединяет дорога, а t (натуральное,
— в последней строкенаходятся номера начального А и конечного В перекрестков.
Спецификация выходныхданных.
Выходные данные должныбыть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:
— в первой строке находитсянатуральное число T — время проезда по самому быстрому маршруту;
— в каждой из следующихстрок находится одно число — номер очередного перекрестка в маршруте (начиная сперекрестка с номером А и кончая В).
Кратко идея решения можетбыть изложена следующим образом.
Алгоритм Дейкстрынапрямую не применим, поскольку:
а) оптимальное решение вследующей вершине не является суммой оптимального решения для предыдущейвершины и веса текущего ребра
б) вес текущего ребра — непостоянная величина, зависящая от того, каким поворотом мы вышли из вершины.
Поэтому предлагаетсярешение поиском в глубину. При этом разрешается использовать каждую вершинустолько раз, сколько у нее есть ребер. Отсекаются решения хуже текущегооптимального.
Можно еще ускоритьрешение, если обеспечивать перебор, начиная с правых поворотов (отсеченияработали бы более эффективно).
Замечание:
В тексте задачи явно неуказано, но авторы оригинальных тестов к задаче полагали, что поворот на 180градусов — это левый поворот (как в армии: поворот на 180 градусов — «через левое плечо»).
Рассмотрим решение болееподробно:
Ввод исходных данныхосуществляется следующим образом:
read(N,M,K);
for i:=1 to Ndo readln(x[i],y[i]);
for i:=1 to Ndo begin kG[i]:=0; D[i]:=0; end;
for i:=1 to Mdo
begin
readln(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] — количестводуг из вершины i
G[i,j,1] — вершина, скоторой соединена вершина i дугой с номером j в списке всех дуг из вершины i.
G[i,j,2] — время проездаот вершины i до вершины, с которой она соединена дугой j в списке всех дуг извершины i.
D[i] — количество дорог,пересекающихся на перекрестке i (то есть суммарное количество дуг, исходящих извершины i и входящик в нее),
vA и vB указывают, откудаи куда нужно добираться.
Поскольку по условиямзадачи дороги двусторонние, то, для каждой введенной дороги, мы добавляем вграф две дуги.
Основной алгоритмвыглядит следующим образом:
for i:=1 to Ndo
begin
for j:=1 tokG[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) обеспечивает выполнение следующей работы:
ProcedureDFS(i)
begin
for j:=1 tokG[i] do
ifG[i,j,1]vB
then
begin
ifcolor[i,j]=FREE
then
begin
продолжение пути свызовом DFS
end
end
else
begin
сравнение пути с текущимоптимальным
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
then {то продолжаем, иначе- отсекаем}
begin
color[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 thenbegin CountTime:=0; exit; end;
i1 :=sled[kv-2];
i2 :=sled[kv-1];
i3 :=sled[kv];
if i3=i1 thenbegin 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)
(((x2
(((y2=y1) and(x1>x2) and (y3
(((y2=y1) and(x1y1))) or
(((x2=x1) and(y1>y2) and (x3>x1))) or
(((x2=x1) and(y1
if Left thenCountTime:=K*D[i2]
else CountTime:=0;
«Сравнение пути соптимальным» выполняется следующим образом:
inc(kv);sled[kv]:=G[i,j,1];
T :=Time[i]+G[i,j,2] + CountTime;
if T
then begin
OptT:=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]);
Полный текст программыприводится ниже
programby98d2s2;
Const
FREE = 1;
DONE = 2;
Type
int1000 =0..1000;
int3 = 1..3;
var
G: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;
functionCountTime(i:int1000):longint;
var
Left:boolean;
i1,i2,i3:int1000;
x1,x2,x3,y1,y2,y3,A,B,C: longint;
begin
if kv=2 thenbegin CountTime:=0; exit; end;
i1 :=sled[kv-2];
i2 :=sled[kv-1];
i3 :=sled[kv];
if i3=i1 thenbegin 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)
(((x2
(((y2=y1) and(x1>x2) and (y3
(((y2=y1) and(x1y1))) or
(((x2=x1) and(y1>y2) and (x3>x1))) or
(((x2=x1) and(y1
if Left
thenCountTime:=K*D[i2]
elseCountTime:=0;
end;
ProcedureDFS(i:int1000);
var
j: byte;
T: longint;
RetSled,RetPred,RetTime:longint;
begin
for j:=1 tokG[i] do
ifG[i,j,1]vB
then
begin
ifcolor[i,j]=FREE
then
begin
inc(kv);sled[kv]:=G[i,j,1];
NewTime:=Time[i]+G[i,j,2]+CountTime;
ifNewTime
then
begin
color[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);
end
end
else
begin
inc(kv);sled[kv]:=G[i,j,1];
T :=Time[i]+G[i,j,2] + CountTime;
if T
then begin
OptT:=T;
OptKv:=kv;OptSled:=Sled;
end;
Sled[kv]:=0;dec(kv);
end;
end;
begin
assign(input,'PER.in');reset(input);
assign(output,'PER.out');rewrite(output);
read(N,M,K);
for i:=1 to Ndo readln(x[i],y[i]);
for i:=1 to Ndo begin kG[i]:=0; D[i]:=0; end;
for i:=1 to Mdo
begin
readln(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 Ndo
begin
for j:=1 tokG[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 toOptKv do writeln(OptSled[i]);
close(input);close(output);
end.4 Задача «Скрудж Мак-Дак»
(Автор — Котов В.М.)
Республиканская олимпиадапо информатике 1995г
Скрудж Мак-Дак решилсделать прибор для управления самолетом. Как известно, положение штурвалазависит от состояния входных датчиков, но эта функция довольно сложна.
Его механик Винт Р. сделалустройство, вычисляющее эту функцию в несколько этапов с использованиепромежуточной памяти и вспомогательных функций. Для вычисления каждой изфункций требуется, чтобы в ячейках памяти уже находились вычисленные параметры(которые являются значениями вычисленных функций), необходимые для ее вычисления.Вычисление функции без параметров может производится в любое время. Послевычисления функции ячейки могут быть использованы повторно (хотя бы для записи результатавычисленной функции). Структура вызова функций такова, что каждая функциявычисляется не более одного раза и любой параметр используется не более одногораза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денегна микросхемы, он поставил задачу минимизировать память прибора. По заданнойструктуре вызовов функций необходимо определить минимальный возможный размер памятиприбора и указать последовательность вычисления функций.
Входной файл INPUT.TXT
Формат ввода:
1 строка>
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 Ndo
begin
read(f,kG[f]);
for j:=1 tokG[f] do read(G[f,j]);
end;
Здесь
N — исходное количествовершин,
FC — номер функции,которую нужно вычислить
kG[i] — количествопараметров для вычисления функции i
G[i,j] — j-тый параметр,требуемый для вычисления функции i
Тело главной программывыглядит так :
for i:=1 to Ndo 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 kvdo DFS4(v[i]);
{Обход графа поиском вглубину начиная с вершин с максимальной степенью из массива V. Найденныевершины заносить в массив r}
writeln(MaxS); {выводколичества ячеек памяти}
for i:=1 to krdo writeln(r[i]);
{вывод порядка вычисленияфункций}
Полное решение задачиприводится ниже
program by95d2t1;
const
WHITE = 1;
GRAY = 2;
BLACK = 3;
var
G: 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;
procedureDFS1(u:longint);
var
i,k: longint;
begin
if s
for i:=1 tokG[u] do DFS1(G[u,i]);
end;
procedureDFS2(u:longint);
var
i,k: longint;
begin
k:=0;
for i:=1 tokG[u] do
ifkG[G[i,j]]=s then inc(k);
ifMaxS
for i:=1 tokG[u] do DFS2(G[u,i]);
end;
procedureDFS3(u:longint);
var
i,k: longint;
begin
if kG[u]=s
then
begin
for i:=1 tokG[u] do DFS3(G[u,i]);
inc(kv);v[kv]:=u;
end;
end;
procedureDFS4(u:longint);
var
i: longint;
begin
color[u]:=GRAY;
ifkG[u]0
then
for i:=1 tokG[u] do
ifcolor[G[u,i]]GRAY
thenDFS4(G[u,i]);
inc(kr);r[kr]:=u;
end;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
read(N,FC);
for i:=1 to Ndo
begin
read(f,kG[f]);
for j:=1 tokG[f] do read(G[f,j]);
end;
for i:=1 to Ndo color[i]:=WHITE;
DFS1(FC);
MaxS:=s;DFS2(FC);
kv:=0; DFS3(FC);
kr:=0; fori:=1 to kv do DFS4(v[i]);
writeln(MaxS);
for i:=1 to krdo writeln(r[i]);
close(input);close(output);
end.
Заключение
Существует целый классзадач по программированию, которые проще решаются, если ученик владеетопределенным набором знаний, умений и навыков в области алгоритмов на графах.Это происходит потому, что такие задачи могут быть переформулированы в терминахтеории графов.
Теория графов содержитогромное количество определений, теорем и алгоритмов. И поэтому данный материалне может претендовать, и не претендует, на полноту охвата материала. Однако, помнению автора, предлагаемые сведения являются хорошим компромиссом междуобъемом материала и его «коэффициентом полезного действия» впрактическом программировании и решении олимпиадных задач.
Необходимо отметить, чтоданный материал в существенной степени опирается на наличие у ученикаопределенных навыков в использовании рекурсивных функций и рекуррентныхсоотношений, которые, в частности, могут появиться при работе над предыдущимиглавами этой книги.
/>Литература
1. Абдеев Р.Ф. Философия информационной цивилизации. — М.:Владос, 1994.
2. Адамар Ж. Исследование психологии процесса изобретения вобласти математики. — М.: Сов. радио, 1970.
3. Болтянский В.Г. Информатика и преподавание математики//Математика в школе. 1989. № 4.-С.86-90
4. Вейценбаум Дж. Возможности вычислительных машин ичеловеческий разум. — М.: Радио и связь, 1982.
5. Вирт Н. Алгоритмы+Структуры данных=Программа. — М.: Мир,1989
6. Вирт Н. Систематическое программирование: Введение. — М.:Мир, 1977.
7. Громов Г.Р. Очерки информационной технологии. — М.:ИнфоАрт, 1993.
8. Дейкстра Э. Дисциплина программирования. — М.: Мир, 1978.
9. Ильенков Э. В. Философия и культура. — М.: Полит. лит.,1991.
10. Йодан Э. Структурное проектирование и конструированиепрограмм. — М.: Мир, 1979.
11. Майерс Г. Надежность программного обеспечения. — М.: Мир,1980.
12. Махмутов М.И. Организация проблемного обучения в школе. — М., 1986.