Мой сайт

Воскресенье, 06.07.2025, 10:49
Приветствую Вас Гость

Регистрация
Вход
Главная » 2014 » Январь » 24 » Робот для состязаний: выход из лабиринта. Часть III :: Лабиринт правило правой руки
07:33

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





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


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


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


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

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

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

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

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

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

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

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


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


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


Источник: nnxt.blogspot.com
Просмотров: 4106 | Добавил: concle | Рейтинг: 0.0/0
Всего комментариев: 0
Меню сайта
Форма входа
Поиск
Календарь
«  Январь 2014  »
Пн Вт Ср Чт Пт Сб Вс
  12345
6789101112
13141516171819
20212223242526
2728293031
Архив записей
Наш опрос
Оцените мой сайт
Всего ответов: 1
Мини-чат
Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Статистика

    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0