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

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

ГоловнаМатематика, Геометрія, Статистика → Стратег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й. Таким чином, при моделюваннi плана утворюється новий бiльш детальний план.

Особистий пiдплан для кожного вузла буде правильним, але немає гарантiї, що буде правильним план вцiлому, через можливi взаємодiї мiж новими докладними кроками. Наприклад, розширення, що входять в план на мал. 6, в при уточненнi плану на мал. 6, б, роблять загальний план некоректним, тому що вони передбачають фарбування драбини ранiш фарбування стелi.

Loading...

 
 

Цікаве