Корінь дерева
ТП виготовлення фотошаблону
З захистом маскуючого шару
Дочірні вершини
Отримане безлічі вершин аналізується за наявності цільової вершини, тобто. вершини, що не має дочірніх вершин. Процедура продовжується до виявлення цільової вершини. На минулому малюнку цільовими вершинами є ABDK та ABDL – вершини 4-го рівня.
Пошук рішень має ітеративний характер, причому кількість ітерацій та вершин, розкритих до знаходження цільового стану, істотно залежить від порядку, в якому розкриваються вершини. Порядок розкриття вершин називається Стратегією пошуку.
Можна виділити два основні типи стратегій пошуку (рис. 6.4):
Сліпий перебір характеризується тим, що розташування цільових вершин та їхня близькість не впливають на порядок розкриття. Існує кілька методів сліпого перебору, представлених малюнку 6.5.
Для структурованого запису методів пошуку рішень у просторі станів введемо поняття списків відкритих вершин (ОТК) та закритих (ЗКР). Список закритих вершин - це список, де розміщуються ідентифікатори розкритих вершин та ідентифткатор вершини, яку потрібно розкрити на даний момент. Вершини зі списку ЗКР, крім останньої, не можна розкривати. Список відкритих вершин - це список, де розміщуються вершини, які можуть бути розкриті. Стратегії пошуку чи прийняття рішень відрізняються правилами розміщення вершин у списку ВТК та вибору чергової вершини для розкриття.
1. Метод повного перебору.
Тут вершини розкриваються у порядку, у якому вони були породжені.
Алгоритм, що реалізує цей метод, можна представити наступним чином:
1.1. Помістити початкову вершину до списку ВТК.
1.2. Якщо список ВТК порожній, подати сигналпро невдачу пошуку, в іншому випадку перейти до наступного кроку.
1.3. Взяти першу вершину зі списку ВТК та перенести її до списку ЗКР. Присвоїти вершині ідентифікатор V.
1.4. Розкрити вершину V. Помістити всі дочірні вершини, не які у списку ЗКР, наприкінці списку ВТК і побудувати покажчики, які від них до вершини V. Якщо вершина V немає дочірніх вершин, то перейти до шигу 1.2.
1.5. Перевірити, чи одна з дочірніх вершин V цільової. Якщо є, видати рішення; інакше перейти до кроку 1.2.
У цьому алгоритмі передбачається, що початкова вершина не задовольняє поставлену мету, хоча неважко ввести етап перевірки такої можливості. Вершини та покажчики, побудовані в процесі перебору, утворюють піддерево всього неявно певного дерева простору станів. Ми називатимемо таке піддерево деревом перебору.
У способі повного перебору неодмінно буде знайдено найкоротший шлях до цільової вершини за умови, що такий шлях взагалі існує. (Якщо такого шляху немає, то у вказаному методі буде оголошено про неуспіх у разі кінцевих графів, а у разі нескінченних графів алгоритм ніколи не закінчить свою роботу.)
2. Метод рівних цін.
Можуть зустрітися завдання, у яких рішенню пред'являються якісь інші вимоги, відмінні від вимоги отримання найкоротшої послідовності операторів. Привласнення дугам дерев певних цін (з наступним перебуванням вирішального шляху, що має мінімальну вартість) відповідає багатьом з таких обіцяних критеріїв. Більш загальний варіант методу повного перебору, званий методом рівних цін, дозволяє у всіх випадках знайти деякий шлях від початкової вершини до цільової, вартість якого мінімальна. У той час як у вище описаному алгоритміпоширюються лінії рівної довжини шляху від початкової вершини, у загальному алгоритмі, який буде описано нижче, поширюються лінії рівної вартості шляху.
Нехай кожній дузі поставлена у відповідність деяка функція вартості CIJ. Суть методу полягає у пошуку шляху мінімальної вартості. В іншому випадку перейдіть до наступного кроку. Розкриття вершин здійснюється у порядку зростання їх вартості. Якщо позначити через G(v) - вартість розкриття деякої вершини v, то алгоритм, що реалізує цей метод, можна представити наступним чином:
2.1. Помістити початкову вершину S0 до списку ВТК. Покласти G(S0)=0.
2.2. Якщо список ВТК порожній, подати сигнал про невдачу пошуку; в іншому випадку перейти до наступного кроку.
2.3. Взяти зі списку ВТК ту вершину, на яку величина G(v) має найменше значення, і помістити їх у список ЗКР. Присвоїти цій вершині ідентифікатор v.
2.4. Якщо є цільова вершина, то видати вирішальний шлях;
2.5. Розкрити вершину v. Для кожної дочірньої вершини vi обчислити вартість G(vi) за формулою G(vi)=G(v)+C(v,vi). Помістити ці вершини разом з відповідними ним G(vi) у список ВТК і побудувати покажчики, що йдуть від них до вершини v. Якщо вершина v немає дочірніх вершин, відразу перейти до кроку 2.
2.6. Перейти до кроку 2.
Алгоритм, що працює за методом рівних цін, може бути також використаний для пошуку шляхів мінімальної довжини, якщо просто покласти вартість кожного ребра, що дорівнюєодиниці. Якщо є кілька початкових вершин, алгоритм просто модифікується: на кроці (1) всі початкові вершини поміщаються в список ВІДКРИТИЙ. Якщо стани, що відповідають поставленій меті, можуть бути явно описані, то процес перебору можна пустити у зворотному напрямку, прийнявши цільові вершини в якостіпочаткових та використовуючи звернення оператора Г.
3. Спосіб перебору в глибину.
Якщо визначити глибину вершини числом, що дорівнює номеру її рівня, то при використанні методу перебору в глибину завжди розкривається та з вершин, яка має найбільшу глибину. Оскільки кілька вершин можуть мати однакову максимальну глибину, то передбачається, що є правило вибору однієї з них. Тобто. задається гранична глибина. Вершини, що мають глибину, що дорівнює граничній глибині, не розкриваються. Таким чином, метод перебору в глибину можна визначити як метод перебору, при якому розкривається та з вершин, яка має найбільшу глибину, меншу за граничну.
Такий підхід може призвести до процесу, що розгортається вздовж деякого марного шляху, тому потрібно запровадити деяку процедуру повернення. Після того як у процесі будується вершина з глибиною, що перевищує деяку граничну глибину, ми розкриваємо вершини найбільшої глибини, що не перевищує цього кордону і т.д.
Алгоритм, що реалізує метод перебору в глибину, можна представити у такому вигляді:
3.1. Помістити початкову вершину до списку ВТК.
3.2. Якщо список ВТК порожній, видати повідомлення про невдалий пошук, в іншому випадку перейти до кроку 3.
3.3. Взяти першу вершину зі списку ВТК та перенести її до списку ЗКР. Цій вершині присвоїти ідентифікатор v.
3.4. Якщо глибина вершини v дорівнює граничній глибині, перейти до кроку 2, інакше до кроку 5.
3.5. Розкрити вершину v. Помістити всі дочірні вершини на початок списку ВТК та побудувати покажчики, що йдуть від них до вершини v. Якщо v немає дочірніх вершин, то перейти до кроку 2.
В алгоритмі пошуку в глибину спочатку йде перебір уздовж одного шляху, доки не буде досягнуто максимальної глибини, потімрозглядаються альтернативні шляхи тієї ж чи меншої глибини, які відрізняються від нього лише останнім кроком, після чого розглядаються шляхи, що відзначаються останніми двома кроками, і т.д.
У всіх розглянутих методах перебору передбачається, що початкова вершина лише одна.
2. Методи впорядкованого перебору.
Більшість практичних завдань вдається сформулювати емпіричні правила, дозволяють зменшити обсяг перебору. Ці правила використовують специфічну інформацію про розв'язувану задачу, що формується на основі досвіду, інтуїції та здорового глузду експерта та інженера знань.
Інформацію такого роду називають евристичною, і засновані на ній методи та алгоритми евристичними. Основна ідея евристичних методів полягає в упорядкуванні списку відкритих вершин відповідно до певної міри, що оцінює "перспективність" вершини або шляху, на якому знаходиться ця вершина.
Такий захід називають ОЦІНОЧНОЇ ФУНКЦІЄЮ, а процедури такого типу методами впорядкованого перебору. Для чергового розкриття зі списку ВТК вибирається вершина, яка має мінімальне значення функції оцінки. Після кожного кроку розкриття проводиться перевпорядкування вершин у списку відповідно до значень оціночної функції.
Як оціночні функції можна вибрати функції, наведені на малюнку 6.6.
Немає жодних конструктивних рекомендацій до способів визначення оціночних функцій. Розглянемо її зміст з прикладу (рис.6.7)
Наприклад розглянемо розташування кубиків на майданчиках