Міністерство освіти і науки Російської Федерації
Агентство з освіти
Тихоокеанський державний економічний університет
Економічний інститут
Курсова робота
Пошук найкоротшого шляху в лабіринті
Виконав: Іванов Б.Н.
Владивосток 2009
Зміст
1. Введення
2. Формальна постановка задачі
3. Методи рішення
4. Модульна організація програми
4.1 Загальна схема взаємодії модулів
4.2 Опис модулів
5. Текст програми
6. Керівництво користувача
7. Тестовий приклад гри
Висновок
Список літератури
1. Введення
Умова розв'язуваної задачі дослівно за завданням звучить наступним чином: «Вибрано лабіринт, складений з кімнат, у кожній з якої є не менше однієї і не більше трьох дверей, що сполучають між собою різні кімнати. Одна з дверей називається входом в лабіринт, інша - виходом. Знайти найкоротший шлях від входу в лабіринт до його виходу ».
Метою представленої роботи є розробка програми "Пошук найкоротшого шляху", яке створює лабіринт і знаходить найкоротший шлях його проходження і відображає його.
Лабіринт задається у вхідному файлі, в тому ж файлі вказуються координати входу і виходу, і для початку роботи нам необхідно вибрати потрібний лабіринт, програма повинна видати розмір найкоротшого шляху, намалювати лабіринт і показати цей шлях.
Якщо ж шлях не знайдений програма видає повідомлення, про те що цей шлях не існує.
2. Формальна постановка задачі
Для програмної реалізації необхідно формалізувати структури даних завдання і розглянути методи її вирішення. Лабіринт ми задаємо у вхідному файлі матрицею, що складаються з 8, 0 і 1. Кожна запис масиву визначає кімнату лабіринту - вісімка характеризує саму кімнату і чотири координати навколо неї (0 - стіна або 1 - прохід) є чи немає прохід. Так само у вхідному файлі задаються координати входу, виходу і розмірність масиву. Саме з цим масивом працює програма при знаходженні шляху.
3. Методи вирішення задачі
Існує досить багато різних методів вирішення такого завдання, кожний з яких грунтується на своїх принципах і прийомах, має унікальні переваги і, відповідно, недоліки. У даній роботі був використаний метод знаходження найкоротшого шляху на графі.
Цей алгоритм визначає відстань між вершинами в простому орграфе з невід'ємними вагами. Якщо граф не зважений, то можна вважати, що всі ребра мають однакову вагу.
Візьмемо простий граф для кожного ребра визначимо вагу, тобто довжина будь-якого ребра більше 0. Знайдемо найкоротший шлях між вершинами які ми визначили як початку і кінець. Неіснуючі ребра будемо вважати ребрами з нескінченними вагами. Суму ваг ребер в дорозі будемо називати вагою або довжиною шляху. Алгоритм пошуку найкоротшого шляху, починаємо з вершини яку ми позначили як початок, переглядає граф у ширину позначаючи пройдені вершини значеннями-мітками їх відстані від початку. Мітки можуть бути тимчасові і остаточні. Остаточна мітка-це мінімально відстань на графі від початку до пройденої вершини. Таким чином, у кожен момент часу роботи алгоритму деякі вершини будуть мати остаточні мітки, а інша їх частина - тимчасові. Алгоритм закінчується, коли кінцева вершина отримує остаточну мітку, тобто відстані від початку до кінця.
Спочатку першій вершині присвоюється остаточна мітка 0 (нульове відстань до самої себе) а кожній з інших вершин присвоюється тимчасова мітка нескінченність. На кожному кроці мітки змінюються наступним чином.
Кожній вершині, що не має остаточної мітки, присвоюється нова тимчасова мітка - найменша з її тимчасовою і числа, якому привласнена остаточна мітка на попередньому кроці.
Визначається найменша з усіх часових міток, яка і стає остаточної міткою своєї вершини. У випадку рівності вибирається кожна з них.
Циклічний процес п.1 та п.2 продовжується до тих пір, поки кінцева вершина не отримає остаточної мітки. Легко бачити, що остаточна мітка кожної вершини - це найкоротший відстані між початковою і кінцевою вершинами.
4. Модульна організація програми
Реалізація проекту виконана в рамках трьох модулів. Кожен з них виконує певні для нього функції. Поділ функцій модулів виконано відповідно до завдань проекту. У загальному випадку поділ виконується на дві складові частини: проведення розрахунків і візуалізація отриманих даних.
4.1 Загальна схема взаємодії модулів
4.2 Опис модулів
Кожен з модулів реалізує свій клас. Опис модулів призиваються до опису класів (їх призначення) і методів класів (вирішення певних завдань класу).
1). UnWay - модуль реалізації класу TWay проведення всіх обчислення знаходження найкоротшого шляху.
Методи класу T Way.
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 квітня - координати кінця шляху
7 червня - розмірність матриці
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, яке знаходить в ньому найкоротший шлях і візуалізує його на формою додатка. Додаток є напівпрофесійним, допускає різні варіанти лабіринтів, настроюванням відповідних параметрів. Виконані численні тестові приклади дозволяють стверджувати, що надійність програмного забезпечення проекту досить висока.
Список літератури
Іванов Б.М. Дискретна математика. Алгоритми та програми: Учеб. Посібник. - Владивосток: Вид-во ДВГТ, 2000. - 288с.
Молчанова Л.А., Пруднікова Л.І. Delphi в прикладах і завданнях: Навч. посібник. Владивосток: Вид-во ТДЕУ, 2006. - 92с.