Алгоритм поиска выхода Кассандра
(см. рисунок )
Находясь в точке (0,0) агент А создает четыре копии, по направлениям (-1,0), (1,0), (0,-1), (0,1)
Так как два направления невозможны в лабиринте 2x2 при создании копии с такими координатами возникает ошибка и эти копии не создаются.
Поэтому далее мы рассматриваем жизненный цикл только успешно созданных копий.
Это два агента B. У одного координаты (1,0), у другого (0,1) Эти агенты создают каждый по три копии, так как исключаются координаты родителя A(0,0)
Agent B(1,0) parent A(0,0)
------------
C(1,-1) exception, not created
C(1,1) wall, exception, not created
C(2,0) success, created
Agent B(0,1) parent A(0,0)
------------
C(-1,1) exception, not created
C(1,1) wall, exception, not created
C(0,2) success, created
Успешно созданные на втором шаге агенты создают каждый по три копии, так как исключаются координаты родителей B(1,0) и B(0,1)
Agent С(2,0) parent B(1,0)
------------
D(3,0) exception, not created
D(2,-1) exception, not created
D(2,1) success, created
Agent С(0,2) parent B(0,1)
------------
D(0,3) exception, not created
D(-1,2) exception, not created
D(1,2) success, created
Успешно созданные на третьем шаге агенты создают каждый по три копии, так как исключаются координаты родителей С(2,0) и С(0,2)
Agent D(2,1) parent B(1,0)
------------
E(3,1) exception, not created
E(1,1) wall, exception, not created
E(2,2) success, exit from puzzle found
Agent D(1,2) parent B(0,1)
------------
E(1,3) exception, not created
E(1,1) wall, exception, not created
E(2,2) success, exit from puzzle found
Если агент заходит в тупик то сообщает об этом своему родителю и прекращает работу.
Если агент находит выход то сообщает об этом своему родителю и прекращает работу, при этом, если у родителя есть родитель, то этот родитель тоже сообщает своему родителю о найденном выходе и прекращает работу.
В итоге агент А получает информацию о двух возможных путях выхода из лабиринта.
В данном случае они равновесны, например по количеству шагов до выхода. Поэтому можно выбрать как первый так и второй.
Из равновесных автоматически выбираем первый.
