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

Є низка різних алгоритмів для розв'язування лабіринтів, тобто методів автоматичного пошуку виходу. Такі алгоритми, як метод випадкової поведінки миші, «триматися за стіну», застава (англ. 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* використовує евристичну техніку. Алгоритм пошуку по ширині використовує чергу, щоб відвідати клітини в збільшеному порядку відстані від початку до кінця. Кожна відвідувана комірка повинна відстежувати свою відстань від початку або яка сусідня комірка ближче до початку викликала її додавання до черги. Коли знайдено кінцеве розташування, алгоритм проходить по шляху від кінця до початку, знаходячи найкоротший шлях. Пошук у ширину в найпростішій формі має свої обмеження, як пошук найкоротшого шляху у зважених графах.

Див. також

Примітки

↑ Maze to Tree на YouTube
↑ Maze Transformed на YouTube
↑ Abelson; diSessa (1980), Turtle Geometry: the computer as a medium for exploring mathematics
↑ Seymour Papert, «Uses of Technology to Enhance Education», MIT Artificial Intelligence Memo No. 298, June 1973
↑ 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
↑ Édouard Lucas: Récréations Mathématiques Volume I, 1882.
↑ H. Fleischner: Eulerian Graphs and related Topics. In: Annals of Discrete Mathematics No. 50 Part 1 Volume 2, 1991, page X20.
↑ Even, Shimon (2011), Graph Algorithms (вид. 2nd), Cambridge University Press, с. 46—48, ISBN 978-0-521-73653-4, архів оригіналу за 23 лютого 2017, процитовано 22 березня 2019.
↑ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (вид. 3rd), Pearson Education, ISBN 978-0-201-36118-6.
↑ 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.

Посилання

Think Labyrinth: Maze algorithms [Архівовано 6 квітня 2019 у Wayback Machine.] (деталі наведених у статті алгоритмів та інших алгоритмів розв'язування лабіринтів)(англ.)
MazeBlog: Solving mazes using image analysis [Архівовано 20 вересня 2015 у Wayback Machine.] (англ.)
Відео: Симуляція розв'язування лабіринту [Архівовано 13 грудня 2016 у Wayback Machine.]
Simon Ayrinhac, Electric current solves mazes, © 2014 IOP Publishing Ltd. (англ.)

[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

[Récréations_Mathématiques-6] Édouard Lucas: Récréations Mathématiques Volume I, 1882.

[Eulerian_Graphs_and_related_Topics-7] H. Fleischner: Eulerian Graphs and related Topics. In: Annals of Discrete Mathematics No. 50 Part 1 Volume 2, 1991, page X20.

[8] Even, Shimon (2011), Graph Algorithms (вид. 2nd), Cambridge University Press, с. 46—48, ISBN 978-0-521-73653-4, архів оригіналу за 23 лютого 2017, процитовано 22 березня 2019.

[9] Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (вид. 3rd), Pearson Education, ISBN 978-0-201-36118-6.

[10] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]