Page 112 - 6109

€( )n 
u h ( )n  h € ( )n , €( ) 0u n 
З умови монотонності виходить, що €( )u n  u
€( )n , тобто недооцінка h(n) в
j i
батьківських вершинах більше або рівно недооцінкам h(n) в дочірніх вершинах.
На графі, зображеному на рис 11.1, умова монотонності не виконується для
початкової вершини. Наприклад,
h(S) > h(D) + c(S, D), тобто 14 > 10 + 1.
€
Якщо ( )h n  h ( )n , то інформованість є повною. В цьому випадку ніякого
пошуку не відбувається і наближення до мети йде по оптимальному шляху.
Таким чином, властивості А-алгоритму істотно залежать від умов, яким
€
задовольняє або не задовольняє евристична частина оцінної функції ( )f n :
1) А-алгоритм відповідає алгоритму рівних цін, якщо h(n) = 0;
€
2) А-алгоритм гарантує оптимальне рішення, якщо ( )h n  h ( )n ; в цьому
випадку він називається А* - алгоритмом;
3) А-алгоритм забезпечує однократне розкриття вершин, якщо
€
€
виконується умова монотонності ( )h n  h ( )n  c ( , )n n ;
i j i j
4) алгоритм A1* евристично більш сильний, ніж алгоритм A2* при
€
€
h ( )n  h ( )n ;
1 2
€
5) А*-алгоритм повністю інформований, якщо ( )h n  h ( )n ;
€
6) при h ( )n  h ( )n А-алгоритм не гарантує отримання оптимального
рішення, проте часто рішення виходить швидко.

11.5 Простір задач і простір станів

Методики планування цілеспрямованих дій прийнято розподіляти на два
класи: планування в просторі станів і планування в просторі задач.
При плануванні в просторі станів заданим вважається деякий набір
станів (ситуацій). Відомі дії, які може здійснювати система та які визначають
перехід з одного стану до іншого.
Графом станів задачі називається орієнтований граф, вершини якого
відповідають можливим станам предметної області, а дуги – методам
переходу від стану до стану.
Дуги можуть мати мітки, які інтерпретуються як вартість або довжина
відповідного переходу. Тоді вирішення задачі являє собою пошук шляху від
початкового стану до цільового; при цьому типовою є вимога оптимізації
даного рішення, тобто пошуку найкоротшого шляху. Відповідно, після того як
зведення задачі до формальної моделі проведено можна використовувати відомі
алгоритми пошуку шляхів на графах (алгоритми Мура, Дейкстри, гілок і
границь і т. п.).
Класичним прикладом планування в просторі станів можна вважати
задачу пошуку шляху від одного міста до іншого.
Планування в просторі задач передбачає декомпозицію початкової задачі
на підзадачі, поки не буде досягнуто зведення до задач, для яких є готові
алгоритми вирішення. Таку декомпозицію зручно уявляти собі у вигляді І/АБО-

112