Двонаправлений пошук (bidirectional search) - Студопедія

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

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

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

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

§ Що робити, якщо є кілька цільових станів?

§ Повинен існувати ефективний спосіб перевірки кожного нового вузла, щоб виявити, чи він не з'явився на протилежному дереві пошуку.

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

Рекурсія

У математиці рекурсивне визначення об'єкта — це його опис термінах частин цього ж визначення. В інформатиці рекурсія використовується визначення та аналізу структур даних і процедур. Рекурсивна процедура складається з наступних етапів.

1. Рекурсивний крок: виклик процедури з тієї ж процедури для повторення після дії дії.

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

Обидва ці компоненти необхідні і з'являються у всіх рекурсивних визначеннях та алгоритмах. Рекурсія – природнийінструмент управління масивами даних, які мають правильну структуру та невизначений розмір, наприклад, списками, деревами та графами. Рекурсія особливо зручна для пошуку простору станів.

Пряме перетворення алгоритму пошуку в глибину в рекурсивну форму ілюструє еквівалентність рекурсії та ітераційного підходу. Цей алгоритм підтримки списку станів використовує глобальні змінні

функція 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 додати нащадок на початок списку openend;

depthsearch %рекурсивний виклик

End.

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

З представленого алгоритму ясно, що пошук у глибину не використовує всі можливості рекурсії. Процедуру можна спростити, використовуючи рекурсію безпосередньо (а не через список open) для розгляду станів і знаходження шляхів у їхньому просторі. У новій версії алгоритму глобальна змінна closed використовується для виявлення повторення станів і запобігання циклів. Список open неявно використовується у записах активації рекурсивного середовища.

functiondepthsearch (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 %пошук вичерпаний

Замість знаходити всі нащадки даного стану, а потім поміщати їх у список open, цей алгоритм розглядає нащадки по одному. Для кожного з них ре- курсивно знаходяться всі нащадки, а потім розглядається черговий нащадок вихідного стану. Слід зазначити, що алгоритм передбачає певний порядок операторів генерації станів. Якщо при рекурсивному пошуку деякий нащадок є цільовим станом, то процедура пошуку успішно завершується, і, природно, алго-ритм ігнорує братів даного нащадка. Якщо рекурсивний виклик для одного з нащадків приведе в глухий кут, то буде розглянутий брат цього нащадка, а також всі його нащадки.

Завдання:

У наведеному нижче плані лабіринті літерою А позначено мобільний агент, літерою В вихід з лабіринту. Мета агента – вийти із лабіринту.

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

З усіх можливих дій агент вибирає найпріоритетніше.

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

У
А

а) Накреслити траєкторію руху агента.

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

в) Написати програму реалізуючу поведінку агента. (Програмування реалітзувати серед Delphi).

Варіанти:

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

Чи не знайшли те, що шукали? Скористайтеся пошуком:

Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно