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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Робот у дерев'яному лабіринті

Є низка різних алгоритмів для розв'язування лабіринтів, тобто методів автоматичного пошуку виходу. Такі алгоритми, як метод випадкової поведінки миші, «триматися за стіну», застава (англ. Pledge) та алгоритм Тремо (англ. Trémaux) розроблені для проходження лабіринту мандрівником без попереднього вивчення лабіринту, тоді як алгоритми: заповнення тупиків та алгоритм найкоротшого шляху створені для використання людиною або комп'ютерною програмою, яка має можливість бачити й обробляти весь лабіринт одночасно.

Лабіринти, що не містять петель, відомі як «однозв'язні», або «досконалі» лабіринти, вони еквівалентні дереву в теорії графів. Отже, багато алгоритмів розв'язання лабіринту тісно пов'язані з теорією графів. Інтуїтивно, складаючи будь-який такий лабіринт, можна було б представити його у вигляді дерева.[1]

Алгоритм випадкової поведінки миші[ред. | ред. код]

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

Алгоритм «триматися за стіну»[ред. | ред. код]

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

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

Є пояснення ефективності алгоритму з топологічної точки зору. Якщо стіни з'єднані, то вони можуть бути деформовані в петлю або коло.[2] Тому «тримання за стіну» в такому випадку зводиться до ходьби по колу від початку до кінця. Далі звернемо увагу на те, що, після групування зв'язаних компонент стінок лабіринту, межі між ними будуть розв'язками, навіть якщо є більше ніж один роз'язок (див. малюнки праворуч).

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

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

Метод триматися за стіну може бути виконаний у тривимірному просторі або у лабіринтах вищих розмірностей, якщо його проміжки вищих розмірностей можуть бути спроектовані на звичайну двовимірну площину детерміністичним способом. Наприклад, якщо у тривимірному лабіринті шлях «угору» можна вважати, що проходи ведуть на північний захід, а шляхи «вниз» можуть вважатися проходами на південний схід, то можна застосовувати алгоритм тримання за стіну. Однак, на відміну від двовимірного лабіринту, цей випадок вимагає, щоб поточна орієнтація була відома, щоб визначити, який напрямок потрібно вважати першим: ліворуч або праворуч.

Алгоритм застави[ред. | ред. код]

Ліворуч: мандрівник, що повертає ліворуч потрапив у «пастку»
Праворуч: розв'язок алгоритмом застави

Лабіринти, що не мають розривів можна розв'язати методом «тримайся за стіну», доки вхід і вихід до лабіринту містяться на зовнішніх стінах лабіринту. Якщо, однак, мандрівник починає шлях всередині лабіринту, він може опинитися на ділянці, що не перетинається з виходом, і алгоритм послідовника стіни буде постійно обходити одне й те ж кільце. Алгоритм «Застава» (названий на честь Джона Заставного Ексетера) може вирішити цю проблему.[3][4]

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

Рука знімається зі стіни тільки тоді, коли «сума обертів» і «поточний курс» знаходяться на нулі. Це дозволяє алгоритму уникнути пасток, подібних до великої літери «G». Припускаючи, що алгоритм повертається ліворуч на першій стіні, він повертається на 360 градусів біля стіни. Алгоритм, який лише відстежує «поточний курс», призводить до нескінченного циклу, оскільки він залишає найнижчу крайню праву стінку зліва і знову проходить у вигнуту ділянку ліворуч. Алгоритм застави не залишає крайньої правої стіни, оскільки «сума зроблених обертів» не дорівнює нулю в цій точці (примітка, 360 градусів не дорівнює 0 градусам). Він слідує за стіною на всьому шляху, нарешті, проходячи її кут, що залишається за межами.

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

Алгоритм Тремо[ред. | ред. код]

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

Алгоритм Тремо, винайдений Шарлем П'єром Тремо,[5] є ефективним методом для виходу з лабіринту, який вимагає малювання ліній на підлозі для позначення шляху, і гарантовано працюватиме для всіх лабіринтів, які мають чітко визначені проходи,[6] але не гарантує знаходження найкоротшого маршруту.

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

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

Коли ви нарешті досягнете розв'язку, шляхи, позначені рівно один раз, покажуть шлях до початку. Якщо немає виходу, цей метод поверне вас до початку, де всі шляхи позначені двічі. У цьому випадку кожен шлях проходить точно двічі, один раз у кожному напрямку. Отримана ходьба називається двонаправленим подвійним трасуванням.[7]

По суті, цей алгоритм, який був відкритий у 19 столітті, використовувався близько ста років пізніше як пошук у глибину.[8][9]

Заповнення тупиків[ред. | ред. код]

Алгоритм заповнення тупиків — це алгоритм розв'язання лабіринтів, який заповнює всі хибні шляхи, залишаючи тільки правильні способи досягнути розв'язку незаповненими. Він може бути використаний для розв'язання лабіринту на папері або за допомогою комп'ютерної програми, але цей алгоритм не підходить для розв'язання в незнайомому лабіринті, оскільки цей метод дивиться на весь лабіринт відразу. Метод полягає в тому, щоб 1) знайти всі мертві кінці в лабіринті, а потім 2) «заповнити» шлях від кожного тупика до досягнення першого переходу. Зауважте, що деякі уривки не стануть частинами мертвих кінців, поки не будуть вилучені інші тупики. Відео про тупикове заповнення дії можна побачити тут: [1] [Архівовано 27 липня 2020 у Wayback Machine.][2] [Архівовано 6 лютого 2021 у Wayback Machine.].

Заповнення тупика не може випадково «відсікти» початок від фінішу, оскільки кожен етап процесу зберігає топологію лабіринту. Крім того, процес не припиниться «занадто рано», оскільки кінцевий результат не може містити жодних тупиків. Таким чином, якщо заповнення тупика відбувається на ідеальному лабіринті (лабіринт без петель), то залишається тільки розв'язок. Якщо це робиться на частковому лабіринті (лабіринт з деякими петлями), то всі можливі розв'язки залишаться, але крім них нічого більше.[3] [Архівовано 6 квітня 2019 у Wayback Machine.]

Рекурсивний алгоритм[ред. | ред. код]

Якщо дано повне уявлення про лабіринт, простий рекурсивний алгоритм може показати, як дістатися до кінця. Алгоритму буде дано початкове значення X і Y. Якщо значення X і Y не знаходяться на стіні, метод викликатиме себе з усіма суміжними значеннями X і Y, переконавшись, що він раніше не використовував ці значення X і Y. Якщо значення X і Y є значеннями кінцевого розташування, це збереже всі попередні екземпляри методу як правильний шлях. Ось приклад коду на Java: 

int[][] maze = new int[width][height]; // Лабіринт
boolean[][] wasHere = new boolean[width][height];
boolean[][] correctPath = new boolean[width][height]; // Розв'язок лабіринту
int startX, startY; // Початкові координати лабіринту
int endX, endY;     // Кінцеві координати лабіринту

public void solveMaze() {
    maze = generateMaze(); // Створити Лабіринт (1 = шлях, 2 = стіна)
    for (int row = 0; row < maze.length; row++)  
        // Встановлює булевим масивам значення за замовчуванням
        for (int col = 0; col < maze[row].length; col++){
            wasHere[row][col] = false;
            correctPath[row][col] = false;
        }
    boolean b = recursiveSolve(startX, startY);
    // Поверне булевий масив (correctPath) 
    // зі шляхом, позначеним значеннями "true".
    // Якщо змінна b має значення "false", то лабіринт не має розв'язків
}
public boolean recursiveSolve(int x, int y) {
    if (x == endX && y == endY) return true; // Якщо ви досягли кінця
    if (maze[x][y] == 2 || wasHere[x][y]) return false;  
    // Якщо дійшли стіни, або вже були на цьому місці
    wasHere[x][y] = true;
    if (x != 0) // Перевіряє, що не знаходиться на лівому краї
        if (recursiveSolve(x-1, y)) { // Викликає цю ж функцію для клітинки зліва
            correctPath[x][y] = true; // Позначає значення шляху як "true";
            return true;
        }
    if (x != width - 1) // Перевіряє, що не знаходиться на правому краї
        if (recursiveSolve(x+1, y)) { // Викликає цю ж функцію для клітинки зправа
            correctPath[x][y] = true;
            return true;
        }
    if (y != 0)  // Перевіряє, що не знаходиться на верхньому краї
        if (recursiveSolve(x, y-1)) { // Викликає цю ж функцію для клітинки згори
            correctPath[x][y] = true;
            return true;
        }
    if (y != height - 1) // Перевіряє, що не знаходиться на нижньому краї
        if (recursiveSolve(x, y+1)) { // Викликає цю ж функцію для клітинки знизу
            correctPath[x][y] = true;
            return true;
        }
    return false;
}

Алгоритм маршрутизації лабіринту[ред. | ред. код]

Алгоритм маршрутизації лабіринту[10] є методом низьких додаткових витрат, щоб знайти шлях між двома місцями лабіринту. Алгоритм спочатку призначався для застосування в багатоядерних процесорах і гарантував результат для будь-якого лабіринту побудованого на основі сітки. Окрім пошуку шляхів між двома місцями сітки (лабіринту), алгоритм може виявити, коли відсутній шлях між початковою і кінцевою точкою. Крім того, алгоритм може використовуватися внутрішнім мандрівником без попереднього знання лабіринту з фіксованим об'ємом пам'яті незалежно від розміру лабіринту; вимагає 4 змінних для пошуку розв'язку і виявлення недоступних місць. Варто пам'ятати, що алгоритм не шукає найкоротший шлях.

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

Point src, dst;// Координати початку і кінця
// cur вказує на теперішнє положення
int MD_best = MD(src, dst);// Зберігає найкращу дистанцію Мангеттенську відстань (MD)
// Продуктивний - той шлях, який робить Мангеттенську відстань меншою
while(cur != dst){
    if(існує продуктивний шлях){
        Взяти продуктивний шлях;
    }else{
        MD_best = MD(cur, dst);
        Уявити лінію між cur та dst;
        Взяти перший шлях, що знаходиться ліворуч або праворуч від лінії;// Вибір ліворуч або праворуч впливає на наступне правило
        while(MD(cur, dst) != MD_best || тут не існує продуктивного шляху){
            Використовувати правило правої або лівої руки;// Протилежна від обраної сторони лінії
    }
}

Алгоритм найкоротшого шляху[ред. | ред. код]

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

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

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. ↑ Maze to Tree на YouTube
  2. ↑ Maze Transformed на YouTube
  3. ↑ Abelson; diSessa (1980), Turtle Geometry: the computer as a medium for exploring mathematics
  4. ↑ Seymour Papert, «Uses of Technology to Enhance Education», MIT Artificial Intelligence Memo No. 298, June 1973
  5. ↑ Public conference, December 2, 2010 — by professor Jean Pelletier-Thibert in Academie de Macon (Burgundy — France) — (Abstract published in the Annals academic, March 2011 — ISSN 0980-6032)
    Charles Tremaux (° 1859 — † 1882) Ecole Polytechnique of Paris (X:1876), French engineer of the telegraph
  6. ↑ Édouard Lucas: Récréations Mathématiques Volume I, 1882.
  7. ↑ Even, Shimon (2011), Graph Algorithms (вид. 2nd), Cambridge University Press, с. 46—48, ISBN 978-0-521-73653-4, архів оригіналу за 23 лютого 2017, процитовано 22 березня 2019.
  8. ↑ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (вид. 3rd), Pearson Education, ISBN 978-0-201-36118-6.
  9. ↑ Fattah, Mohammad; et, al. (28 вересня 2015). A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips. NOCS '15 Proceedings of the 9th International Symposium on Networks-on-Chip. doi:10.1145/2786572.2786591.

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=Алгоритм_розв%27язування_лабіринтів&oldid=42200626