Page 111 - 6109

(14) S

7
1 5
3
(7) (1)
1 1 1 10
(10) D C B A G
(4)
2

Рисунок 11.1 – Граф станів вершинами, що розкриваються декілька раз

Стани списків ОРЕN і СLOSED показані в таблиці 11.1. Кожний рядок
таблиці відповідає черговому кроку роботи алгоритму. Числа поряд з іменами
вершин відповідає значенням оцінної функції f € ( )n . З таблиці 11.1 виходить,

що вершина А розкривається чотири рази, вершина В – 3 рази, вершина C – 2
рази.
Таблиця 11.1 - Виконання А*-алгоритма
№ ОPEN CLOSED Коментар
1 S(14) -
2 А(8) В(9) C(10) D(11) s(14)
3 В(9) C(10) D(11) G(17) B(9) S(14)
4 А(7) C(10) D(11) G(17) В(9) S(14) Повернення: А
5 C(10) D(11) G(16) А(7) В(9) S(14)
6 А(6) В(8) D(11) G(15) C(10) S(14) Повернення: А, В
7 В(8) D(11) G(15) А(6) З(10) 5(14)
8 D(11) G(15) В(8) А(6) C(1 0) S(14)
9 C(9) G(15) D(11) В(8) А(6) S(14) Повернення: С

10 А(5) В(7) G(15) C(9) D(11) S(14) Повернення: А, В
11 В(7) G(14) А(5) C(9) D(11) S(14)
12 G(14) В(7) А(5) C(9) D(1 1) S(14)

Щоб А*-алгоритм не розкривав кілька разів одну і ту ж вершину,
необхідно враховувати умову монотонності
€
€
h ( )n  h ( )n  c ( , )n n (11.2)
i j i j
де n i, – батьківська вершина; n j – дочірня вершина; c(n i n j) – вартість
шляху між вершинами n i і n j.
Якщо умова монотонності дотримується для всіх дочірніх вершин, то
можна довести, що в той момент, коли розкривається деяка вершина n,
€
оптимальний шлях до неї вже знайдений. Отже, оцінна функція ( )f n для даної
вершини надалі не міняє своїх значень, і ні які вершини із списку Сlosed в
список Open не повертаються.
Раніше наголошувалося, що А*-алгоритм недооцінює витрати h(n). Умова
монотонності означає, що недооцінка на шляху до мети стає все меншою або, в
крайньому випадку, не змінюється. Дійсно, якщо позначити недооцінку через
u
€( )n , то

111