Упрощение пути LSRB для роботов в линейном лабиринте

Робот, который проходит линейный лабиринт только по правилу левой руки, всегда достигнет финиша, но всегда выберет нелепый маршрут: спустится в каждый тупик, выйдет обратно и будет бродить по ветвям, которые никуда не ведут. LSRB — приём, который превращает этот первый неуклюжий проход в оптимальный второй, используя почти никакой памяти и вообще никакой карты.

Ему нужен один массив символов. Это вся структура данных.

Четыре символа

Каждый раз, когда робот покидает разветвление, он добавляет один символ, описывающий его действие:

• L — повернул налево
• S — пошёл прямо
• R — повернул направо
• B — развернулся; это происходит только в тупике

После прохода с исследованием эта строка и есть пройденный путь. В ней же внутри скрыт путь, который следовало бы пройти.

Единственное наблюдение

Каждый B в строке отмечает ошибку: робот зашёл в ветвь, которая никуда не вела, и был вынужден развернуться. Поворот перед B и поворот после него были частью этого напрасного обхода.

Поэтому рассматривайте каждый B вместе с соседними символами — окно из трёх символов, например L B L. Эти три перемещения привели робота в тупик и обратно, оставив его лицом в некотором направлении. Всегда существует один поворот, который дал бы тот же результат без обхода. Замените эту тройку одним поворотом, и тупик исчезнет из маршрута.

Проследите пример. Робот прибывает к среднему разветвлению, направляясь на восток, и выбирает левую ветвь (L) — ответвление, идущее на север. Он попадает в тупик и разворачивается (B). Вернувшись к разветвлению и направляясь на юг, он снова выбирает левую ветвь (L), которая теперь указывает на восток. Итог: он вошёл, направляясь на восток, и вышел, направляясь на восток. Это S — прямо через разветвление.

Шесть подстановок

Возможны только шесть окон, поскольку средний символ всегда равен B, а B никогда не стоит рядом с другим B:

Каждую строку можно вывести, складывая углы поворотов: поворот налево считается за −90°, прямо за 0°, направо за +90°, а разворот за 180°. L B L — это −90 + 180 − 90 = 0°, то есть S. S B S — это 0 + 180 + 0 = 180°, то есть B. Таблицу не нужно запоминать — она получается из арифметики.

Применение до стабилизации

Одного прохода недостаточно. Свёртывание обхода может сблизить два поворота, которые теперь образуют новое сводимое окно, поэтому повторяйте просмотр, пока полный проход ничего не меняет:

void simplify(String& path) {
  bool changed = true;
  while (changed) {                       // a collapse can expose another
    changed = false;
    for (int i = 0; i + 2 < path.length(); i++) {
      if (path[i + 1] != 'B') continue;   // only windows centred on a turn-back
      path = path.substring(0, i) + fold(path[i], path[i + 2])
                                   + path.substring(i + 3);
      changed = true;
      break;
    }
  }
}

Длинная ветвь от главного коридора сворачивается по одному разветвлению за проход, проход за проходом, пока от неё ничего не останется. Когда цикл завершится, строка вообще не будет содержать B — это доказательство завершения, поскольку любой оставшийся обход тупика всё ещё содержал бы один такой символ.

Запуск оптимизированного маршрута

Второй проход намного проще первого. Решений больше нет: робот следует линии, а в каждом разветвлении берёт следующий символ из упрощённой строки и поворачивает соответственно. Классификация разветвления всё ещё важна — роботу нужно знать, что он достиг разветвления, — но выбор разветвления теперь сводится к чтению следующего символа.

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

Чего LSRB не может сделать

LSRB работает на идеальном лабиринте — без циклов, где между любыми двумя точками существует ровно один путь. Если в лабиринте есть цикл, правило левой руки может ходить по нему бесконечно, а правилам подстановки нечего будет сворачивать, поскольку нет тупиков.

Как только циклы становятся возможны, нужна настоящая карта и поиск по графу. Это область заливки, которая строит поле расстояний по всему лабиринту и движется по нему вниз; именно её симулятор решателя лабиринта запускает после фазы исследования. LSRB — правильный инструмент, когда лабиринт является деревом, а линейные лабиринты на ленте почти всегда именно такие; он требует несколько десятков байтов, тогда как заливка требует полной сетки.