на тему рефераты Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
на тему рефераты
на тему рефераты
МЕНЮ|
на тему рефераты
поиск
Алгоритмы на графах. Кратчайшие расстояния на графах
ожно еще ускорить решение, если обеспечивать перебор, начиная с правых поворотов (отсечения работали бы более эффективно).

Замечание:

В тексте задачи явно не указано, но авторы оригинальных тестов к задаче полагали, что поворот на 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 do

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 N do

begin

for 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)

begin

for j:=1 to kG[i] do

if G[i,j,1]<>vB

then

begin

if color[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<OptT {если новое время меньше оптимального}

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 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 < OptT

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]);

Полный текст программы приводится ниже

program by98d2s2;

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;

function CountTime(i:int1000):longint;

var

Left : boolean;

i1,i2,i3 : int1000;

x1,x2,x3,y1,y2,y3,A,B,C : longint;

begin

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;

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 Left

then CountTime:=K*D[i2]

else CountTime:=0;

end;

Procedure DFS(i:int1000);

var

j : byte;

T : longint;

RetSled,RetPred,RetTime :longint;

begin

for j:=1 to kG[i] do

if G[i,j,1]<>vB

then

begin

if color[i,j]=FREE

then

begin

inc(kv); sled[kv]:=G[i,j,1];

NewTime:=Time[i]+G[i,j,2]+CountTime;

if NewTime<OptT

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 < OptT

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 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 do

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 N do

begin

for 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 do

begin

read(f,kG[f]);

for j:=1 to kG[f] do read(G[f,j]);

end;

Здесь

N - исходное количество вершин,

FC - номер функции, которую нужно вычислить

kG[i] - количество параметров для вычисления функции i

G[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;

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;

procedure DFS1(u:longint);

var

i,k : longint;

begin

if s<kG[u] then s:=kG[u];

for i:=1 to kG[u] do DFS1(G[u,i]);

end;

procedure DFS2(u:longint);

var

i,k : longint;

begin

k:=0;

for i:=1 to kG[u] do

if 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);

var

i,k : longint;

begin

if kG[u]=s

then

begin

for i:=1 to kG[u] do DFS3(G[u,i]);

inc(kv); v[kv]:=u;

end;

end;

procedure DFS4(u:longint);

var

i : longint;

begin

color[u]:=GRAY;

if kG[u]<>0

then

for i:=1 to kG[u] do

if color[G[u,i]]<>GRAY

then DFS4(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 N do

begin

read(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-90

4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. - М.: Радио и связь, 1982.

5. Вирт Н. Алгоритмы+Структуры данных=Программа. - М.:Мир, 1989

6. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977.

7. Громов Г.Р. Очерки информационной технологии. - М.: ИнфоАрт, 1993.

8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.

9. Ильенков Э. В. Философия и культура. - М.: Полит. лит., 1991.

10. Йодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979.

11. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980.

12. Махмутов М.И. Организация проблемного обучения в школе. - М., 1986.

Страницы: 1, 2


© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.