Двунаправленный поиск (bidirectional search)

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

При практической реализации двунаправленного поиска необходимо решить ряд проблем.

§ Что такое поиск в обратном направлении от целевого состояния? Предками (predecessors) узла n называются все те узлы, для которых n является наследником (successor). Поиск в обратном направлении озна­чает последовательную генерацию предков, начиная с целевого узла.

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

§ Что делать, если имеется несколько целевых состояний?

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

Необходимо решить какой тип поиска применять для каждого из деревьев.

Рекурсия

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

1. Рекурсивный шаг: вызов процедуры из этой же процедуры для повторения после­
довательности действий.

2. Условие, которое обеспечивает выход из процедуры и таким образом предотвра­
щает зацикливание (рекурсивная версия бесконечного цикла).

Оба этих компонента необходимы и появляются во всех рекурсивных определениях и алгоритмах. Рекурсия — естественный инструмент управления массивами данных, кото­рые имеют правильную структуру и неопределенный размер, например, списками, де­ревьями и графами. Рекурсия особенно удобна для поиска в пространстве состояний.

Прямое преобразование алгоритма поиска в глубину в рекур-
сивную форму иллюстрирует эквивалентность рекурсии и итерационного подхода.
Этот алгоритм для поддержки списка состояний использует глобальные переменные

open и closed:

function depthsearch; %переменные open и closed глобальные

Begin

if список open пуст

then return FAIL;

current_state:= первый элемент списка open;
if current_state равно целевому состоянию
then return SUCCESS
else

Begin

open:= хвост списка open;

closed:= closed с добавлением current_state;
для каждого потомка current_state
if не в списке closed или open

%построение стека

then добавить потомок в начало списка open
end;

depthsearch %рекурсивный вызов

End.

Поиск в ширину можно описать фактически тем же самым алгоритмом. При этом не-
обходимо сохранять список closed как глобальную структуру данных и рассматривать
список open как очередь, а не как стек.

Из представленного алгоритма ясно, что поиск в глубину не использует все возмож-
ности рекурсии. Процедуру можно упростить, используя рекурсию непосредственно (а
не через список open) для рассмотрения состояний и нахождения путей в их простран-
стве. В новой версии алгоритма глобальная переменная closed используется для обна-
ружения повторяющихся состояний и предотвращения циклов. Список open неявно ис-
пользуется в записях активации рекурсивной среды.

function depthsearch (current__state);

%closed — глобальная переменная
begin

if current_state равно целевому состоянию

then return SUCCESS;

добавить current_state в список closed;
while current_state имеет непроверенные потомки
begin

child:= следующий непроверенный потомок;
if потомок не член списка closed

then if depthsearch(child) = SUCCESS

then return SUCCESS
end;

return FAIL %поиск исчерпан

end

Вместо того чтобы находить все потомки данного состояния, а затем помещать их в список open, этот алгоритм рассматривает потомки по одному. Для каждого из них ре-
курсивно находятся все потомки, а затем рассматривается очередной потомок исходного
состояния. Следует заметить, что алгоритм предполагает определенный порядок опера-
торов генерации состояний. Если при рекурсивном поиске некоторый потомок является
целевым состоянием, то процедура поиска успешно завершается, и, естественно, алго-
ритм игнорирует братьев данного потомка. Если рекурсивный вызов для одного из по-
томков приведет в тупик, то будет рассмотрен брат этого потомка, а также все его по-
томки.

Заданиe:

В приведенном ниже плане лабиринте буквой А помечен мобильный агент, буквой В выход из лабиринта. Цель агента – выйти из лабиринта.

Список возможных действий агента в порядке уменьшения приоритета:

<ШагНаСевер (­), ШагНаВосток(®), ШагНаЮг(¯), ШагНаЗапад(), ШагНазад>.

Из всех возможных действий агент выбирает самое приоритетное.

При выполнении каждого шага, не являющегося шагом назад, Агент отмечает его стрелочкой. Действие невозможно, если есть препятствие, мешающее его выполнению. Такими препятствиям являются: стены и границы лабиринта, а также стрелочки. Действие «ШагНазад» реализует шаг бэктрекинга (возврата по ранее пройденному пути).

									В
					А

а) Начертить траекторию движения агента.

б) Указать, какая стратегия поиска целевого состояния им используется (по варианту).

в) Написать программу реализующую поведение агента.(программирование реалитзовать в среде Delphi).

Варианты:

1. поиск от цели в ширину;
2. поиск от цели в глубину;
3. поиск на основе данных в ширину;
4. поиск на основе данных в глубину;
5. рекурсивный поиск от цели в ширину;
6. рекурсивный поиск от цели в глубину;
7. рекурсивный поиск на основе данных в ширину;
8. рекурсивный поиск на основе данных в глубину;
9. двунаправленный поиск;
10. рекурсивный поиск от цели в ширину;