Алгоритми розв’язання лабіринтів

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

ВСТУП

Сучасній людині часто доводиться мати справу з великим обсягом даних. Такі масштабні задачі розв'язуються за допомогою різних підходів. Щоб визначити, який саме підхід необхідний в певній ситуації потрібно знати багато алгоритмів і мати альтернативні методи розв'язання.

В дискретній математиці та в теорії алгоритмів значне місце посідають алгоритми роботи з лабіринтами. Лабіринти - це так звані графи, які дають змогу візуально змоделювати практичні задачі. Лабіринти мають широке застосування в науці і техніці. За допомогою них психологи вивчають поведінку людей і тварин у повторюваних або екстремальних ситуаціях. Кібернетикам лабіринти допомагають конструювати ЕОМ, зокрема роботів, які мають здатністю до самонавчання. Одним з перших, хто проводив такі експерименти був американський математик Клод Шеннон(піддослідні мишки за допомогою певних алгоритмів знаходили вихід з лабіринту). Також за принципом лабіринту виготовляють глушителі в двигунах внутрішнього згорання, заповнюють частини деталей під високим тиском.

Актуальність даної теми полягає в тому, що алгоритм є не тільки центральним поняттям теорії алгоритмів, не тільки одним з головних понять математики взагалі, але одним з головних понять сучасної науки. Більш того, сьогодні, з настанням ери інформатики, алгоритми стають одним з найважливіших факторів цивілізації. Саме таке велике коло використання цього поняття і стало підґрунтям для вибору теми курсової роботи «Алгоритми розв'язання лабіринтів».

Метою курсової роботи є аналіз методів розв'язання лабіринтів та їх реалізація за допомогою мов програмування.

Об'єктом роботи виступають лабіринти та способи їх розв'язання за допомогою різноманітних алгоритмів.

Предметом курсової роботи є представлення лабіринту у пам'яті комп'ютера.

Для реалізації поставленої мети необхідно виконати наступні завдання:

літературу відповідної тематики;

проаналізувати позитивні та негативні аспекти алгоритму розв'язання лабіринту;

визначити побудову лабіринту за допомогою комп'ютера.

Структурно робота складається з вступу, трьох розділів, висновків, списку використаних джерел та викладена на 24 сторінках.



РОЗДІЛ I.ПРЕДСТАВЛЕННЯ ЛАБІРИНТІВ

1.1 Поняття лабіринту

Лабіринти - одна із складних ще не до кінця розв'язаних загадок історії. В давнину назву лабіринти (грец. Лбвэсйнипт) мали споруди зі складними заплутаними ходами, в які легко потрапити, і дуже важко знайти вихід. Першим про один з них повідомив історик Геродот(бл. 484-431 рр. до н. е.). У другій книжці свого знаменитого твору «Історія», він описав відвіданий ним велетенський Фаюмський лабіринт і розповів про його будову (рис. 1.1). Цей найдавніший з відомих лабіринтів був храмом, побудованим біля піраміди фараона Аменемхета ІІІ (1840-1792 рр. до н. е.).

Рис. 1.1 Фаюмський лабіринт

У різні часи ці дивні витвори у формі печер, палаців або споруд без покрівлі тощо з'являлись скрізь, де мешкала людина.

Найбільшого поширення набули лабіринти-головоломки. Для дітей давніх греків і римлян, такі розваги заповнювали дозвілля. Про що свідчать креслення, виявлені на стіні одного з будинків міста Помпеї, яке опинилось під попелом від виверження вулкана Везувій в 79 р. до н. е. З того часу і до наших днів ідея лабіринту постає в математиці все цікавішою і змістовнішою. Урізноманітнюються і форми лабіринтів. З'являються числові, об'ємні та інші. Історії лабіринтів присвячено багато наукових досліджень і популярних праць.

Загальний метод розв'язання задач про лабіринти запропонував у 1882 р. француз Тремо.

Увійшовши в лабіринт, будемо дотримуватись, наприклад правила правої руки. Дійшовши до перехрестя, йдемо в будь-якому напрямку, а якщо опинимося в тупику, повертаємось у вихідну точку. З неї прямуємо в той коридор, в якому ще не були. Робимо позначки для зручності на стінах коридору. Не можна входити в коридор, на обох стінах якого уже зроблено позначки про наше перебування. Правило Тремо можна перевірити, шукаючи шлях до позначених точками центрів квадратного і круглого лабіринтів.

До розв'язування задач про лабіринти можна застосувати елементи теорії графів. Коридори будемо позначати ребрами, а входи і виходи, тупики, кімнати і перехрестя - вершинами або вузлами (рис.1.2).

Рис. 1.2 Приклад графу

На такому графі легко визначити всі можливі маршрути, і в тому числі оптимальний. Але щоб граф міг подати вичерпну інформацію, потрібно уважно позначити всі елементи лабіринту і зобразити їх відповідними елементами графа. Для складних лабіринтів - це досить клопітка робота.

Залежно від того, парна чи непарна кількість ребер сходиться у вузлі графа, вузли називаються, відповідно, парними або непарними. Легко довести, що коли граф зовсім немає вузлів, або має небільше як два непарних вузли, його можна накреслити не відриваючи олівця від паперу і не проводячи двічі ліній по одному і тому самому ребру. Лінії, які можна так накреслити, називаються унікурсальними.

Звідси випливає, що далеко не всі лабіринти можна обійти так, щоб проходити кожним коридором лише один раз. Така подорож можлива лише по лабіринту, графом якого є унікурсальна лінія.

Лабіринт - заплутана мережа доріжок, ходів та комірок, які сполучаються між собою. Наші лабіринти - плоскі, тому їх можна легко зобразити на папері. Крім того. Всі комірки, а їх називають локаціями, будуть квадратними, а сам лабіринт прямокутним. У кожної такої комірки є не більш ніж чотири сусідні, і в кожну сусідню комірку може вести хід ( а може і не вести - в цьому випадку там буде «стіна» ).

За приклад візьмемо рис. 1.3

Рис. 1.3 Прямокутний лабіринт

Саме з лабіринтами такого типу ми і будемо працювати.

1.2 Представлення лабіринтів у пам'яті комп'ютера

Отже, як представити лабіринт у пам'яті комп'ютера?

Потрібно просто створити двовимірний масив з нулів і одиниць: за нуль візьмемо стіну, а одиниця позначатиме прохід (рис. 1.4).

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

00000

01110

00010

01110

00000

Рис. 1.4 Просте представлення лабіринту в пам'яті

Малювати стінки при виведенні на екран потрібно тонкими лініями. Цей спосіб дозволяє описати будь-який лабіринт нашого типу. Але у нього є істотний недолік: якщо зруйнувати будь-яку стіну (тобто поміняти нуль на одиницю), на місці зруйнованої стіни в лабіринті утворюється нова локація. При руйнуванні стіни повинен відкриватися хід, але ніяк не утворюватися нова локація. Тому нам доведеться скористатися не таким простим і зручним, зате позбавленим цього недоліку методом.

У кожній локації лабіринту може існувати від однієї до чотирьох стін (зверху, знизу, зліва і справа).

При цьому не можна забувати про правило: лабіринт завжди по краях повинен бути обмежений стіною.

1.3 Завантаження/збереження лабіринту.

Надалі розглянемо процедури завантаження/збереження лабіринту.

Напишемо їх раз. Оскільки поки що у нас немає можливості згенерувати лабіринт автоматично. То варто зберігати його в текстовому файлі - так, принаймні можна вручну створити який-небудь тестовий приклад. Структура файлу буде простою. У першому рядку запишемо два числа - ширину і висоту лабіринту. Потім у файлі буде ще стільки ж рядків, скільки локацій у лабіринті. У будь-якому з цих рядків буде зберігатися пара чисел, кожне з яких рівне або нулю, або одиниці. Перше число показує наявність стіни зверху, а друге - стіни зліва в поточній локації. Локації зберігаються послідовно, рядок за рядком.

Залишається з'ясувати, що ж робити з додатковими, «службовими» локаціями, які обмежують лабіринт справа і знизу. Дійдемо до того, що вони все-таки не є частиною лабіринту. Якщо розміри поля рівні 10 х 20, то і у файлі будуть записані ці числа, а загальна кількість збережених локацій виявиться рівною 10 х 20 - 200. Реально ж в пам'яті зберігатиметься матриця 11 х 21, але у файлі службові локації зберігати не потрібно.

Зовнішній вигляд маленького лабіринту показаний на рис. 1.5

Рис. 1.5 Простий лабіринт



РОЗДІЛ II.РОЗВ'ЯЗАННЯ ЛАБІРИНТУ

2.1 Розв'язання лабіринту

Отже, лабіринт створений і завантажений у пам'ять комп'ютера. Тепер потрібно навчитись розв'язувати його. Під розв'язуванням мається на увазі пошук шляху з деякої стартової локації в іншу(фінішну). Стартова і фінішна локації не фіксовані, тобто ми можемо спробувати вирішити лабіринт для будь-якої пари локацій. Ми зупинимось на двох найбільш популярних і часто використовуваних методах: рекурсивному обході і алгоритмі хвильового трасування.

2.2 Рекурсивний обхід

Рекурсія - спосіб організації обробки даних, за якого програма викликає безпосередньо сама себе, або з інших програм.

А якби стала вирішувати лабіринт людина? Оскільки у мене немає ідей щодо цього, залишається одне: послідовно вивчати лабіринт, поки не натраплю на шлях, який може вивести до фінішної локації. Якщо шлях проходить по коридору, від якого немає розгалужень, треба йти вперед; цікаве починається, коли ми знаходимось на перехресті. Потрібно вчинити так: відзначити який-небудь з можливих шляхів і рухатись по ньому, якщо доведеться повернутися, то зможемо вибрати вже інший шлях.

Якщо на шляху зустрілась фінішна локація - кінець алгоритму. При цьому не потрібно забувати відзначати свій шлях, щоб знати, яким саме чином ми сюди потрапили.

На жаль, набагато частіше, ми будемо зустрічатися не з фінішною локацією, а з безвихіддю. Безвихідь буває двох видів: або просто нікуди йти( в кінці коридору глуха стіна), або там, де ми вже були. Друге означає, що в маршруті утворилася петля і ніякого сенсу йти по знайомих маршрутах немає. В цьому випадку простіше всього зробити крок назад, забувши про те, що ми вже відвідували поточну локацію, і вибрати інший шлях. Якщо крок назад нічого не дає, зробити ще один, а якщо знадобиться, то ще декілька кроків назад, до тих пір поки не з'явиться альтернатива. Якщо всі варіанти вичерпані, а рішення так і не знайдено, це означає, що його просто не існує(наприклад, фінішна локація повністю оточена стіною).

Ось і весь алгоритм. Є просте правило: якщо хочеш вийти з лабіринту, завжди, що б не трапилося, тримайся по праву руку(можна і по ліву руку, але головне - не змінювати своєї тактики).

Рис 2.1 Розв'язок, знайдений за допомогою рекурсивного обходу

Принцип роботи рекурсивного обходу більш менш ясний. Зараз розглянемо його недоліки, а потім перейдемо до алгоритму хвильового трасування.

Недоліки алгоритму:

а) він обходить лабіринт нераціонально(може пройти досить багато часу, поки розв'язок буде не оптимальний);

б) одержаний розв'язок може бути не оптимальним.

Рис 2.2Проблематичний лабіринт для процедури рекурсивного обходу

лабіринт трасування алгоритм

2.3 Алгоритм хвильового трасування

В даний час використовуються різні варіанти хвильового алгоритму, зокрема променевий і маршрутні. Простим видом хвильового алгоритму є хвильовий алгоритм знаходження найкоротшого шляху без перетину безлічі зайнятих і заборонених елементів. Його доцільно використовувати при трасуванні з'єднань в одній площині, коли неприпустимо виходити з меж цієї площини. Визначаються початкова і кінцева крапки і моделюється розповсюдження хвилі від кінцевої крапки до початкової у напрямі хвилі. Недоліком цього алгоритму є те, що він мало придатний для трасування багатошарової друкарської плати, значне число довгих паралельних провідників є причиною великої взаємоіндуктивності.

Досконалішим алгоритмом є хвильовий алгоритм прокладки шляху з мінімальним числом перетину. У цьому випадку число перетинів раніше прокладених трас повинне бути мінімальним. Для подолання недоліку цього алгоритму, при якому траси прагнуть до однієї ж плати і притискаються один до одного, був запропонований алгоритм для проведення шляху, мінімально що наближаються до інших трас.

Основою алгоритму є умова, при якому елементи даного з'єднання повинні мати мінімум сусідніх елементів, що належать раніше прокладеним трасам. Якщо однією з умов є вимога регулярності з'єднань (один шар горизонтальні, інший - вертикальні і т.п.), то зручніше використовувати хвильовий алгоритм прокладки шляху з мінімальним числом змін напряму, який дозволяє мінімізувати кількість міжшарових з'єднань.

А як би стала вирішувати лабіринт людина? Зрозуміло, що копіювання людських дій - не єдиний спосіб досягнення розв'язку; цілком можна застосувати і інші моделі поведінки. Наприклад, таку: уявимо, що в стартовій локації ми перекинули бочку води ( а ще краще, густого киселю). Рідина починає розтікатися по сторонах, поступово добираючись навіть до найвіддаленіших локацій лабіринту. Рано чи пізно вода досягне і фінішної локації: в цьому випадку треба прослідити, яким чином рідина туди потрапила - а це і буде маршрут від старту до фінішу (причому найкоротший! ). Якщо киселю вже нікуди текти, а фінішна локація гак і не досягнута, це означає, що розв'язку не існує. Моделюванням такої поведінки займається алгоритм хвильового трасування.

Помітимо спочатку всі локації лабіринту нулями (це означає «локація не містить киселю»). Стартову локацію помітимо одиницею (вилили кисіль). Тепер виконуємо дії:

знайти в лабіринті локації, помічені одиницями;

для кожної з чотирьох сусідніх з нею локацій, перевірити дві умови:

а) чи помічена вона нулем;

б) чи є стіна між двома локаціями (вибраної і сусідньої), якщо обидві умови виконані, позначимо сусідню локацію двійкою.

Малюнок 2.3 ілюструє сказане.

Рис2.3 Перша ітерація алгоритму хвильового трасування

Ітерація - такий спосіб організації обробки даних, за якого деякі дії багатократно повторюються, не зумовлюючи рекурсивних викликів програм.

Із стартової позиції можна потрапити лише в локацію, розташовану знизу від неї. Оскільки вона помічена нулем, записуємо двійку. Друга ітерація алгоритму виглядає так:

знайти в лабіринті локації помічені двійками;

для кожної з чотирьох сусідніх локацій перевірити ті ж умови;

якщо обидві умови виконані, то помічаємо сусідню локацію трійкою.

На N-й ітерації нам доведеться виконати дії:

а) знайти в лабіринті локації, помічені числом N;

б) для кожної з чотирьох сусідніх з нею локацій перевірити ті ж умови;

в) якщо обидві умови виконані, позначаємо сусідню локацію числом N + 1.

1	0	9	8	9
2	3	8	7	8
3	4	5	6	7
6	5	6	7	8

Рис 2.4 Результат роботи алгоритму хвильового трасування



Якщо на якійсь ітерації ми досягли фінішної локації (фінішна - права верхня локація лабіринту), робота алгоритму закінчується. Якщо протягом ітерації ми не зуміли зайняти жодної нової клітинки, розв'язку не існує.

Якщо розв'язок знайдений на N-й ітерації (у нашому випадку - на восьмій), фінішна локація помічена числом N + 1. Тепер залишилося лише визначити власне шлях. Зробити це нескладно: у фінішну локацію (номер N + 1) ми потрапили з тієї сусідньої локації, яка має номер 14; у свою чергу, в неї можна потрапити з локації з номером N - 1 і т.д. Якщо в процесі визначення шляху ми знайшли дві локації, звідки можна було потрапити в поточну, можна вибрати будь-яку з них - обидва маршрути будуть оптимальними. Зрозуміло, треба стежити, щоб між сусідніми локаціями маршруту не було стіни.

Поговоримо тепер про якості алгоритму хвильового трасування. Його позитивні сторони: він простий (напевно, навіть простіший, ніж рекурсивний обхід), різниця пов'язана із залами і знаходить оптимальний розв'язок (причому дуже швидко).У нього є і істотна негативна сторона: на кожній ітерації доводиться досліджувати весь лабіринт цілком, визначаючи, яким числом помічена та або інша локація. Якщо ми маємо справу з великим лабіринтом, цей недолік може швидко стати критичним. Інший недолік - велика витрата пам'яті: доводиться мати двовимірний масив з мітками локацій. У принципі, при рекурсивному обході ми теж використовували подібний масив, щоб визначити, чи була відвідана локація раніше чи ні; проте тут ситуація інша. У разі рекурсивного обходу можна просто зберігати координати відвіданих локацій в списку, економлячи тим самим пам'ять, зараз же такий прийом не допоможе: кількість міток дуже швидко розростається, покриваючи істотну частину всього лабіринту.



Розділ III.Пошук маршруту у графі

3.1 Зважені графи

У реальних задачах на графах часто потрібно брати до уваги додаткову інформацію - відстань між окремими пунктами, вартість проїзду, час проїзду тощо. Для цього використовують поняття зваженого графа.

Зваженим називають граф, кожному ребру e якого приписано дійсне число w(e). Це число називають вагою ребраe. Аналогічно означають зваженийорієнтований граф:це такий орієнтований граф,кожній дузіeякого приписане дійсне числоw(e),яке називаєтьсявагою дуги.

Розглянемо два способи зберігання зваженого графа G = (V, E) в пам' яті комп' ютера.

Нехай |V| = n, |E| = m.

Перший - подання графу матрицею ваг W, яка являє собою аналог матриці суміжності. Її елемент wij = w(vi, vj), якщо ребро або дуга (vi, vj) ОE. Якщо ж ребро або дуга (vi, vj) ПE, то wij= 0чи wij=Ґзалежно від розв'язуваної задачі.

Другий спосіб - поданням графу списком ребер. Для зваженого графу під кожний елемент списку E можна відвести три комірки - дві для ребра й одну для його ваги, тобто всього потрібно 3m комірок.

Довжиною шляху в зваженому графі називають суму ваг ребер

(дуг), які утворюють цей шлях. Якщо граф не зважений, то вагу кожного ребра (кожної дуги) уважають рівною одиниці та отримають раніше введене поняття довжини шляху як кількості ребер (дуг) у ньому.



3.2 Алгоритм Дейкстри

Задача про найкоротший шляхполягає в знаходженні найкоротшого шляху відзаданої початкової вершини a до заданої вершини z. Наступні дві задачі - безпосередні узагальнення сформульованої задачі про найкоротший шлях.

Для заданої початкової вершини a знайти найкоротші шляхи від a до всіх інших вершин.

Знайти найкоротші шляхи між усіма парами вершин.

Виявляється що майже всі методи розв' язання задачі про найкоротший шлях від заданої початкової вершини a до заданої вершини z також дають змогу знайти й найкоротші шляхи від вершини a до всіх інших вершин графа. Отже, за їх допомогою можна розв' язати задачу 1 із невеликими додатковими обчислювальними витратами. З іншого боку, задачу 2 можна розв' язати або n разів застосувавши алгоритм задачі 1 із різними початковими вершинами, або один раз застосувавши спеціальний алгоритм.

Найефективніший алгоритм визначення довжини найкоротшого шляху від фіксованої вершини до будь-якої іншої запропонував 1959 р. датський математик Е. Дейкстра. Цей алгоритм застосовується лише тоді, коли вага кожного ребра (дуги) додатна. Опишемо докладно цей алгоритм для орієнтованого графа.

Нехай G = (V, E) - зважений орієнтований граф, w(vi, vj) - вага дуги (vi, vj). Почавши з вершини a, знаходимо віддаль від a до кожної із суміжних із нею вершин. Вибираємо вершину, відстань від якої до вершини a найменша; нехай це буде вершина v*. Далі знаходимо відстані від вершини a до кожної вершини суміжної з v* вздовж шляху, який проходить через вершину v*. Якщо для якоїсь із таких вершин ця відстань менша від поточної, то замінюємо нею поточну відстань. Знову вибираємо вершину, найближчу до a та не вибрану раніше; повторюємо процес.

Описаний процес зручно виконувати за допомогою присвоювання вершинам міток. Фіксованою початковою вершиною вважаємо вершину a; довжину найкоротшого шляху шукаємо до вершини z (або до всіх вершин графа). Тепер формально опишемо алгоритм Дейкстри.

Крок1

Ініціалізація. Відстань до всіх вершин графа V = . Відстань до а = 0. Жодна вершина графа ще не опрацьована.

Крок 2

Знаходимо таку вершину (із ще не оброблених), поточна найкоротша відстань до якої мінімальна. В нашому випадку це вершина 1. Обходимо всіх її сусідів і, якщо шлях в сусідню вершину через 1 менший за поточний мінімальний шлях в цю сусідню вершину, то запам'ятовуємо цей новий, коротший шлях як поточний найкоротший шлях до сусіда.

Крок 3

Перший по порядку сусід 1-ї вершини -- 2-а вершина. Шлях до неї через 1-у вершину дорівнює найкоротшій відстані до 1-ї вершини + довжина дуги між 1-ю та 2-ю вершиною, тобто 0 + 7 = 7. Це менше поточного найкоротшого шляху до 2-ї вершини, тому найкоротший шлях до 2-ї вершини дорівнює 7.

Кроки 4, 5

Аналогічну операцію проробляєм з двома іншими сусідами 1-ї вершини -- 3-ю та 6-ю. 

Крок 6

Всі сусіди вершини 1 перевірені. Поточна мінімальна відстань до вершини 1 вважається остаточною і обговоренню не підлягає (те, що це дійсно так, вперше довівДейкстра). Тому викреслимо її з графа, щоб відмітити цей факт. 

Крок 7

Практично відбувається повернення до кроку 2. Знову знаходимо «найближчу» необроблену (невикреслену) вершину. Це вершина 2 з поточною найкоротшою відстанню до неї = 7. І знову намагаємося зменшити відстань до всіх сусідів 2-ої вершини, намагаючись пройти в них через 2-у. Сусідами 2-ої вершини є 1, 3, 4.

Перший (по порядку) сусід вершини № 2 -- 1-а вершина. Але вона вже оброблена (або викреслена -- див. крок 6). Тому з 1-ою вершиною нічого не робимо.

Крок 8 (з іншими вхідними данними)

Інший сусід вершини 2 -- вершина 4. Якщо йти в неї через 2-у, то шлях буде = найкоротша відстань до 2-ої + відстань між 2-ою і 4-ою вершинами = 7 + 15 = 22. Оскільки 22 < ?, встановлюємо відстань до вершини № 4 рівним 22. 

Крок 9

Ще один сусід вершини 2 -- вершина 3. Якщо йти в неї через 2-у, то шлях буде = 7 + 10 = 17. Але 17 більше за відстань, що вже запам'ятали раніше до вершини № 3 і дорівнює 9, тому поточну відстань до 3-ої вершини не міняємо. 

Крок 10

Всі сусіди вершини 2 переглянуті, заморожуємо відстань до неї і викреслюємо її з графа. 

Кроки 11 -- 15

По вже «відпрацьованій» схемі повторюємо кроки 2 -- 6. Тепер «найближчою» виявляється вершина № 3. Після її «обробки» отримаємо такі результати:

Наступні кроки

Проробляємо те саме з вершинами, що залишилися (№ по порядку: 6, 4 і 5).

Алгоритм закінчує роботу, коли викреслені всі вершини. Результат його роботи видно на останньому малюнку: найкоротший шлях від 1-ої вершини до 2-ої становить 7, до 3-ої -- 9, до 4-ої -- 20, до 5-ої -- 20, до 6-ої -- 11 умовних одиниць.

3.3 Реалізація алгоритму Дейкстри

У ній використовується масив відстаней та масив позначок. На початку алгоритму відстані заповнюються великим позитивним числом (більшим максимального можливого шляху в графі), а масив позначок заповнюється нулями. Потім відстань для початкової вершини вважається рівною нулю і запускається основний цикл.

На кожному кроці циклу ми шукаємо вершину з мінімальною відстанню і прапором рівним нулю. Потім ми встановлюємо в ній позначку 1 і перевіряємо всі сусідні з нею вершини. Якщо в ній відстань більша, ніж сума відстані до поточної вершини і довжини ребра, то зменшуємо його. Цикл завершується коли позначки всіх вершин стають рівними 1.

Розглянемо конкретно на прикладі як реалізується цей метод на мові C++.

#include"stdafx.h"

#include<iostream>

usingnamespace std;

constint V = 6;

//алгоритмДейкстры

void Dijkstra(intGR[V][V], intst)

{

int distance[V], count, index, i, u, m = st + 1;

bool visited[V];

for (i = 0; i<V; i++)

{

distance[i] = INT_MAX; visited[i] = false;

}

distance[st] = 0;

for (count = 0; count<V - 1; count++)

{

int min = INT_MAX;

for (i = 0; i<V; i++)

if (!visited[i] && distance[i] <= min)

{

min = distance[i]; index = i;

}

u = index;

visited[u] = true;

for (i = 0; i<V; i++)

if (!visited[i] &&GR[u][i] && distance[u] != INT_MAX&&

distance[u] + GR[u][i]<distance[i])

distance[i] = distance[u] + GR[u][i];

}

cout <<"Стоимость пути из начальной вершины до остальных:\t\n";

for (i = 0; i<V; i++) if (distance[i] != INT_MAX)

cout << m <<" > "<< i + 1 <<" = "<< distance[i] << endl;

else cout << m <<" > "<< i + 1 <<" = "<<"маршрутнедоступен"<< endl;

}

//главнаяфункция

void main()

{

setlocale(LC_ALL, "Rus");

int start, GR[V][V] = {

{ 0, 1, 4, 0, 2, 0 },

{ 0, 0, 0, 9, 0, 0 },

{ 4, 0, 0, 7, 0, 0 },

{ 0, 9, 7, 0, 0, 2 },

{ 0, 0, 0, 0, 0, 8 },

{ 0, 0, 0, 0, 0, 0 } };

cout <<"Начальнаявершина>> "; cin >> start;

Dijkstra(GR, start - 1);

system("pause>>void");

}

ВИСНОВОК

Для представлення лабіринту у пам'яті комп'ютера створюється двовимірний масив з нулів та одиниць: нуль позначає стіну, одиниця прохід.

Процедуру завантаження лабіринту автор виклав у даній роботі наступним чином. У першому ряду пишеться два числа -- ширину і висоту лабіринту, потім у файлі ще стільки ж рядів, скільки локацій у лабіринті. Локації зберігаються послідовно, рядок за рядком.

Автор розглянув два методи розв'язування лабіринтів: рекурсивний обхід і метод хвильового трасування.Рекурсивний обхід є простим і популярним, але він обходить лабіринт нераціонально, потребує великої затрати часу, і отриманий розв'язок може бути не оптимальним. Алгоритм хвильового трасування є простим і знаходить оптимальний розв'язок, причому досить швидко.

У курсовій роботі розглянуто алгоритми побудови лабіринтів за допомогою комп'ютера, зокрема алгоритм Дейкстри. Алгоритм знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.



СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

Глинський Я.М. Алгоритмізація і програмування / Я.М. Глинський. - Л.: Деол, 2003. - 200 с.

Мозговой М. В. Занимательное программирование: Самоучитель / М.В. Мозговой. - СПб.: Питер, 2005. - 208с.

Савченко В.А. Методи розв'язування задач перебору варіантів: готуємося до олімпіади // Інформатика. - 2004. - №8 (248), лютий. - С. 15 - 18.

Савченко В.А. Рекурсивні алгоритми // Інформатика. - 2004. - №4 (244), січень. - С. 11 - 16.

Скляр А.Б. Методи обминання перешкод // Інформатика. - 2005. - №6 (294), лютий. - С. 17 - 20.

Размещено на Allbest.ru

...