WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Стратегiї планування рiшень - Реферат

Стратегiї планування рiшень - Реферат


Реферат на тему:
Стратегiї планування рiшень
1. Поняття стратегiї та стратегiчного прийому рiшень
У складi Інтелектуальноi Вирiшуючоi Сiстеми (IВС) може бути выдiлено оператори (моделi дiй) двох типiв:
" оператори, за допомогою яких модель однiєї ситуацiї перетворюється в модель iншої ситуацiї;
" оператори, за допомогою яких формуються плани рiшень, тобто послiдовностi операторiв першого типу, якi перетворюють модель вихiдної ситуацiї в модель цiльової ситуацiї.
У вiдповiдностi з функцiональною направленiстю оператори першого типу будемо називати ST-операторами (SITUATION TRANSFORMATION OPERATOR), оператори другого типу - PF-операторами (PATH FORMATION OPERATOR).
Визначення 1:
Програма, що складається з PF-операторiв, для пошуку шляхiв рiшення з ST-операторiв, називається стратегiєю рiшення.
Досвiд дослiдження рiзноманiтних ІВС показує, що для розв'язання задач в складних середовищах, стратегiя набуває першочергове значення. Ми використовуємо стратегiю для класифiкацiї та спiвставлення рiзноманiтних методiв розв'язання задач.
Пошук шляху рiшення можна розглядати як циклiчний процес, на кожному кроцi якого обирається черговий ST-оператор. Складнiсть пiдзадачi вибору оператору можна розцiнювати за допомогою функцiї , де - деяка величина , що визначає обсяг дiлянки пошуку шляху розв'язання; а - iнформацiя про шляхи розв'зання. Складнiсть зростає iз збiльшенням та зменшенням .
Пошук шляху рiшення може бути виконан:
" в прямому напрямку вiд вихiдної ситуацiї до цiльової умови;
" в зворотньому напрямку вiд цiльової умови до вихiдної ситуацiї;
" в прямому та зворотньому напрямках.
Визначення 2: Стратегiчними прийомами рiшення називаються прийоми, що задовольняють одному з наступних критерiїв:
" призводять до зменшення ;
" призводять до збiльшення ;
" визначають напрямок пошуку.
2. Огляд та обговорення стратегiчних прийомiв рiшення
У цьому пiдроздiлi розглядаються стратегiчнi прийоми, якi використовуються при розробцi рiзних стратегiй рiшення.
2.1. Прямий пошук
Прямий пошук визначає направлення пошуку шляху рiшення вiд вихiдної сiтуацiї до цiльової умови. Процес прямого пошуку iнтерпретується на графi сiтуацiй, де вершини вiдповiдають ситуацiям, а дуги - операторам перетворення ситуацiй. Приклад графа ситуацiй показано на мал.1.
Вирiшуючим графом ситуацiй називається граф ситуацiй, у якого всi вершини зняходяться на шляху рiшення. У прикладi на мал.1 це граф з вершинами , , , , .
Явне завдання графа ситуацiй є прийнятним тiльки для середовищ з невеликою потужнiстю множин ситуацiй. Для бiльш складних середовищ граф сiтуацiй породжується в процесi пошуку шляху рiшення.
2.2. Зворотний пошук
Зворотний пошук визначає направлення пошуку шляху рiшення вiд цiльової умови до вихiдної ситуацiї. У деяких випадках це призводить до спрощення пiдзадачи вибору оператора завдяки зменшенню областi пошуку . В залежностi вiд типу операцiї застосування оператора в зворотньому напрямку будемо розрiзняти Т-зворотний i R-зворотний пошук.
Т-зворотний пошук використується, коли цiльову умову задачi зображено повним описом цiльової ситуацiї. В цьому випадку цiльова ситуацiя перетворюється в вихiдну шляхом застосування операторiв в зворотньому напрямку за типом трансформацiї.
Процес Т-зворотнього пошуку може бути iнтерпретовано на графi ситуацiй. Направлення дуг, що з'єднують вершини графа ситуацiй при Т-зворотньому пошуку, протилежне направленню дуг, що з'єднують тi ж самi вершини при прямому пошуку.
R-зворотний пошук полягає в тому, що головна цiль задачi зводиться до сукупностi допомiжних пiдцiлей, якi досягнутi в вихiднiй ситуацiї. Щоб звести головну цiль до допомiжних пiдцiлей застосовуються оператори в зворотньому напрямку за типом редукцiї.
В процесi Т-зворотнього пошуку будується направлений граф, який називається І-АБО-графом [1].
В І-АБО-графi є выдiленими:
" початкова вершина, ступiнь заходу до якої дорiвнює 0;
" кiнцевi вершини, ступенi вихiду з яких дорiвнюють 0;
" заключнi вершини (кiнцевi), що задовiльняють правилу розмiчання заключних вершин;
" тупиковi вершини (кiнцевi), що задовiльняють правилу розмiчання тупикових вершин;
" вершини типу І (некiнцевi), ступенi вихiду з яких >1;
" вершини типу АБО (некiнцевi), ступенi вихiду з яких 1;
Інтерпретацiя дуг, вершин, а також правила розмiчання тупикових i заключних вершин залежать вiд класу задач, що вирiшуються.
Для задач дедуктивного виводу всi вершини І-АБО-графа, за виключенням вершин типу І, вiдповiдають елементам цiлi та пiдцiлей, що задаються окремими виразами. Вершини типу І вiдповiдають цiлi та пiдцiлям, у яких число елементiв >1.
Хай - І-вершина, що вiдповiдає пiдцiлi . Тодi дуги, якi виходять з , з'єднують цю вершину з вершинами, якi вiдповiдають елементам .
Дуги, якi виходять з АБО-вершин, вiдповiдають варiантам застосування операторiв в зворотньому напрямку до елементiв цiлi та пiдцiлей, якi зв'язанi з цими вершинами.
Для задач дедуктивного виводу використуються такi правила розмiчання заключних i
тупикових вершин І-АБО-графа.
Правило 1. Кiнцева вершина вважається заключною, якщо елементарна цiль або пiдцiль, що їй вiдповiдає, є досягнутою в вихiднiй ситуацiї.
Правило 2. Кiнцева вершина вважається тупiковою, якщо вона не є заключною i нема жодного оператора, який може бути застосован в зворотньому напрямку до елемента цiлi або пiдцiлi, що зв'язана з цiєю вершиною.
Для задач комплектування серед вершин І-АБО-графа, за винятком вершин типу І, цiлi вiдповiдає початкова вершина, пiдцiлям - всi iншi вершини.
Для iнтерпретацiї вершин типу І введемо визначення варiанта операторної сегментацiї цiлi або пiдцiлi.
Визначення 3. Варiантом операторної сегментацiї цiлi або пiдцiлi називається множина варiантiв застосування операторiв в зворотньому напрямку, така, що множина вихiдних виразiв цих операторiв включає множину недосягнутих елементiв цiлi або пiдцiлi.
Вершини типу І вiдповiдають варiантам операторних сегментацiй цiлi i пiдцiлей з числом варiантiв застосування операторiв > 1. Дуги, що ведуть до вершин, якi не є вершинами типу І, вiдповiдають варiантам застосування операторiв.
Для задач комплектування використуються такi правила розмiчання заключних i
тупикових вершин І-АБО-графа.
Правило 3. Кiнцева вершина вважається заключною, якщо цiль або пiдцiль, що їй вiдповiдає, є досягнутою в вихiднiй ситуацiї.
Правило 4. Кiнцева вершина вважається тупiковою, якщо вона не є заключною i не
iснує варiантiв операторної сегментацiї пiдцiлi, що зв'язана з цiєю вершиною.
Введемо рекурсивне визначення вирiшеностi i невирiшеностi вершин І-АБО-графа.
Визначення 4.
" Заключнi вершини вирiшенi.
" Тупiковi вершини невирiшенi.
" І-вершина вирiшена, якщо вирiшенi всi iї дочiрнi вершини, i невирiшена, якщоневирiшена хоча б одна з iї дочiрнiх вершин.
" АБО-вершина вирiшена, якщо вирiшена хоча б одна з iї дочiрнiх вершин, i невирiшена, якщо невирiшенi всi iї дочiрнi вершини.
R-зворотнiй пошук вирiшення задачi полягає в побудовi такого пiдграфа (І-АБО-графа), на якому у вiдповiдностi з визначенням 4 вихiдна вершина є або вирiшеной, або невирiшеной.
Визначення 5.Пiдграф І-АБО-графа з вирiшеною початковою вершиною називається вирiшуючим графом, а з невирiшеной початковою вершиною - графом спростування.
Приклади І-АБО-графа для задач дедуктивного виводу i комплектування приведено вiдповiдно на мал.2 i 3. (Тут вирiшенi вершини
Loading...

 
 

Цікаве