Методы рішення задач

Тип работы:
Реферат
Предмет:
Информатика, программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

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

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

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

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

определенность даних про розв’язуваної завданню, ступінь точності (помилковості) і повноти (неповноти) даних.

Требования користувача до результату завдання, розв’язуваної з допомогою пошуку, можна характеризувати:

количеством рішень: одне правильне рішення, кілька рішень, всі.

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

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

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

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

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

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

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

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

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

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

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

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

поиск методом «генерация-проверка ».

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

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

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

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

Процесс рішення на вигляді графа G=(Х, Y), де X={х0, х1,…} - безліч (у випадку нескінченне) вершин графа, станів, а Y — безліч, що містить пари вершин (xi, xj), (xi, xj)? X. Якщо кожне подружжя (xi, xj) неупорядкована, що його називають руба, а граф — неориентированным. Якщо кожної пари (xi, xj) заданий порядок (напрям), то пару (xi, xj) називають дугою (орієнтованим руба), а граф називають орієнтованим (спрямованим). Вершини пари (xi, xj) називають кінцевими точками ребра (дуги).

Поиск у просторі станів природно у вигляді орієнтованого графа. Наявність пари (xi, xj) свідчить про існування деякого оператора f (f? F), перетворюючого стан, відповідне вершині xi, до стану xj. Для деякою вершини xi виділяємо безліч всіх спрямованих пар (xi, xj)? Y, т.ь. безліч дуг, що виходять з вершини хi, (батьківської вершини), і безліч вершин (званих дочірніми вершинами), у яких ці дуги наводять. Безліч дуг, що виходять з вершини xi, відповідає безлічі операторів, які можна застосовані до стану, відповідному вершині хi.

В безлічі вершин X виділяють підмножина вершин Х0? Х, відповідне безлічі початкових станів (So), і підмножина вершин Хт? X, відповідне безлічі кінцевих (цільових) станів (SТ). Безліч Хт то, можливо поставлено вочевидь, і неявно, тобто. через властивості, що мати цільові стану.

Отметим, що граф З може бути поставлене явно і неявно. Неявний завдання графа G стоїть у визначенні безлічі Х0? Х (відповідного безлічі початкових станів) і багатьох операторів, які, будучи застосовні до деякою вершині графа, дають всі її дочірні вершини.

Итак, граф G задає простір станів, тобто. простір, у якому здійснюється пошук рішення. Побудова простору здійснюється з допомогою наступного процесу. Береться якась вершина х0? Х, до неї застосовуються всіх можливих оператори, які породжують все дочірні вершини. Цей процес відбувається називають процесом розкриття вершин. Якщо отримана цільова вершина, вона не розкривається. Процес побудови простору станів закінчується, коли всі нерозкриті вершини є цільовими, чи термінальними (тобто. вершинами, яких не можна застосувати ніяких операторів). У зв’язку з тим, що простір станів може містити безліч вершин, практично процес породження простору обмежують або часом, або обсягом пам’яті.

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

поиск завглибшки (спочатку розкривається та вершина, що була побудована останній). Рис. 3.1. а

поиск завширшки. (вершини розкриваються у тому порядку, де вони народжуються.) Рис. 3.1.б.

Целевые вершини позначені чорними квадратами, а термінальні - білими квадратами. З використанням кожного із засобів вдасться знайти всі. При переборі всього простору обидва методу аналізуватимуть однакову кількість вершин, проте метод пошуку ширину вимагатиме значно більше пам’яті, оскільки він запам’ятовує всі дороги пошуку (а чи не один, як із пошуку завглибшки).

3.1.2. Пошук методом редукції

При пошуку методом редукції вирішення завдання зводиться до вирішення сукупності їхнім виокремленням її подзадач. Цей процес відбувається повторюється кожної подзадачи до того часу, поки кожна гілка отриманого набору подзадач, їхнім виокремленням рішення вихідної завдання, це не матиме очевидне рішення. Процес виконання завдання розбивкою в подзадачи можна як спеціального спрямованого графа G, званого И/ИЛИ-графом; Кожній вершині цього графа ставлять у відповідність опис деякою завдання (подзадачи). У графі виділяють два типу вершин: конъюнктивные вершини і диз’юнктивні вершини.

Решение завдання у пошуку методом редукції (у пошуку в И/ИЛИ-графе) зводиться до пошуку в И/ИЛИ-графе вирішального графа.

Цель процесу пошуку И/ИЛИ-графе — показати, що початкова вершина можна залагодити, тобто. з цією вершини існує вирішальний граф. Визначення можливо розв’язати вершини в И/ИЛИ-графе можна сформулювати рекурсивно так:

Конечные (цільові) вершини можна розв’язати, бо їх рішення відомо вихідному припущенню.

Вершина АБО можна залагодити тоді й тільки тоді, коли можна залагодити по крайнього заходу одне з її дочірніх вершин.

Вершина І можна залагодити толу і тільки тоді ми, коли можна залагодити кожна гілка її дочірніх вершин.

Решающий граф окреслюється подграф з розв’язаних вершин, що свідчить про, що початкова вершина можна залагодити (відповідно до наведених вище визначенням). На рис. 3.3. розв’язні вершини зачернены, а нерозв’язні залишені білими.

Для графа И/ИЛИ, як і на допомогу пошуку у просторі станів, можна визначити пошук завглибшки та відшуковування завширшки як у прямому, і у напрямку. На рис. 3.4. наведено приклад пошуку ширину (рис. 3.4., чи пошуку глибину (рис. 3.4., б). На малюнку вершини пронумеровано у порядку, де вони розкривалися, кінцеві вершини є такі квадратами, розв’язні вершини зачернены, дуги вирішального графа виділено подвійними лініями.

3.1.3. Евристичний пошук

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

3.1.4. Поиск методом «генерация-проверка «

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

3.2. ПОШУК У ІЄРАРХІЇ ПРОСТОРІВ

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

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

поиск в факторизованном просторі,

поиск в фіксованому безлічі просторів

поиск в змінюваному безлічі просторів.

3.2.1. Пошук в факторизованном просторі

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

3.2.2. Пошук в фіксованому безлічі просторів

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

3.2.3. Пошук в змінюваному безлічі ієрархічних просторів

В ряді додатків вдасться все можуть бути вирішені завдання зводити до фіксованому набору подзадач. План виконання завдання у разі повинен мати зміну структуру не може бути зведений до фіксованому набору подзадач. Аби вирішити таких завдань можна використовувати метод спадного уточнення. Цей метод виходить з наступних припущеннях:

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

решения, прийняті на верхніх рівнях, не потрібно скасовувати більш нижніх.

3.3. ПОШУК У АЛЬТЕРНАТИВНИХ ПРОСТОРАХ

Рассмотренные вище методи пошуку походять від мовчазної передумови, знання про предметної області й даних про розв’язуваної завданню є точними і з повними і їх справедливо таке:

все затвердження, описують стан, є «справжніми;

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

Однако під час вирішення будь-яких практичних завдань і особливо в рішенні неформалізованих завдань поширена зворотна ситуація. Експерту доводиться працювати за умов неповноти і неточності знань (даних) і, зазвичай, за умов дефіциту часу. Коли експерт переймається тим, він використовує методи, які від формальних математичних міркувань. І тут експерт робить правдоподібні припущення, що він неспроможна довести; цим питання про їхнє істинності залишається питанням відкритим. Усі затвердження, отримані з урахуванням цих правдоподібних припущень, теж може бути доведені.

Итак, щоб система могла робити умовиводи, засновані на здоровий глузд, під час роботи з неповними (неточними) даними і знаннями, повинна бути здатна робити припущення, а і при отриманні нову інформацію, яка б показала хибність припущень, відмовлятися як від зроблених припущень, і від умовиводів, отриманих з урахуванням цих припущень. Думка системи у тому, які факти мають місце, змінюється під час міркування, тобто. можна казати про ревізії думок. Отже, навіть якщо розглядати проблемну область як статичну, неповнота (і неточність) знань і передачею даних тягне у себе розгляд цій галузі що за різних (і навіть протилежних) припущеннях, що, своєю чергою, призводить до уявленню області у вигляді альтернативних просторів, відповідних різним, можливо, суперечливим і (чи) взаємодоповнюючим припущенням і думок.

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

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

Этот метод пошуку називають пошуком, направляемым залежністю.

3.4. ПОШУК З ВИКОРИСТАННЯМ КІЛЬКОХ МОДЕЛЕЙ

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

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

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

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

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

3.5. ВИБІР МЕТОДУ РІШЕННЯ ЗАВДАНЬ

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

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

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

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

ПоказатьСвернуть
Заполнить форму текущей работой