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

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

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

Лабіринт з двома рішеннями

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Лабіринт
• Алгоритм створення лабіринту
• Алгоритм Еллера генерації лабіринтів

• Think Labyrinth: Maze algorithms (деталі наведених у статті алгоритмів та інших алгоритмів розв'язування лабіринтів)(англ.)
• MazeBlog: Solving mazes using image analysis (англ.)
• Відео: Симуляція розв'язування лабіринту
• Simon Ayrinhac, Electric current solves mazes, © 2014 IOP Publishing Ltd. (англ.)