Page 109 - 6109

Ргосеdure Best First Searght;
Begin
Помістити початкову вершину в Open; Сlosed:='порожній список';
While ОРЕN 'порожній список' Dо
Вegin
п:=«First (Open);
І п='цільова вершина' Тhen Вихід(УСПІХ);
Перемістити вершину n із списку Open в список Сlosed;
Розкрити вершину n, для кожної дочірньої вершини обчислити
h(ni)
перемістіть дочірньої вершини яких нема в списку Open і
Closed.в список Open взявши з кожної вершини показник на вершину
н.
Упорядкувати список Open по зросту значень h(n)
End
Вихід (неудача)
End
Даний алгоритм дозволяє успішно справлятися з проблемою локальних
мінімумів. Проте при цьому знижується ефективність самого процесу пошуку.
Ефективність процесу пошуку залишатиметься високої, якщо оцінка вартості
€
найкоротшого шляху ( )h n ) з вершини n в цільову вершину буде якомога
ближче до реальної вартості h(n).

11.4.3 А-алгоритм

Перевага алгоритму рівних цін полягає в тому, що він гарантує
знаходження оптимального шляху. Перевагою алгоритмів, що використовують
оцінку майбутніх витрат h € ( )n , є можливість усікання дерева пошуку, що

підвищує ефективність пошуку. Природним є прагнення комбінувати ці
алгоритми і враховувати як зроблені, так і майбутні витрати. Цього можна
добитися, якщо скористатися оцінною функцією
€
€( )n 
f € ( )n  g h ( )n
де f € ( )n – оцінка вартості шляху з початкової вершини у вершину n;
€
h ( )n – оцінка вартості найкоротшого шляху з вершини n в цільову вершину.
Алгоритм, що базується на використовуванні оцінної функції f € ( )n

називається А-алгоритмом. Оцінки h € ( )n в ході пошуку не міняють своїх
значень. Оцінки €( )g n також не міняють своїх значень і завжди рівні реальним

витратам g(n), якщо пошук шляху виконується на дереві станів. Проте при
пошуку шляху на графі станів оцінки €( )g n можуть мінятися. Отже, в
€
загальному випадку оцінки ( )f n міняють свої значення в процесі пошуку. Це
призводить до того, що вершини із списку Сlosed можуть переміщатися назад в
список Open:

Ргосеdure А_Searsh;
Вegin
Помістити початкову вершину S в список Open: f^(s)=h^(s)
Сlosed:='порожній список';

109