Page 63 - 6103

шляхи, що ведуть до цільової вершини, розташовані
приблизно на одній і тій же глибині. Обидва сліпих методи
вимагають великої витрати часу і тому необхідні спрямовані
методи пошуку.
Метод гілок і границь. З незакінчених шляхів, що
формуються в процесі пошуку, вибирається найкоротший і
продовжується на один крок. Отримані нові незакінчені
шляхи (їх стільки, скільки гілок у даної вершини)
розглядаються поряд зі старими, і знову продовжується на
один крок найкоротший з них. Процес повторюється до
першого досягнення цільової вершини, рішення
запам'ятовується. Потім з незакінчених шляхів, що
залишилися, виключаються довші, ніж закінчений шлях, або
рівні йому, а що залишилися продовжуються за таким же
алгоритмом доти, доки їхня довжина менша за закінчений
шлях. У підсумку або всі незакінчені шляхи виключаються,
або серед них формується закінчений шлях, більш коротший,
ніж раніше отриманий. Останній шлях починає відігравати
роль еталона і т.д.
Алгоритми пошуку шляху на графі розрізняються також
напрямком пошуку. Існують прямі, зворотні й двонаправлені
методи пошуку. Прямий пошук іде від вихідного стану і, як
правило, використовується тоді, коли цільовий стан заданий
неявно. Зворотний пошук іде від цільового стану і
використовується тоді, коли вихідний стан заданий неявно, а
цільовий – явно. Двонаправлений пошук вимагає
задовільного рішення двох проблем: зміни напрямку пошуку
й оптимізації "точки зустрічі". Одним із критеріїв для
рішення першої проблеми є порівняння "ширини" пошуку в
обох напрямках – вибирається той напрямок, який звужує
пошук. Друга проблема викликана тим, що прямий і

64