Робот для состязаний: выход из лабиринта. Часть III

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

Хотя и в конкретном приведенном примере было видно, что траектория движения робота, выполняющего "Правило левой руки", - более оптимальна, их этого нельзя сделать вывод, что в каждом лабиринте такой робот будет опережать робота, запрограммированного на движение по "Правилу правой руки".

Например,
1. Робот, двигающийся вдоль правых стенок – выполняет меньше ненужных обходов, т.е. придет к финишу быстрее. Общая длина ненужных обходов для него 1 ячейка, в то время как роботу, двигающемуся вдоль левых стенок – нужно сделать ненужных проходов длиной в 3 ячейки (одна в четвертом коридоре и две в пятом).


2. На этом поле, робот, движущийся по "Правилу левой руки", придет к финишу раньше. 2 ячейки против 4-х.


3. В данной конфигурации количество "лишних" заходов у обоих роботов – одинаково (по 2 ячейки).


Эти три примера показывают, что для разных конфигураций лабиринтов эффективными будут разные алгоритмы. Но это нерепрезентативная выборка.

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

Всего различных возможных вариантов установки перегородок	243
"Разумных" вариантов, когда не никакие три сподряд идущие перегородки не будут установлены в одинковые позиции	180

Если теперь рассмотреть варианты прохода для каждой конфигурации лабиринта, то получится такая вот статистика:

Где

• в первой строчке – идеальные конфигурации – робот не сделает ни одного ненужного заворота.
• остальных строчки для проходов с одним или несколькими "ненужными" заворотами в тупики. Причем, если написано два «ненужных» прохода, то это может быть заворот в один длинный тупик или два коротких – в любом случае, на их проходы тратиться почти одинаковое время.
• в последней строчке – сколько "ячеек" придется посетить при самой неудачной конфигурации лабиринта.
  

Из таблицы видно, что в 45 конфигурациях лабиринта из 180 робот, обходящий алгоритм по "Правилу левой руки", будет делать только верные перемещения. В то время как роботу, выполняющий программу по "Правилу правой руки" доступно только 13 таких конфигураций. Даже на то, что роботу выпадет конфигурация в которой ему придется сделать все го лишь два "ненужных" прохода., вероятность больше в случае "Правила левой руки" - 41 к 180, тогда как у "Правила правой руки" - всего 36 к 180.

Следовательно, можно сделать вывод, что у робота, двигающегося вдоль левых стенок, вероятность прийти к финишу первым выше. Т.е. при выборе, какой именно алгоритм реализовывать у робота, выбор, безусловно, ложиться на "Правило левой руки".

Причем, если вспомнить о необходимости собирать шарики по пути движения робота (а они лежать в строго определенных позициях в 3-ем, 4-ом и 5-ом коридорах), статистика несильноизменится.

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


Назовем этот маневр также "ненужным" ходом, тогда табличка станет выглядеть следующим образом:


Т.е. варианты попасть на "хорошее" поле у робота, работающего по "Правилу левой руки" все еще существенно выше.