РЕАЛІЗАЦІЯ АЛГОРИТМУ ПОШУКУ ВИХОДУ З ЛАБІРИНТУ Текст наукової статті зі спеціальності «Комп'ютерні та інформаційні науки»

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Пусний Д. О.

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

Схожі теми наукових праць з комп'ютерних та інформаційних наук, автор наукової роботи - Пусний Д. О.

МЕТОДИ ТА МОДЕЛІ ГРУППОВОГО САМОВРЯДУВАННЯ РУХОМ КОЛЕКТИВУ РОБОТІВ З ОДНОЧАСНОЇ ЛОКАЛІЗАЦІЄЮ І ПОБУДУВАННЯМ КАРТИ ПЕРЕШКОД ЗА ДАНИМИ СКАНУЮЧИМИ ПРИСТРОЯМИ

ПРОГРАМНА СИСТЕМА ВІЗУАЛІЗАЦІЇ МАРШРУТІВ РУХУ РОБОТ ПО ОПТИМАЛЬНИМ ТРАЕКТОРІЯМ УСЕРЕДИНІ ПРОМИСЛОВОГО ЦЕХУ

IMPLEMENTATION OF EXIT SEARCH ALGORITHM FROM MAZE

Цей матеріал розкриває основні algorithms, що дозволить вам продовжити дорожку в різних способах. .

Текст наукової роботи на тему «РЕАЛІЗАЦІЯ АЛГОРИТМУ ПОШУКУ ВИХОДУ З ЛАБІРИНТУ»

Пусний Д.О., бакалавр напрям підготовки 02.03.03 «Математичне забезпечення та адміністрування інформаційних систем»

НДУ «БєлДУ» Росія, м. Білгород

РЕАЛІЗАЦІЯ АЛГОРИТМУ ПОШУКУ ВИХОДУ З ЛАБІРИНТУ

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

Ключові слова: алгоритм, лабіринт, шлях, граф, хвиля.

Pusny D.O., bachelor training direction 02.03.03 «Information Systems software and

administration» NRU "BelSU" Russia, Belgorod

IMPLEMENTATION OF EXIT SEARCH ALGORITHM FROM MAZE

Abstract: Ця стаття розказує про основні algorithms, що ви можете виконати шорстку ходу в різних випадках. Comparison of algorithms is carried out, and the most optimal according to the given parameters is selected. algoritm is shown in flowchart with results of it's work.

Keywords: algoritm, maze, way, graph, wave.

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

На даний момент відомо кілька основних алгоритмів пошуку шляху.

1. Правило «однієї руки» - суть якого полягає в русі лабіринтом, торкаючись правою або лівою рукою його стіни. Недоліком є ​​необхідність пройти довгий шлях, заходячи у всі безвиході, і

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

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

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

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

4. Алгоритм Дейкстри (також званий пошуком з рівномірною вартістю) – дозволяє нам ставити пріоритети дослідження шляхів.Замість рівномірного дослідження всіх можливих шляхів він віддає перевагу коліям з низькою вартістю. пошуку завширшки.

5. А* - це модифікація алгоритму Дейкстри, оптимізована для єдиної кінцевої точки. відстань від початку та оцінена відстань до мети.

Узагальнивши викладений матеріал, можна дійти невтішного висновку, що пошук завширшки, алгоритм Дейкстри і А* можуть знайти найкоротший маршрут до

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

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

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

Потім алгоритм перевіряє наявність виходу та йде далі, якщо він

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

Даний алгоритм був реалізований мовою програмування С++. Результати його роботи представлені на малюнку 1. Лабіринт задається «#», де виступає в ролі стіни. точками.

Малюнок 1 Консоль з виведеним лабіринтом та найкоротшим шляхом

1. Бережний, В.В. Дискретна математика/В.В. Бережний, А.В. Шапошников; Міністерство освіти і науки РФ, Федеральна державна автономна освітня установа вищої освіти «Північно-Кавказький федеральний університет». -Ставрополь: СКФУ, 2016. – 199 с. : іл.

2. Окулов, З. М. Основи програмування/Окулов С. М. М: БІНОМ. Лабораторія знань, 2012. 340С.

Математика та лабіринти: як знайти вихід із будь-якої головоломки за допомогою топології

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

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

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

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

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

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