. 5 , .
, , , , . - , .
( - ).
.
, , .
.
, , "" "" . , .
, . ( ) , , , . , , .
, , :
(1) , , , .
(2) , . , . (1).
- , "" .
, , , , , .. . .
, , , . "" , .
, , .. "" . , 1 2 , , .
, (best-first search).
|
|
- , , .
, .
, , , , "".
A* .
n :
f(n)=g(n)+h(n).
g(n) n , a h(n) n , () . f(n), "", .. n .
, f(n) .
*.
:
s ;
g ;
OPEN , , ;
CLOSED , .
(1) OPEN:={s}.
(2) OPEN:={}, . .
(3) OPEN n, f(n) ≤ f(m) m, OPEN, CLOSED
(4) , n, , ; n.
(5) g, . , g s.
(6) n', , .
f(n').
n' OPEN, CLOSED, , f(n') n.
n' OPEN CLOSED, f(n)=new c f(n')=old.
(7) old < new, .
(8) new < old, , , CLOSED, OPEN.
(9) .