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

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

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

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

ситуацiї.
Стратегiчнi прийоми та операторнi схеми для шести типiв стратегiй приведено в табл. 2. Операторн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шення (ЦР):
ЦР = , (4)
де - сумарний обсяг вирiшуючих ГС i ГП;
- сумарний обсяг ГС i ГП, побудованих в процесi пошуку шляху рiшення.
Подовження шляху рiшення (ПШР):
ПШР = , (5)
де - довжина одержаного шляху рiшення;
- мiнiмальна довжина шляху рiшення.
Швидкiсть рiшення (ШР):
ШР = , (6)
де - час рiшення.
Розглянемо характернi особливостi кожного типу стратегiй, приведених в табл. 2.
Вибiр ST-оператора в стратегiї типу ППР-1 здiйснюється з числа операторiв, що є застосовнi в прямому напрямку. В зв'язку з цим висока ШР при выкористаннi стратегiй цього типу досягається тiльки при невеликому галуженнi в ГС. Зменшення ШР при збiльшеннi галуження ГС трапляється за рахунок збiльшення часу розпознавання застосування операторiв.
В стратегiях типу ППР-2 вибiр ST-оператора здiйснюється з числа операторiв, що є застосовнi в зворотньому напрямку. В зв'язку з цим ППР-2 зобезпечує високу ШР тiльки при невеликому галуженнi в ГП. Проте, оскiльки вибiр оператора в ППР-2 здiйснюється без врахування застосовностi в прямому напрямку, їх ЦР менша, нiж ППР-1.
Стратегiї типу ППР-1 i ППР-2 допускають руйнування досягнутих елементiв пiдцiлей i тому мають велике ПШР.
Значно кращi нiж ППР-2 показники ЦР i ПШР мають стратегiї типу ППР-3, в яких використується стратегiчний прийом орiєнтацiї на пiдцiлi та ситуацiї. В той самий час ШР ППР-3 менше, нiж ППР-2, внаслiдок додаткових витрат часу на розпiзнавання застосовностi операторiв в прямому напрямку.
Ще кращi показники, нiж ППР-3, по ПШР мають стратегiї типу ППР-4, якi не допускають руйнування досягнутих елементiв пiдцiлей. Але через збiльшення кiлькостi "вiдступiв назад" внаслiдок заборони на руйнування вже досягнутих елементiв пiдцiлей цi стратегiї мають малi ЦР i ШР.
Стратегiї типу ППР-5 i ППР-6 передбачають апрiорне упорядкування елементiв пiдцiлей i в цiлому бiльш ефективнi, нiж ППР-1 - ППР-4. Але ПШР стратегiй ППР-5 бiльше, нiж ППР-4, оскiльки вони допускають руйнування досягнутих елементiв пiдцiлей. Бiльш ефективнi по ПШР, нiж ППР-4 i ППР-5, є стратегiї типу ППР-6.
В ус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 вибору ST-оператора, є параметром ІВС.
Вибiр пiдцiлей та ST-оператор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дцiлi;
- довжина шляху вiд вершини i-й пiдцiлi до початкової вершини ГП;
- коефiцiєнт, який є параметром системи i задає ступiнь цiльоспрямованостi рiшення.
В стратегях, що не мiстять орiєнтацiю на конкретизованi пiдцiлi, формула для , має такий же вигляд (7), але без доданка .
Оцiночна функцiя, що використовується для вибору ST-оператора в стратегiях з орiєнтацiєй на пiдцiлi та ситуацiї, має вигляд:
, (8)
де - ступiнь досягнутостi i-й пiдцiлi пiсля застосування j-го оператора в прямому напрямку;
- ступ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я для n останнiх обраних операторiв не почне зменшуватися (n - параметр системи). При зменшуваннi оцiночной функцiї виконується вiдступ назад по ГС до вершини, з якої почалось зменшування.
3.5. Стратег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дно розглядати як часткове упорядкування ST-операторiв. Подання планiв в виглядi нелiнiйной послiдовностi ST-операторiв дозволяє, з одного боку, зпростити процес рiшення задач з взаємодiючими пiдцiлями, а з другого боку - пiдвищити ефективнiсть рiшення завдяки розпаралелюванню процесiв планування та реалiзацiї плану в багатопроцесорнiй ІВС.
Однiєю з перших ІВС, здатних генерувати нелiнiйнi плани, була система NOAH [5]. Ця система стала основоположною для наступних систем, таких як NONLIN [6], DEVICER [7], SIPE [8] та iншi.
Плани в системi NOAH подаються у вигдядi семантичної мережi, багато в чому схожiй на сiтьовий графiк виконання робiт.
Кожний вузол мережi вiдображує певну дiю на деякому рiвнi подробицi та мiсьтить як процедурну, так i описову iнформацiю. Вузли з'єднуються, утворюючи iєрархiчнi частково упорядкованi описи операцiй та планiв дiй.
Існують вузли чотирьох типiв:
" GOAL - вузли, якi зображують цiлi, що можуть бути досягнутi;
" PHANTOM - вузли, якi зображують цiлi, що вже досягнутi;
" SPLIT - вузли, що мають ступiнь заходу 1, ступiнь виходу >1 i зображують розгалуження часткового упорядкування;
" JOIN - вузли, що мають ступiнь заходу >1, ступiнь виходу 1 i зображують з'єднання пiдпланiв в часткове упорядкування.
Кожному вузлу надаються два списки: доповнень та виключень. Вони мiстять символiчнi вираження, описуючи змiни в ситуацiї, що визванi дiями, вiдповiдними даному вузлу.
Розглянемо, наприклад, мережу, що зображує iєрархiю планiв фарбування стелi i фарбування драбини [5]. Абстрактно цей план може бути зображений одним вузлом, як показано на мал. 6, а. Бiльш докладний план є кон'юнкцiєю двох дiй (мал. 6, б). Ще бiльш докладнi плани мали би бути: "ВiЗЬМИ ФАРБУ; ВiЗЬМИ ДРАБИНУ; ПОФАРБУЙ СТЕЛЮ;" i "ВiЗЬМИ ФАРБУ; ПОФАРБУЙ ДРАБИНУ;", як показано на мал. 6, в.
В системi NOAH використовується стратегiя iєрархiчного нелiнiйного планування. Ця стратегiя моделює бiльш детальний план, моделюючи кожний вузол плану по черзi. Моделювання (розширення) вузла полягає в застосуваннi ST-оператора, який є моделлю дiї, вiдповiдной даному вузлу. При цьому до мережi додаються новi вузли з бiльш детальними дiями i змiнюється модель ситуацiї з урахуванням впливу цих дiй. Таким чином, при
Loading...

 
 

Цікаве