Загрузка...
Учебная работа. Курсовая работа: Поиск кратчайшего пути в лабиринте 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. Модульная организация приложения
Реализация проекта выполнена в рамках 3-х модулей. Любой из их делает определенные для него функции. Разделение функций модулей выполнено в согласовании с задачками проекта. В общем случае разделение производится на две составные части: проведение расчетов и визуализация приобретенных данных.
4.1 Общая схема взаимодействия модулей
4.2 Описание модулей
Любой из модулей реализует собственный класс. Описание модулей призываются к описанию классов (их предназначения) и способов классов (решения определенных задач класса).
1). UnWay — модуль реализации класса TWay проведения всех вычисления нахождения кратчайшего пути.
Way
Procedure TWay.Input — процедура ввода перегородок комнаты
Procedure TWay.CreateAdj — процедура формирование матрицы смежности комнат
Procedure TWay.ShortRoom – процедура поиска малого пути
2). UnDraw — модуль реализации класса 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;
// процедура ввода перегородок комнаты
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 = 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с.
]]>