5.6 Пошук із поверненням
5.6.1 Вступ
Існує клас алгоритмів під назвоюbacktrackingalgorithms,що в перекладі означає «алгоритми з відкатом назад». Як правило, такі алгоритми будуються на основі рекурсії. Ці алгоритми відрізняються тим, що шукають рішення методом спроб і помилок, перебираючи всі або майже всі варіанти. Алгоритми із поверненням можна назвати «лобовими»; є набагато більш просунуті класи алгоритмів (динамічне програмування, «розділяй і володарюй», жадібні алгоритми). Тобто. коли доводиться мати справу із завданням пошуку раціонального рішення, коли неможливо застосувати жоден з відомих способів, здатних знайти оптимальний варіант рішення, і залишається вдатися до останнього засобу - повного перебору.
Така ситуація виникає у таких випадках:
Пошук оптимуму з перебором всіх варіантів;
Пошук будь-якого рішення з виходом за його знайденні;
Пошук оптимального рішення з оптимізацією повного перебору (відсіканням варіантів, які явно гірші від знайденого до цього моменту оптимального рішення).
5.6.2 Перебірні алгоритми
Розглянемо перебірні алгоритми, засновані на методах обходу графа з прикладу завдання знаходження найкоротшого шляху лабіринті. Оскільки існує два методи обходу графа, то й перебірних алгоритмів розглядатимемо два.
Лабіринт, що складається з прохідних та непрохідних клітин, заданий матрицеюAрозміромmn. Елемент матриціA[i,j]=0, якщо клітина (i,j) прохідна. ІнакшеA[i,j]=.
Потрібно знайти найкоротший шлях із клітини (1, 1) у клітину (m,n).
Фактично дана інвертована матриця суміжності (у ній нулі замінені , а одиниці – нулями). Лабіринтє граф.
Метод перебору з поверненням (по-англійськи званий backtracking ) заснований на методі пошуку в глибину. Перебір із поверненням – це метод спроб і помилок («спробуємо сходити в цей бік: не вийде – повернемося і спробуємо в інший»). Оскільки йдеться про перебор варіантів методом пошуку в глибину, то під час роботи алгоритму треба зберігати поточний шлях у дереві. Цей шлях є стек Way. Крім того, необхідний масив Dest, розмірність якого відповідає кількості вершин графа, що зберігає для кожної вершини відстань від неї до вихідної вершини.
Повернемося до нашого завдання. Нехай поточною є деяка клітина (на початку роботи алгоритму – клітина (1, 1)).
if для поточної клітини є клітина-сусід Neighbor, така що:
(відсутня у Way) and
(Dist[Neighbor]=0 або (Dist[Neighbor] > Length(Way))) then begin
додати Neighbor до Way;
поточна клітина: = Neighbor;
Лістинг 5.15 - Перебірний алгоритм проходження лабіринту
З наведеного вище фрагмента ясно, чому цей метод називається перебором із поверненням. Поверненню тут відповідає операція "витягти з Way", яка зменшує довжину Way на 1.
Перебір закінчується, коли Way порожній і робиться спроба повернення назад. У цій ситуації повертатися вже нема куди.
Way – це поточний шлях, але в процесі роботи необхідно зберігати ще й оптимальний шлях OptimalWay.
Зауважимо, що алгоритм можна вдосконалити, якщо не дозволяти, щоб довжина Way була більшою або дорівнює довжині OptimalWay. У цьому випадку якщо і буде знайдено якийсь варіант більшої довжини, він явно не буде оптимальним. Таке вдосконалення в загальному випадку означає, що як тільки поточний шлях стане свідомо неоптимальним, треба повернутисяназад. У деяких випадках це покращення алгоритму дозволяє сильно скоротити перебір.
Рисунок 5.14 – Пошук виходу з лабіринту шляхом пошуку у глибину
Перебірний алгоритм, заснований на пошуку завширшки, складається з двох етапів:
Поширення хвилі і є власне пошук завширшки, у якому клітини позначаються номером кроку методу, у якому клітина відвідується. При зворотному ході, починаючи з кінцевої вершини, йде відновлення найкоротшого шляху, яким у неї потрапили шляхом включення до нього клітин з мінімальною позначкою. Важливо, що відновлення починається з кінця (від початку воно часто неможливе).
Треба сказати, що перебір методом пошуку завширшки порівняно з перебором із поверненням, як правило, вимагає більше додаткової пам'яті, що витрачається на зберігання інформації необхідної для побудови шляху при зворотному ході та позначки відвіданих вершин, але і працює швидше, тому що зовсім виключається відвідування однієї і тієї ж клітини більш ніж один раз.
Рисунок 5.15 – Пошук виходу з лабіринту шляхом пошуку шириною
Як ще один приклад розглянемо гри двох осіб, які зазвичай описуються безліччю «позицій» і сукупністю правил переходу з однієї позиції до іншої, причому передбачається, що гравці ходять по черзі. Вважатимемо, що правилами дозволені лише кінцеві послідовності позицій і що у кожній позиції є лише кінцеве число дозволених ходів. Тоді для кожної позиціїpзнайдеться числоN(p) таке, що ніяка гра, що почалася вp, не може тривати більшеN(p) ходів.
Термінальними називають позиції, з яких немає дозволених ходів. На кожній з них визначено цілісну функціюf(p), що задає виграш того згравців, котрому належить хід у цій позиції; виграш другого гравця вважається рівним -f(p).
Малюнок 5.16 – Дерево гри «хрестики-нуліки»
Якщо з позиціїpєdдозволених ходівp1, …, pd, виникає проблема вибору найкращого з них. Будемо називати хід найкращим, якщо після закінчення гри він приносить найбільший можливий виграш за умови, що супротивник вибирає ходи, найкращі для нього (у тому ж сенсі). Нехайf(p) є найбільшим виграшем, досяжним у позиціїpгравцем, якому належить черга ходу, проти оптимального захисту. Оскільки після ходу в позиціюpiвиграш цього гравця дорівнює -f(pi),маємо
Ця формула дозволяє індуктивно визначитиf(p) для кожної позиціїp.
Нижченаведений алгоритм, званий пошуком із поверненням, обчислюєf(p).