Page 108 - 6109

вершини, тобто є мірою вартості шляху, що залишився.
€
Чим менше значення ( )h n , тим більше «перспективний» шлях, на якому
знаходиться вершина n.
Подібний алгоритм використовується при пошуку екстремумів функції.
Відомо, що положення екстремуму функції багатьох змінних визначається
напрямом вектору градієнта функції. Тому пошук екстремуму здійснюють у
напрямі найбільшого зростання (убування) функції, тобто в напрямі,
співпадаючому (або протилежному) з напрямом градієнта. Пошук максимуму
функції в цьому випадку нагадує сходження на пік по найкрутішому маршруту.
Тому даний алгоритм і називають алгоритмом «підйому на гору».
На черговому кроці алгоритму для кожної з дочірніх вершин n 1, n 2,..., n m
€
вершини n обчислюється значення оцінної функції ( )h n , і для продовження
i
шляху вибирається вершина з якнайменшим значенням h € ( )n . Процедура
i
€
€
пошуку терпить невдачу, якщо для всіх дочірніх вершин ( )h n  h ( )n .
i
Ргосеdure Hill Climbing;
Begin
n:='початкова вершина'; Whilе n<> 'початкова вершина' Dо
Веgin
Розкрити вершину n і для всіх дочірніх вершин n i обчислити
оцінки h(n i)
Вибрати дочірню вершину n i, з мінімальним значенням h(n i);
If h^(n i) >= h^(n) Тhen Вихід(НЕВДАЧА);
n:=n i;
End;
Вихід(УСПІХ);
Еnd.

Існують різні способи побудови евристичної оцінної функції, проте
готових рецептів немає. При рішенні кожної конкретної задачі використовують
раніше накопичений досвід рішення подібних задач.

11.4.2 Глобальний облік відповідності мети
Цей алгоритм пошуку рішення задачі схожий на попередній. Тут також
оцінюється «перспективність» того або іншого шляху за допомогою
€
евристичної оцінної функції ( )h n . Відмінність полягає в тому, що на кожному
етапі виконується не локальне порівняння вершин, одержаних при розкритті
поточної вершини, а глобальне порівняння всіх вершин-кандидатів, що
знаходяться в списку Open. Для цього список відкритих вершин сортується в
€
порядку зростання значень ( )h n . Якнайкраща вершина для продовження шляху
знаходитиметься на першому місці в списку Open. Тому даний алгоритм
називають також алгоритмом вибору першої якнайкращої вершини (Best-First)
Процедура пошуку, заснована на даному алгоритмі, схожа на процедуру
Optimal Seargh. Відмінність полягає в тому, що замість функції вартості €( )g n
€
застосовується евристична функція ( )h n , тобто враховуються тільки майбутні
витрати:

108