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

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

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

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

І-АБО-графiв заштриховано. Дуги, що виходять з І-вершин, зв'язано круговими лiнiями. Символи визначають j-ий варiант оператора , - j-ий елемент ц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чого сказати не можемо.
Із викладеного виходить, що R-зворотнiй пошук не може бути використан для задач планування дiй.
2.3. Двонаправлений пошук
Двонаправлений пошук включає в себе елементи прямого 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льна вершина. Тодi шлях, що з'єднує початковi вершини ГС, є вирiшуючим i вiдповiдає рiшенню задачi.
Приклади ГС прямого i зворотнього пошуку, якi побудованi при двонаправленому пошуку, приведено на мал.4.
Вершина - спiльна для ГС прямого i зворотнього пошуку. Шлях, що з'єднує вершини i , є вирiшуючим.
Графом зворотнього пошуку при R-двонаправленому пошуцi є граф пiдцiлей (ГП).
Графом пiдцiлей називається направлений зв'язаний граф, в якому вершини вiдповiдають цiлям або пiдцiлям, а дуги - варiантам застосування операторiв в зворотньому напрямку по типу редукцiї.
Вершина ГП, яка вiдповiдає цiлi, називається початковой.
Вирiшенiсть вершин графа пiдцiлей визначається вiдносно однiєї з вершин графа ситуацiй.
Визначення 6. Вершина графа пiдцiлей називається вирiшеной вiдносно вершини графа ситуацiй, якщо вiдповiдна цiль є досягнутою в ситуацiї, що вiдповiдає .
Граф пiдцiлей при R-двонаправленому пошуку є звичайно графом типу дерева.
Процес R-двонаправленого пошуку починається з зворотнього пошуку i продовжується кожного разу, доки в ГП не утвориться вершина, що буде вирiшеною вiдносно обраної вершини ГС. Пiсля цього починається прямий пошук по ГП. Вiн полягає в тому, що оператори, якi зв'язанi з вирiшеними вершинами ГП, виконуютьс я в прямому напрямку. При цьому вiдбувається нарощування вершин ГС i перехiд до батькiвських вершин ГП (BACK TRACKING).
Вар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дбувається вiдносно цiєї вершини.
Видбiр вершин в процесi нарощування ГП вiдбувається з числа фронтальних вершин.
Визначення 7. Вершина ГП називається фронтальною, якщо вона є невирiшеной вiдносно тiєї вершини ГС, що розглядається, i позначена мiткою, яка вiдзначає поточну вершину.
Ситуацiйними мiтками вершини ГП позначаються в момент їх утворення, а також в моменти зворотнього вiдслiдковування цих вершин (BACK TRACKING) при прямому пошуку.
Визначення 8. Вирiшуючим ГП називається пiдграф, у якого кожна вершина є вирiшена вiдносно однiєї з вершин вирiшуючого графа ситуацiй.
Приклади ГС i ГП, що побудованi при R-двонаправленому пошуку, приведено на мал.5. В ф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ї .Оскiльки вершина як i ранiш невирiшена вiдносно вершини , в ГП утворюється вирiшена вiдносно вершина . Пiсля цього в ГС
утворюється вершина , вiдносно якої в ГП немає вирiшених вершин. Подальше продовження R-двонаправленого пошуку призводить до утворення в ГС вершини , вiдносно якої в ГП є роз'язна вершина .
Вирiшуючий шлях в ГС видiлено жирними лiнiями (див. мал.5).
R-двонаправлений пошук зберiгає переваги прямого i R-зворотнього пошук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стю упорядкованою. Отже R-двонаправлений пошук може бути використан для рiшення задач планування дiй.
2.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ститься в описах цiлi, тобто за рахунок збiльшення .
2.5. Упорядкування елемент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 цих виразiв як схему для упорядкування елементiв пiдцiдей.
______________________________
* Розкриттям вершини ГС називається процес утворення її дочiрнiх вершин.
Для уточнення сказаного розглянемо к-й варiант застосування оператора в зворотньому напрямку до пiдцiлi .
Хай
- множина вхiдних виразiв
Loading...

 
 

Цікаве