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

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

ГоловнаМатематика, Геометрія, Статистика → Стратег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лей є характерним для ІВС, заснованих на процедурному засобi представлення задачi.
Схеми упорядкування розробляються в процесi формалiзацiї задач на основi докладного вивчення семантики проблемной галузi.
2.6. Ор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]).
3. Новi стратегiчнi прийоми
Однiєю з головних причин, що обумовлюють труднощi вирiшення задач в складних середовищах, є значне поширення обсягу пошуку шляху рiшення внаслiдок збiльшення кiлькостi застосованих операторiв в кожнiй ситуацiї моделi середовища. Розглянемо новi стратегiчнi прийоми, розробленi для реалiзацiї процесiв рiшення в складних середовищах.
3.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дцiлей.
Хай - кiлькiсть досягнутих елементiв пiдцiлi -загальна кiлькiсть елементiв , тодi ступiнь досягнутостi для пiдцiдi визначається так:
0, якщо ;
= (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дцiлi буде, якщо , .
Пошук шляху рiшення при орiєнтацiї на декiлька пiдцiлей виконується бiльш широким фронтом, нiж при орiєнтацiї на одну пiдцiль. Зfвдяки цьому збiльшується йiмовiрнiсть вибору оператора шляху рiшення задач с довгими шляхами рiшення.
3.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 п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лi, - загальна кiлькiсть змiнних , тодi ступень конкретизацiї для пiдцiлi визначаться таким чином:
, якщо або = 0
= (2)
, якщо i > 0
Максимальна ступiнь конкретизацiї буде, якщо i 0 i = , в цьому випадку =1.
Орiєнтацiя на конкретизованi пiдцiлi призводить до збiльшення iнформацiї про шляхи рiшення.
3.3. Орiєнтацiя на пiдцiлi та ситуацiї
Цей прийом використовується в поєднаннi з R-двонаправленим пошуком i є подальшим розвитком орiєнтацiї на декiлька пiдцiлей.
Черговий оператор рiшення вибирається так, щоб получити найбiльшу ступнь досягнення однiєї з пiдцikей. Якщо цiq вимозi задовiльняє декiлька операторiв, перевагу вiддається тим з них, якi мають найбiльшу ступень застосованностi в прямому напрямку.
Хай - кiлькiсть елементарних умов застосування оператора , якi виконуються в ситуацiї ; - загальна кiлькiсть елементарних умов застосування . Тодi ступiнь застосування в прямому напрямку для оператора визначається таким чином:
0, якщо = 0;
= (3)
, якщо > 0;
Отже, якщо оператор може бути застосован до ситуацiї , то , а =1.
Спрощення пiдзадачи вибору оператора при орiєнтацiї на пiдцiлi та ситуацiї досягається завдяки збiльшенню обсягe 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.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єнтована на певний клас задач.
Визначення 9. Стратег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]:
,
де - позначення PF-оператора;
- логiчна умова;
- оператор кiнця рiшення.
Стрiлка позначує операцiю передачи керування. На кiнцi стрiлки ставиться цифра. Вона показує номер оператора, на який передається керування. Такi ж самi цифри ставляться над вiдповiдними операторами. PF-оператори, що використуються для опису стратегiй, приведено в табл. 1. Цi оператори реалiзують стратегiчнi прийоми орiєнтацiї не декiлька пiдцiлей, на конкретизованi пiдцiлi, на пiдцiлi та
Loading...

 
 

Цікаве