Поиск кратчайшего пути в лабиринте 2 (стр. 1 из 2)

Министерство образования и науки Российской Федерации

Агентство по образованию

Тихоокеанский государственный экономический университет

Экономический институт

Курсовая работа

Поиск кратчайшего пути в лабиринте

Выполнил: Иванов Б.Н.

Владивосток 2009

Содержание

1. Введение

2. Формальная постановка задачи

3. Методы решения

4. Модульная организация приложения

4.1 Общая схема взаимодействия модулей

4.2 Описание модулей

5. Текст программы

6. Руководство пользователя

7. Тестовый пример игры

Заключение

Список литературы

1. Введение

Условие решаемой задачи дословно по заданию звучит следующим образом: «Задан лабиринт, составленный из комнат, у каждой из которой имеется не менее одной и не более трех дверей, соединяющих между собой различные комнаты. Одна из дверей называется входом в лабиринт, другая — выходом. Найти кратчайший путь от входа в лабиринт к его выходу».

Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает лабиринт и находит кратчайший путь его прохождения и отображает его.

Лабиринт задается во входном файле, в том же файле указываются координаты входа и выхода, и для начала работы нам необходимо выбрать нужный лабиринт, программа должна выдать размер кратчайшего пути, нарисовать лабиринт и показать этот путь.

Если же путь не найден программа выдает сообщение, о том что данный путь не существует.

2. Формальная постановка задачи

Для программной реализации необходимо формализовать структуры данных задачи и рассмотреть методы ее решения. Лабиринт мы задаем во входном файле матрицей, состоящих из 8, 0 и 1. Каждая запись массива определяет комнату лабиринта — восьмерка характеризует саму комнату и четыре координаты вокруг нее (0- стена или 1- проход) есть или нет проход. Так же во входном файле задаются координаты входа, выхода и размерность массива. Именно с этим массивом работает программа при нахождении пути.

3. Методы решения задачи

Существует довольно много различных методов решения подобной задачи, каждый из которых основывается на своих принципах и приемах, имеет уникальные преимущества и, соответственно, недостатки. В данной работе был использован метод нахождения кратчайшего пути на графе.

Этот алгоритм определяет расстояние между вершинами в простом орграфе с неотрицательными весами. Если граф не взвешен, то можно считать, что все ребра имеют одинаковый вес.

Возьмем простой граф для каждого ребра определим вес, то есть длина любого ребра больше 0. Найдем кратчайший путь между вершинами которые мы определили как начала и конец. Несуществующие ребра будем считать ребрами с бесконечными весами. Сумму весов ребер в пути будем называть весом или длиной пути. Алгоритм поиска кратчайшего пути, начинаем из вершины которую мы обозначили как начало, просматривает граф в ширину помечая пройденные вершины значениями-метками их расстояния от начала. Метки могут быть временные и окончательные. Окончательная метка- это минимально расстояние на графе от начала до пройденной вершины. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а остальная их часть – временные. Алгоритм заканчивается, когда конечная вершина получает окончательную метку, то есть расстояния от начала до конца.

Вначале первой вершине присваивается окончательная метка 0 (нулевое расстояние до самой себя) а каждой из остальных вершин присваивается временная метка бесконечность. На каждом шаге метки меняются следующим образом.

1. Каждой вершине, не имеющей окончательной метки, присваивается новая временная метка – наименьшая из ее временной и числа, которому присвоена окончательная метка на предыдущем шаге.

2. Определяется наименьшая из всех временных меток, которая и становится окончательной меткой своей вершины. В случае равенства выбирается любая из них.

Циклический процесс п.1 и п.2 продолжается до тех пор, пока конечная вершина не получит окончательной метки. Легко видеть, что окончательная метка каждой вершины – это кратчайшее расстояния между начальной и конечной вершинами.

4. Модульная организация приложения

Реализация проекта выполнена в рамках трех модулей. Каждый из них выполняет определенные для него функции. Разделение функций модулей выполнено в соответствии с задачами проекта. В общем случае разделение выполняется на две составные части: проведение расчетов и визуализация полученных данных.

4.1 Общая схема взаимодействия модулей

4.2 Описание модулей

Каждый из модулей реализует свой класс. Описание модулей призываются к описанию классов (их назначения) и методов классов (решения определенных задач класса).

1). UnWay — модуль реализации класса TWay проведения всех вычисления нахождения кратчайшего пути.

Методы класса TWay.

Procedure TWay.Input — процедура ввода перегородок комнаты

Procedure TWay.CreateAdj — процедура формирование матрицы смежности комнат

Procedure TWay.ShortRoom – процедура поиска минимального пути

2). UnDraw — модуль реализации класса TOcno

Методы класса TOcno.

Procedure TOcno.Organize - процедура формирует сеть прямоугольников

Procedure TOcno.DrawWay – процедура рисует найденный кратчайший путь

Procedure TOcno.DrawRect – процедура рисует перегородки лабиринта

5. Текст программы

В данном пункте приводятся тексты отдельных наиболее значимых разработанных классов приложения и их ключевых методов.

Класса TWay вычисления маршрута коня по шахматному полю.

TWay = class

Public

nmDataFile:String;

fout:TextFile; {Файл печати данных}

nX:Integer; { Количество вершин в графе }

Mark:TypeMark; { Признаки временных и постоянных меток }

Dist:TypeDist; { Значения текущих меток вершин (расстояния) }

Prev:TypePrev; { Указатель на ближайшую вершину }

x0:Integer; { Вершина начала пути }

z:Integer; { Вершина конца пути }

y:Integer; { Последняя вершина с постоянной меткой }

nr,mr:Integer; {Размеры комнат барьеров}

Adj:TypeAdj; {Структура смежности}

nA:Integer; {Число комнат и вершин}

Wr:TypeWe; {Перегородки комнат}

zEnd:Integer; { Вершина конца пути-найденная }

Public

Constructor Init;

Destructor Done;

Procedure Input;

Procedure CreateAdj;

Procedure ShortRoom;

function YesRib(xr,yr:Integer):Boolean;

end;

Ключевые методы класса TMaze

// процедура ввода перегородок комнаты

Procedure TWay.Input;

var f:TextFile; {Файл ввода данных}

i,j,w:Integer;

i0,j0:Integer;

iz,jz:Integer;

begin

AssignFile(f,nmDataFile);

Reset(f);{Файл открыт для чтения}

ReadLn(f,i0,j0); {Начало пути}

ReadLn(f,iz,jz); {Конец пути}

ReadLn(f,nr,mr); {Размеры комнаты барьеров}

//---------------------------------------------

x0:=(i0-1)*mr+(j0-1); //Комната-Начало

z:=(iz-1)*mr+(jz-1); //Комната-Конец

zEnd:=z;

//---------------------------------------------

//Обнулить

for i:=1 to nr do begin

for j:=1 to mr do begin

Wr[i,j].L:=0;

Wr[i,j].U:=0;

Wr[i,j].R:=0;

Wr[i,j].D:=0;

end;

for i:=1 to nr do begin

//----------------------------------------

if i=1 then

for j:=1 to mr do Read(f,Wr[i,j].U)

else

for j:=1 to mr do Wr[i,j].U:=Wr[i-1,j].D;

//----------------------------------------

for j:=1 to mr do begin

if j=1 then Read(f,Wr[i,1].L);

Read(f,w,Wr[i,j].R);

if j<mr then Wr[i,j+1].L:=Wr[i,j].R;

end;

for j:=1 to mr do Read(f,Wr[i,j].D);

end;

// процедура формирование матрицы смежности комнат

Procedure TWay.CreateAdj;

var i,j,k,v:Integer;

begin

na:=nr*mr; {Число комнат-вершин}

k:=0;

for i:=1 to nr do begin

for j:=1 to mr do begin

for v:=1 to 4 do Adj[k,v]:=-1; //Нет прохода

if wr[i,j].L=1 then Adj[k,1]:=k-1;

if wr[i,j].R=1 then Adj[k,2]:=k+1;

if wr[i,j].U=1 then Adj[k,3]:=k-mr;

if wr[i,j].D=1 then Adj[k,4]:=k+mr;

k:=k+1; //Число комнат

end;

//------------------------------------

for k:=0 to na-1 do begin

for v:=1 to 4 do begin

Write(fout,Adj[k,v]:3);

end;

WriteLn(fout);

end;

//процедура поиска минимального пути

Procedure TWay.ShortRoom;

Var

i,j,x,k:Integer;

weight:LongInt;

yes:Boolean;

begin

nX:=na-1; (* X={0,1,2,...,nX} - множество вершин *)

//Вычисления

for x:=0 to nX do begin

Mark[x]:=FALSE;

Dist[x]:=$7fffffff;

end;

y:=x0; {Последняя вершина с постоянной меткой}

Mark[y]:=TRUE;

Dist[y]:=0;

zEnd:=z;

while not Mark[z] do begin

{Обновить временные метки}

for x:=0 to nX do

if (not Mark[x]) and YesRib(x,y) and (Dist[x]>Dist[y]+1) then begin

Dist[x]:=Dist[y]+1;

Prev[x]:=y;

end;

{Поиск вершины с минимальной временной меткой}

yes:=False;

weight:=$7fffffff;

for x:=0 to nX do if not Mark[x] then if weight>Dist[x] then begin

weight:=Dist[x];

y:=x;

yes:=True;

end;

if not yes then begin

Write(fout,'Нет выхода из лабиринта!');

showmessage('нет выхода из лабиринта');

zEnd:=y; //Последняя пройденная

break;

end;

Mark[y]:=TRUE;

end;

Класса TOcno рисование лабиринта

TOcno = class(TObject)

public

mI:TRect;//Железное окно

mC:TCanvas;//Графический контекст

m,n:Integer;//Размерность (m,n)

R: array of array of TRect;//Сеть прямоугольников

C0,C1: TColor;

public

procedure Init();

procedure Done();

procedure Draw(wCvas:TCanvas; wIron:TRect; md:TWay);

procedure DrawRect(i,j:Integer; md:Tway);

procedure Organize(zR: TRect);

function MouseRect(mX,mY:Integer; md:Tway):Boolean;

procedure DrawWay(md:Tway);

end;

Ключевые методы класса TOcno.

// процедура формирует сеть прямоугольников

procedure TOcno.Organize(zR: TRect);

var i,j,d,k:Integer;

x,y,z:array of Integer;

pr:String;

begin

//Разрушить

//if R<>nil then for i:=0 to m do R[i]:=nil;

R:=nil;

SetLength(R,m+1); //Память

for i:=0 to m do SetLength(R[i],n+1);

//Формируем прямоугольники

SetLength(y,m+1);

SetLength(x,n+1);

SetLength(z,m+n+1);

//По высоте

d:=(zR.Bottom-zR.Top) div m;

k:=(zR.Bottom-zR.Top) mod m;

for i:=0 to m-1 do z[i]:=d;

for i:=0 to k-1 do inc(z[i]);

y[0]:=zR.Top;

for i:=0 to m-1 do y[i+1]:=y[i]+z[i];

//По ширине

d:=(zR.Right-zR.Left) div n;

k:=(zR.Right-zR.Left) mod n;

for j:=0 to n-1 do z[j]:=d;

for j:=0 to k-1 do inc(z[j]);

x[0]:=zR.Left;

for j:=0 to n-1 do x[j+1]:=x[j]+z[j];

//Прямоугольники

for i:=0 to m-1 do begin

for j:=0 to n-1 do begin

R[i+1,j+1]:=Rect(x[j],y[i],x[j+1],y[i+1]);

end;

x:=nil;

y:=nil;

z:=nil;

end;

// процедура рисует найденный кратчайший путь

procedure TOcno.DrawWay(md:Tway);

var k,x,ir,jr:Integer;

wr,wrG:TRect;

h,w:Integer;

cx,cy:Integer;

begin

k:=md.z;

x:=k+1;

ir:=(x-1) div md.mr +1;

jr:=(x-1) mod md.mr +1;

wr:=R[ir,jr];

cx:=(wr.Left+wr.Right) div 2;

cy:=(wr.Top+wr.Bottom) div 2;

w:=(wr.Right-wr.Left) div 12;

h:=(wr.Bottom-wr.Top) div 7;

wr.Left:=cx-w;