Бектрекінг

Опишемо загальний метод, який дає змогу значно зменшити обсяг обчислень в алгоритмах типу повного перебору всіх можливостей. Щоб застосувати цей метод, розв'язок задачі повинен мати вигляд скінченної послідовності ( х₁, …, х_п). Головна ідея методу полягає в тому, що розв'язок будують поступово, починаючи з порожньої послідовності λ (довжини 0). Загалом, якщо є частковий (неповний) розв'язок (х₁, …, х_і), де і < п, то намагаємося знайти таке допустиме значення х_і+1, що можна продовжувати (х_1, …, х_і, х_і+1) до одержання повного розв'язку. Якщо таке допустиме, але ще не використане значення х_і+1, існує, то долучаємо цю нову компоненту до часткового розв'язку та продовжуємо процес для послідовності (х₁,..., x_i, x_i+1). Якщо такого значення х_і+і немає, то повертаємося до попередньої послідовності (х₁,..., x_i-1) і продовжуємо процес, шукаючи нове, іще не використане значення х_і^’. Тому процес називають бектрекінгом (англ. backtracking — пошук із поверненнями).

Роботу цього алгоритму можна інтерпретувати як процес обходу якогось дерева. Кожна його вершина відповідає якійсь послідовності (х₁, x_i), причому вершини, які відповідають послідовностям вигляду (х₁ ,..., х_i, у), - сини цієї вершини. Корінь дерева відповідає порожній послідовності.

Виконується обхід цього дерева пошуком углиб. Окрім того, задають предикат Р, означений на всіх вершинах дерева. Якщо P(v) = F, то вершини піддерева з коренем у вершині v не розглядають, і обсяг перебору зменшується. Предикат P(v) набуває значення F тоді, коли стає зрозумілим, що послідовність (х₁, …, х_i), яка відповідає вершині v, ніяким способом не можна добудувати до повного розв'язку.

Проілюструємо застосування алгоритму бектрекінг на конкретних прикладах.

Рис. 5.1. Визначення гамільтонових циклів у графі.

Пошук усіх гамільтонових циклів у графі з п'ятьма вершинами можна проілюструвати за допомогою дерева. Роботу алгоритму почато з одноелементної послідовності, бо в циклі вибір першої вершини неістотний. Розв'язки задачі обведено, і до них у прямокутних рамках приписано відповідні гамільтонові цикли. Отже, замість побудови й аналізу 5! = 120 послідовностей довжиною 5 вершин графа, зображеного на рис. 5.1, ми розглянули лише 23 послідовності довжиною від 1 до 5.

Приклад 5.2. Розфарбовування графа в n кольорів. Нехай вершини графа позначено як а, b, с, .... Спочатку розфарбуємо вершину а в колір 1, а потім — вершину b в той самий колір, якщо b не суміжна з вершиною а, а ні, то розфарбуємо вершину b в колір 2. Перейдемо до третьої вершини с. Використаємо для вершини с колір 1, якщо це можливо, а ні, то колір 2, якщо це можливо. Тільки якщо жоден із кольорів 1 і 2 не можна використовувати, розфарбуємо вершину с в колір 3. Продовжимо цей процес, доки це можливо, використовуючи один з п

Рис. 5.2. Розфарбування графа в n кольорів

Приклад 5.3. Задача про N ферзів. Умова: як п ферзів можна розмістити на шахівниці пxn, щоб жодні два ферзя не били один одного? Для розв'язання цієї задачі потрібно визначити n позицій на шахівниці так, щоб жодні дві позиції не були в одному рядку, в одному стовпці та на одній діагоналі. Діагональ містить усі позиції з координатами такі, що і +j=m для якогось т, або i-j=m (тут і — номер рядка, j — номер стовпця). Починаємо з порожньої шахівниці. На (k+1) -му кроці намагаємося розмістити нового ферзя в (k+1) -му стовпці, причому в перших k стовпцях уже є ферзі. Перевіряємо клітинки в (k + 1) - му стовпці, починаючи з верхньої. Шукаємо таку позицію для ферзя, щоб він не був у рядку та на діагоналі з тими ферзями, які вже є на шахівниці. Якщо це неможливо, то повертаємося до місця ферзя на попередньому k-му кроці та розміщаємо цього ферзя на наступному можливому рядку в цьому k-му стовпці, якщо такий рядок є, а ні, то повертаємося до ферзя в (k-1) -му стовпці. Алгоритм бектрекінг для n = 4 проілюстровано на рис. 5.3.

Рис.5.3.Задача про N ферзів.

Приклад 5.4. Сума елементів підмножин. Задано множину натуральних чисел (х_1, х₂, …, х_n ). Потрібно знайти її підмножину, сума елементів якої дорівнює заданому числу М.

Рис.5.4 Сума елементів підмножин.

Приклад 5.5. Побудова всіх максимальних незалежних множин вершин у простому графі G = (V, Г). Тут граф подано як пару, утворену множиною вершин V та відповідністю Г, котра показує, як зв'язані між собою вершини. Почнемо з порожньої множини й будемо додавати до неї вершини зі збереженням незалежності. Нехай — уже отримана множина з k вершин, — множина вершин, котрі можна додати до , тобто ø. Серед вершин розрізняють ті, котрі вже було використано для розширення (їх позначають ), і ті, котрі ще не використано (їх позначають ). Загальна схема алгоритму бектрекінг для задачі побудови максимальних незалежних множин вершин у простому графі має такий вигляд.

Прямий крок від до полягає у виборі вершини

Крок повернення від до

Якщо множина вершин S_k максимальна, то ø. Якщо ø, то множину було розширено раніше, і вона не максимальна. Отже, перевірку максимальності задають такою умовою: ø.

Доцільно намагатися почати кроки повернення якомога раніше, бо це обмежить розміри „непотрібної” частини дерева пошуку. У зв'язку з цим зауважимо таке. Нехай і ø. Цю вершину неможливо вилучить з , оскільки можна вилучати лише вершини, суміжні з вершинами множини . Отже, існування такої вершини , що і ø — достатня умова для повернення. Окрім того, .

Алгоритм побудови всіх максимальних незалежних множин вершин у простому графі G = (V, Г).

Наведемо кроки алгоритму.

Крок 1. Ініціалізація. Виконати ø, ø, , .

Крок 2. Прямий крок. Вибрати вершину і побудувати, як описано вище, множини , , ; при цьому залишити та без змін. Виконати .

Крок 3. Перевірка. Якщо виконано умову ø, то перейти до кроку 5, інакше до кроку 4.

Крок 4. Якщо ø. то надрукувати максимальну незалежну множину та перейти до кроку 5. Якщо ø, а ø, то перейти до кроку 5. Інакше перейти до кроку 2.

Крок 5. Крок повернення. Виконати . Вилучити вершину із , щоб одержати . Виправити та , для чого вилучити вершину із множини і долучити її до . Якщо та ø, то зупинитися (на цей момент уже буде надруковано всі максимальні незалежні множини). Інакше перейти до кроку 3.