Повна версія

Головна arrow Інформатика arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ЕКСПОНЕНЦІАЛЬНО СКЛАДНІСТЬ ПОШУКУ НА ДЕРЕВІ РІШЕНЬ І МЕТОДИ ЇЇ РЕДУКУВАННЯ

В результаті освоєння даного розділу навчається буде:

знати

• методологічні принципи застосування антропоморфних методів в штучному інтелекті;

вміти

• застосовувати отримані знання про методи редукування дерева рішень до практичних ситуацій;

володіти

• сучасними технологіями скорочення розмірності простору пошуку в базах знань великого розміру.

Наївний логічний пошук і завдання реального світу

Модель наївного логічного висновку

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

Логічний висновок з правила, що складається з умов, складених триплету «суб'єкт - предикат - об'єкт» виду з (х, -, p jy г /,), являє собою рішення системи рівнянь з кількістю невідомих, що дорівнює кількості змінних в правилі. Одну частину рівнянь утворюють пари х, - = у г якщо змінна використовується більш ніж в однієї умови правила, другу - рівняння х, = значення, г /, = значення , одержувані підстановкою в умови правила відповідних фактів / = (s, р , про ). Наївний висновок складається з наступних кроків.

  • 1
  • 2. Якщо уніфікація умови правила успішна, то виконується перехід до наступного умові правила, інакше машина виведення намагається уніфікувати умова правила з наступним фактом.
  • 3. Якщо всі факти вичерпані, а умова правила не уніфіковано, виконується відкат до попереднього умові правила і в нього підставляється черговий факт.
  • 4. Після успішної уніфікації всіх умов значення змінних підставляються в результуючу частина правил. Щоб отримати всі можливі рішення, виконується відкат, як якщо б правило не було уніфіковано.

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

 
<<   ЗМІСТ   >>