Аналіз алгоритмів пошуку шляху та реалізація оптимального алгоритму засобами Action Script 3

ВСТУП 8
РОЗДІЛ 1. ОГЛЯДОВИЙ АНАЛІЗ ОСНОВНИХ ВИДІВ АЛГОРИТМІВ ПОШУКУ ШЛЯХУ І ЇХ ЕФЕКТИВНОСТІ. 12
1.1. Постановка завдання 13
1.2. Прості алгоритми обходу перешкод 13
1.3. Основні поняття теорії графів 16
1.3.1. Основні види графів 17
1.3.2. Способи завдання графів 18
1.4. Алгоритми пошуку шляхів на графах 19
1.4.1. Пошук з поверненням 20
1.4.2. Алгоритм Флойда-Уоршелла 21
1.5. Алгоритм А* і його окремі випадки 23
1.5.1. Алгоритм А* 24
1.5.2. Алгоритм Дейкстры 25
1.5.3. Пошук завширшки 28
1.5.4. Пошук в глибину 31
1.5.5. Двонаправлений пошук 33
1.6. Результати теоретичного порівняння якості алгоритму 34
1.6.1. Тимчасова характеристика 34
1.6.2. Висновок і рекомендації по використанню пошукових алгоритмів в ігрових завданнях 35
РОЗДІЛ 2. ПРОГРАМНА РЕАЛІЗАЦІЯ ОСНОВНИХ ПОШУКОВИХ АЛГОРИТМІВ І ОЦІНКА ЇХ ЕФЕКТИВНОСТІ 36
2.1. Базові поняття оцінки алгоритму і написання програми 36
2.1.1. Оцінка ефективності алгоритму 36
2.1.2. Короткий опис мови програмування ActionScript 3.0 38
2.2. Прості алгоритми для вирішення завдання пошуку шляху. 39
2.1.2. Розробка простого алгоритму 39
2.2.1. Тимчасова характеристика роботи алгоритму 47
2.3. Хвилевий алгоритм 50
2.4. Реалізація і оцінка Алгоритму A* 58
2.5. Висновки до розділу 65
РОЗДІЛ 3. ОХОРОНА ПРАЦІ 66
3.1. Характеристика умов праці програміста 66
3.2. Ергономічні вимоги до робочого місця 67
3.1. Загальні вимоги безпеки 72
ВИСНОВКИ 74

Актуальність.
Завдання про знаходження найкоротшого шляху є одним з класичних завдань теорії графів. Це завдання має досить велику кількість реалізацій. Пошуком найбільш оптимальних алгоритмів її рішення займалися видатні математики і програмісти чиї імена звучать в назвах розроблених ними алгоритмів пошуку рішення цієї задачі. Сфера застосування пошукових алгоритмів досить велика від розрахунків для виготовлення друкованих плат до рішення економічних завдань ("завдання комівояжера").
Пошукові алгоритми використовуються практично у всіх сферах діяльності людини, де необхідно знайти оптимальне рішення з багатьох інших. Вміло використання пошукових алгоритмів дає немалий економічний ефект.
Нове звучання пошукові алгоритми отримали в ігровій індустрії. Більше того, слід зазначити, що саме в рішеннях ігрових завдань виникли найбільш оптимальні рішення пошуку найкоротшого або оптимального шляху (для зважених графів). Тому розгляд пошукових алгоритмів, на наш погляд, доцільно проводити саме з точки зору ігрової індустрії.
При розробці комп'ютерних ігор аркадного, шутерного, квестового і деяких інших типів часто виникає необхідність прокласти курс з пункту A в пункт Би через ігрове поле з відміченими непрохідними областями (будовами, перешкодами, зонами і т. д).
Завдання знаходження найкоротшого шляху між деякими точками A і В на ігровому полі з довільно розташованими перешкодами характерна, в першу чергу, для тактичних і стратегічних ігор, а також як в RPG, квестaх, в деяких логічних іграх, тобто присутній практично в усіх жанрах.
У будь-якому випадку персонаж, об'єкт і так далі повинні переміщатися по ігровому полю, використовуючи найкоротший шлях, причому, якщо таких шляхів декілька, то вибір одного з них в загальному випадку не принциповий. Ігрове поле зазвичай представляється у вигляді дискретної простої або ізометричної сітки, переміщення по ньому зводиться до переміщення по клітинах карти, яким відповідають певні координати. В цьому випадку зазвичай...

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