Використання евристик в іграх

його предків MIN.

Таким чином, альфа-бета-усікання виражає відношення між вузлами рівнів n і n +2. При цьому з розгляду можуть бути виключені цілі піддерева з корінням на рівні n+1. Наприклад, на мал. 8 зображений простір пошуку з мал. 3, до якого застосований алгоритм альфа-бета-усікання. Відмітимо, що результуюче значення, що повертається, ідентичне отриманому в алгоритмі мінімакса, але при цьому процедура альфа-бета-усікання значно економічніше мінімакса.

При вдалому порядку станів в області пошуку процедура альфа-бета-усікання може ефективно подвоювати глибину пошуку в даному просторі при фіксованих просторово-часових характеристиках комп'ютера [Nilsson, 1980]. Якщо ж вузли розташовані невдало, процедура альфа-бета-усікання здійснює пошук в такому ж просторі, як і звичайний мінімакс. Проте пошук проводиться тільки за один прохід.

3. Стратегії пошуку в просторі станів на основі даних і від цілі

Пошук в просторі станів можна вести в двох напрямах: від початкових даних завдання до цілі і у зворотному напрямі від цілі до початкових даних.

При пошуку на основі даних (data-driven search — пошук, керований даними), який іноді називають прямим ланцюжком (forward chaining), дослідник починає процес рішення задачі, аналізуючи її умову, а потім застосовує допустимі ходи або правила зміни стану. В процесі пошуку правила застосовуються до відомих фактів для отримання нових фактів, які, у свою чергу, використовуються для генерації нових фактів. Цей процес продовжується до тих пір, поки ми, якщо повезе, не досягнемо цілі.

Можливий і альтернативний підхід

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

Підведемо підсумки: пошук на основі даних починається з умов задачі і виконується шляхом застосування правил або допустимих ходів для отримання нових фактів, ведучих до цілі. Пошук від цілі починається із звернення до цілі і продовжується шляхом визначення правил, які можуть привести до цілі, і побудови ланцюжка підцілей, що веде до початкових даних задачі.

Нарешті відмітимо, що в обох випадках (і при пошуку на основі даних і при пошуку від цілі) дослідник працює з одним і тим же графом простору станів, проте порядок і число станів в процесі пошуку можуть розрізнятися. Яку стратегію пошуку віддати перевазі, залежить від самої задачі. При цьому слід враховувати складність правил, "форму" простору станів, природу і доступність даних задачі. Все це може змінюватися від задачі до задачі.

Як приклад залежності складності пошуку від вибору стратегії розглянемо задачу, в якій потрібно підтвердити або спростувати твердження "Я — нащадок Томаса Джефферсона". Позитивним рішенням є шлях по генеалогічному дереву від "Я" до "Томас Джефферсон". Пошук на цьому графові можна вести в двох

1 2 3 4 5 6 7 8

Схожі роботи

Реферати

Курсові

Дипломні