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

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

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

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

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

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

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

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

Владивосток 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;

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;

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;

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;

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;

wr.Right:=cx+w;

wr.Top:=cy-h;

wr.Bottom:=cy+h;

mC.Brush.Color:=RGB(0,255,255);

mC.Pen.Width:=3;

mC.Pen.Color:=RGB(0,0,0);

mC.Arc(wR.Left, wR.Top, wR.Right, wR.Bottom, wR.Left, wR.Top, wR.Left, wR.Top);

k:=md.zEnd;

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;

wr.Right:=cx+w;

wr.Top:=cy-h;

wr.Bottom:=cy+h;

mC.MoveTo(cx,cy);

mC.Brush.Color:=RGB(0,255,0);

mC.Pen.Width:=3;

mC.Pen.Color:=RGB(255,255,255);

mC.Arc(wR.Left, wR.Top, wR.Right, wR.Bottom, wR.Left, wR.Top, wR.Left, wR.Top);

while k<>md.x0 do begin

k:=md.Prev[k];

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;

wr.Right:=cx+w;

wr.Top:=cy-h;

wr.Bottom:=cy+h;

mC.Pen.Width:=7;

mC.Pen.Color:=RGB(255,0,0);

mC.LineTo(cx,cy);

mC.Brush.Color:=RGB(0,255,0);

mC.Pen.Width:=3;

mC.Pen.Color:=RGB(255,255,255);

mC.Chord(wR.Left, wR.Top, wR.Right, wR.Bottom, wR.Left, wR.Top, wR.Left, wR.Top);

end;

end;

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

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

var d:Integer;

wr,wrG:TRect;

CR:TColor;

wd:Integer;

begin

wd:=14; //Перегородки

wr:=R[i,j];

wrG:=wr;

d:=3;

Inc(wr.Left,d);

Inc(wr.Top,d);

Dec(wr.Right,d);

Dec(wr.Bottom,d);

mC.Brush.Color:=C1;

mC.Pen.Width:=0;

mC.Pen.Color:=RGB(0,255,255);

mC.FillRect(wr);

CR:=RGB(255,128,255);

if md.Wr[i,j].L<>1 then

begin

mC.pen.Color:=CR; mC.Pen.Width:=wd;

mc.MoveTo(wr.Left,wr.Top+3);

mc.LineTo(wr.Left,wr.Bottom-3);

end;

if md.Wr[i,j].R<>1 then

begin

mC.pen.Color:=CR; mC.Pen.Width:=wd;

mc.MoveTo(wr.Right,wr.Top+3);

mc.LineTo(wr.Right,wr.Bottom-3);

end;

if md.Wr[i,j].U<>1 then

begin

mC.pen.Color:=CR; mC.Pen.Width:=wd;

mc.MoveTo(wr.Left+2,wr.Top);

mc.LineTo(wr.Right-2,wr.Top);

end;

if md.Wr[i,j].D<>1 then

begin

mC.pen.Color:=CR; mC.Pen.Width:=wd;

mc.MoveTo(wr.Left+2,wr.Bottom);

mc.LineTo(wr.Right-2,wr.Bottom);

end;

end;

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

При разработке программы применялся принятый в среде Delphi объектно-ориентированный подход для разработки интерфейса. При реализации алгоритмов обработки данных использовался структурный подход. В рабочем окне программы лабиринт занимает все пространство. Управление программой выполняется посредством меню приложения, расположенное в главном окне.

Назначение пунктов меню.

· «Компоненты» -- пункт меню содержит в себе две вкладки

ь «О программе» -- выбор пункта меню сопровождается вызовом диалога сообщения о разработчике приложения.

ь «Выход» -- пункт меню выхода из приложения.

· «Файл лабиринта» -- пункт меню позволяет выбрать различные лабиринты.

· «Вычислить» -- пункт меню находит кратчайший путь и рисует лабиринт и показывает найденный путь.

Если путь найден, он выдает сообщение и рисует лабиринт и найденный путь. Если путь не найден на экран выводится сообщения «Путь не найден», рисует лабиринт и путь который не достигает нужной точки.

Структура данных клеточной области лабиринта определяется в текстовом файле. Такие файлы -- это исходные данными приложения. Выбор файла данных лабиринта осуществляется в диалоге, вызов которого выполняется пунктом меню «Файл лабиринта».

Описание структуры данных файла лабиринта.

При подготовке данных условно ввели обозначения цифрой 8 для комнат лабиринта.

Дана цифра никак не используется. Однако она применяется для установки конфигурации перегородок между комнатами.

Например, комната 8 имеет перегородки сверху и снизу, а справа и слева они отсутствует.

Данные реального примера лабиринта

1 1 -- координаты начала пути

6 4 - координаты конца пути

7 6 - размерность матрицы

0 0 0 0 0 0 - верхние перегородки

0 8 1 8 1 8 0 8 0 8 0 8 0 - комнаты и боковые перегородки

1 1 1 1 0 1 - внутренние перегородки комнат

0 8 0 8 0 8 1 8 0 8 1 8 0

0 0 0 1 0 1

0 8 1 8 1 8 1 8 1 8 1 8 0

1 0 0 0 0 1

0 8 0 8 1 8 1 8 1 8 1 8 0

1 1 0 1 0 1

0 8 0 8 0 8 1 8 0 8 0 8 0

0 0 1 0 1 1

0 8 1 8 1 8 0 8 0 8 0 8 0

1 0 0 1 1 1

0 8 1 8 1 8 1 8 0 8 1 8 0

0 0 0 0 0 0

По этим данным выполнены тестовые расчеты, результаты которых приведены ниже в тестовом примере (рис.1).

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

Тестовый пример является расчетом кратчайшего пути в лабиринте.

Рис.1. Рабочее окно приложения - нахождения кратчайшего пути

Заключение

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

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

1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. Пособие. - Владивосток: Изд-во ДВГТ, 2000. - 288с.

2. Молчанова Л.А., Прудникова Л.И. Delphi в примерах и задачах: Учеб. пособие. Владивосток: Изд-во ТГЭУ, 2006. - 92с.