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

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

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

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

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

2. Є велике число правил, які на основі отриманих фактів дозволяють продукувати зростаюче число висновків або цілей. Своєчасний відбір цілей дозволяє відсіяти безліч можливих гілок, що робить процес пошуку в просторі станів ефективнішим (мал. 9)

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

3. Початкові дані не наводяться в задачі, але розуміється, що вони повинні бути відомі вирішувачеві. В цьому випадку пошук від цілі може служити керівництвом для правильної постановки задачі. У програмі медичної діагностики, наприклад, є всілякі діагностичні тести. Лікар вибирає з них тільки ті, які дозволяють підтвердити або спростувати конкретну гіпотезу про стан пацієнта.

Таким чином, при пошуку від мети відповідні правила застосовуються для виключення неперспективних гілок пошуку.

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

1. Все або більшість початкових даних задані в постановці задачі. Задача інтерпретації полягає у виборі цих даних і їх уявленні у вигляді, відповідному для використання в інтерпретуючих системах вищого рівня. На стратегії пошуку від даних засновані системи аналізу даних певного типу. Це такі системи, як PROSPECTOR або Dipmeter, аналізатори геологічних даних, що визначають, які мінерали з найбільшою вірогідністю можуть бути знайдені в деякому місці.

2. Існує велике число потенційних цілей, але всього лише декілька способів застосування фактів і представлення інформації про конкретний приклад задачі (мал. 10). Прикладом цього типу систем є програма DENDRAL — експертна система дослідження молекулярних структур органічних сполук на основі формул, даних масс-спектрографа і знань з хімії. Для будь-якої органічної сполуки існує надзвичайно велике число можливих структур. Проте дані масс-спектрографа дозволяють програмі DENDRAL залишити лише невелике число таких комбінацій.

3.

1 2 3 4 5 6 7 8

Схожі роботи

Реферати

Курсові

Дипломні