Стратегiї планування рiшень, Детальна інформація

Виб(р ST-оператора в стратег(( типу ППР-1 зд(йсню(ться з числа оператор(в, що ( застосовн( в прямому напрямку. В зв(язку з цим висока ШР при выкористанн( стратег(й цього типу досяга(ться т(льки при невеликому галуженн( в ГС. Зменшення ШР при зб(льшенн( галуження ГС трапля(ться за рахунок зб(льшення часу розпознавання застосування оператор(в.

В стратег(ях типу ППР-2 виб(р ST-оператора зд(йсню(ться з числа оператор(в, що ( застосовн( в зворотньому напрямку. В зв(язку з цим ППР-2 зобезпечу( високу ШР т(льки при невеликому галуженн( в ГП. Проте, оск(льки виб(р оператора в ППР-2 зд(йсню(ться без врахування застосовност( в прямому напрямку, (х ЦР менша, н(ж ППР-1.

Стратег(( типу ППР-1 ( ППР-2 допускають руйнування досягнутих елемент(в п(дц(лей ( тому мають велике ПШР.

Значно кращ( н(ж ППР-2 показники ЦР ( ПШР мають стратег(( типу ППР-3, в яких використу(ться стратег(чний прийом ор((нтац(( на п(дц(л( та ситуац((. В той самий час ШР ППР-3 менше, н(ж ППР-2, внасл(док додаткових витрат часу на розп(знавання застосовност( оператор(в в прямому напрямку.

Ще кращ( показники, н(ж ППР-3, по ПШР мають стратег(( типу ППР-4, як( не допускають руйнування досягнутих елемент(в п(дц(лей. Але через зб(льшення к(лькост( “в(дступ(в назад” внасл(док заборони на руйнування вже досягнутих елемент(в п(дц(лей ц( стратег(( мають мал( ЦР ( ШР.

Стратег(( типу ППР-5 ( ППР-6 передбачають апр(орне упорядкування елемент(в п(дц(лей ( в ц(лому б(льш ефективн(, н(ж ППР-1 - ППР-4. Але ПШР стратег(й ППР-5 б(льше, н(ж ППР-4, оск(льки вони допускають руйнування досягнутих елемент(в п(дц(лей. Б(льш ефективн( по ПШР, н(ж ППР-4 ( ППР-5, ( стратег(( типу ППР-6.

В ус(х стратег(ях, приведених в табл. 2, використу(ться стратег(чний прийом ор((нтац(( на дек(лька п(дц(лей чи його модиф(кац(я - ор((нтац(я на конкретизован( п(дц(л(, на п(дц(л( та ситуац((.К(льк(сть п(дц(лей, на як( ведеться ор((нтац(я в процес( вибору ST-оператора, ( параметром (ВС.

Виб(р п(дц(лей та ST-оператор(в викону(ться за допомогою оц(ночних функц(й.

, що використу(ться для в(дбору п(дц(лей в стратег(( з ор((нтац((ю на конкретизован( п(дц(л(, ма( такий вигляд:

, (7)

- ступ(нь досягнутост( (-й п(дц(л(;

- ступ(нь конкретизац(( (-й п(дц(л(;

- довжина шляху в(д вершини (-й п(дц(л( до початково( вершини ГП;

- коеф(ц((нт, який ( параметром системи ( зада( ступ(нь ц(льоспрямованост( р(шення.

.

Оц(ночна функц(я, що використову(ться для вибору ST-оператора в стратег(ях з ор((нтац((й на п(дц(л( та ситуац((, ма( вигляд:

, (8)

- ступ(нь досягнутост( (-й п(дц(л( п(сля застосування j-го оператора в прямому напрямку;

до поточной ситуац((.

в прямому напрямку;

- загальна к(льк(сть елемент(в (-о( п(дц(л(;

, що сп(впадають з недосягнутими елементами (-п(дц(л(.

.

.

Виб(р вершин ГС в ус(х стратег(ях викону(ться в порядку, що ( зворотн(м порядку (х утворення, доти, поки оц(ночна функц(я для n останн(х обраних оператор(в не почне зменшуватися (n - параметр системи). При зменшуванн( оц(ночной функц(( викону(ться в(дступ назад по ГС до вершини, з яко( почалось зменшування.

Стратег(( нел(н(йного планування

Стратег(( планування, як( були розглянут( вище, ор((нтован( на генерац(ю л(н(йних

план(в, що подаються як л(н(йн( посл(довност( ST-оператор(в. Але при р(шенн( практичних задач часто доводиться мати справу з нел(н(йними планами, як( необх(дно розглядати як часткове упорядкування ST-оператор(в. Подання план(в в вигляд( нел(н(йной посл(довност( ST-оператор(в дозволя(, з одного боку, зпростити процес р(шення задач з вза(мод(ючими п(дц(лями, а з другого боку - п(двищити ефективн(сть р(шення завдяки розпаралелюванню процес(в планування та реал(зац(( плану в багатопроцесорн(й (ВС.

Одн((ю з перших (ВС, здатних генерувати нел(н(йн( плани, була система NOAH [5]. Ця система стала основоположною для наступних систем, таких як NONLIN [6], DEVICER [7], SIPE [8] та (нш(.

Плани в систем( NOAH подаються у вигдяд( семантично( мереж(, багато в чому схож(й на с(тьовий граф(к виконання роб(т.