Page 106 - 6109

Еnd.
На початку пошуку список CLOSED порожній, а OPEN містить тільки
початкову вершину. Кожного разу із списку Open вибирається для розкриття
перша вершина (виклик функції First(Open)). Розкрита вершина переміщається
в список Closed, а її дочірні вершини поміщаються в початок списку Open.
Таким чином, на наступному кроці розкриватимуться дочірні вершини поточної
вершини n. Принцип формування списку Open в цьому випадку відповідає
стеку, тобто вершина, додана в список останньої, обробляється першою (LIFO –
Last In First Out). Якщо прослідити напрям пошуку по дереву станів, то фронт
пошуку росте в глибину. Для побудови зворотного шляху (з цільової вершини в
початкову вершину) всі дочірні вершини забезпечуються покажчиками на
відповідні батьківські вершини.
Процедура пошуку завширшки відрізняється від розглянутої процедури
пошуку в глибину тим, що дочірні вершини, одержувані при розкритті вершини
n, поміщаються в кінець списку Open Отже, при пошуку в ширину принцип

формування списку Open відповідає черзі, тобто вершина, внесена в список
першої, обробляється першою (FIFO – First In First Out ). Завдяки цьому фронт
пошуку росте вширину, що гарантує знаходження шляху з мінімальною
кількістю дуг (ребер) між початковою і цільовою вершинами (свого роду
оптимальності).
11.3.3 Алгоритм рівних цін

Інформованість про вирішувану задачу тут вище, ніж у разі пошуку в
глибину і ширину. Кожному оператору, що перетворює стан n i, в стан n j,
ставиться у відповідність деяка функція вартості c(n i, n j), що характеризується
позитивними значеннями. В ході пошуку шляху на графі враховуються сумарні
витрати для досягнення тієї або іншої вершини, тобто вартість шляху до цієї
вершини. Вартість шляху до вершини n j, може бути визначена по наступній
формулі
g(n j) = g(n i) + c(n j. n i)
де g(n j) – вартість шляху з початкової вершини у вершину n j.
В ході пошуку вершини в списку OPEN сортуються в порядку збільшення
вартості. Кожного разу розкривається вершина з якнайменшою вартістю. Це
дозволяє знайти шлях мінімальної вартості з початкової вершини в цільову
вершину. Слід зазначити, що в процесі пошуку вартість шляху до вершини
може мінятися, якщо виявляється більш дешевий шлях. Тому позначатимемо
вартість оптимального шляху з початкової вершини у вершину n через €( )g n , а

вартість поточного шляху, знайденого алгоритмом, через g(n), тобто €( )g n – це
оцінка вартості шляху g(n). В кінці пошуку €( )g n  g ( )n .
Нижче представлена процедура пошуку оптимального шляху
(мінімальної вартості), записана на псевдомові:

Procedure Optimal Search;
Begin
Помістити початкову вершину в список Open;
Сlosed:='порожній список';

106