Головна

Алгоритми пошуку в просторі станів.

  1.  B-дерева: принципи побудови, операція пошуку.
  2.  III. Сформованість просторових уявлень.
  3.  IV. ПРЯМА В ПРОСТОРІ
  4.  Абсолютні Amicus et Hostis портрети в часі і просторі
  5.  Акти законодавства про податки і збори як основне джерело НП. Дія актів в просторі.
  6.  Алгоритм руху що навчається в освітньому просторі
  7.  Алгоритм пошуку в глибину.

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

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

Можливий і альтернативний підхід. Розглянемо мета, яку ми хочемо досягти.

Проаналізуємо правила або допустимі ходи, що ведуть до мети, і визначимо умови

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

пощастить) ми не досягнемо вихідних даних завдання. Таким чином визначається шлях від

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

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

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

Проста оцінка дозволяє порівняти складність пошуку в обох напрямках. Томас Джефферсон народився приблизно 250 років тому. Якщо вважати, що нове покоління народжується кожні 25 років, то довжина шуканого шляху становить приблизно 10. Оскільки кожен нащадок має двох батьків, то шлях від "Я" вимагає аналізу 210 предків. З іншого

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



 Пошук в просторі станів. |  Алгоритм пошуку з поверненням.

 Колективне поведінка агентів. |  СПОСОБИ І ПРИЧИНИ Взаємодія МІЖ АГЕНТАМИ |  МОДЕЛЮВАННЯ Взаємодія В Мультиагентний СИСТЕМАХ. |  Координація ПОВЕДІНКИ АГЕНТІВ У Мультиагентний СИСТЕМІ. |  На основі моделі аукціону |  ТЕХНОЛОГІЇ ПРОЕКТУВАННЯ Мультиагентний СИСТЕМ |  ІНСТРУМЕНТАЛЬНІ ЗАСОБИ ДЛЯ ПОБУДОВИ Мультиагентний СИСТЕМ. |  МУЛ ЬТІАГЕНТНИЕ СИСТЕМИ ДЛЯ ПОШУКУ ІНФОРМАЦІЇ. |  Перспективи мультиагентних технологій. |  Висновки по 9-му розділі. |

© um.co.ua - учбові матеріали та реферати