МЕТОДИ ПОШУКУ РІШЕНЬ В ЕКСПЕРТНИХ СИСТЕМАХ

Методи вирішення завдань, що базуються на зведення їх до пошуку, залежать від особливостей предметної області, в якій вирішується завдання, і від вимог, що пред'являються користувачем до рішення. Особливості предметної області:

обсяг простору, в якому належить шукати рішення;

ступінь змінності області в часі і просторі (статичні та динамічні області);

повнота моделі, що описує область, якщо модель не повна, то для опису області використовують кілька моделей, які доповнюють один одного;

визначеність даних про розв'язуваної задачі, ступінь точності (хибності) та повноти (неповноти) даних.

Вимоги користувача до результату завдання, що вирішується за допомогою пошуку, можна характеризувати:

кількістю рішень: одне рішення, кілька рішень, всі рішення.

властивостями результату: обмеження, яким повинен задовольняти отриманий результат та (або) способом його отримання.

Існуючі методи вирішення завдань, які використовуються в експертних системах, можна класифікувати таким чином:

методи пошуку в одному просторі - методи, призначені для використання в наступних умовах: області невеликий розмірності, повнота моделі, точні і повні дані;

методи пошуку в ієрархічних просторах - методи, призначені для роботи в областях великої розмірності;

методи пошуку при неточних та неповних даних;

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

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

3.1. ПОШУК РІШЕНЬ В ОДНОМУ ПРОСТОРІ

Методи пошуку рішень в одному просторі зазвичай поділяються на:

пошук в просторі станів (розглянемо детально),

пошук методом редукції,

евристичний пошук

пошук методом "генерація-перевірка".

3.1.1. Пошук в просторі станів

Завдання пошуку в просторі станів звичайно формулюється в теоретико-Графова інтерпретації.

Нехай задана трійка (S0, F, SТ), де S0 - безліч початкових станів (умови завдання), F - безліч операторів завдання, що відображають одні стану в інші, SТ - безліч кінцевих (цільових) станів (рішень задачі).

Мета: визначати таку послідовність операторів, що перетворює початкові стану в кінцеві.

Процес рішення у вигляді графа G = (Х, Y), де X = (х0, х1 ,...} - безліч (у загальному випадку нескінченна) вершин графа, станів, а Y - безліч, що містить пари вершин ( xi, xj), (xi, xj)