Зворотний перехід

Зворотний перехід (англ. backjumping) — одна з технік, що дозволяє зменшити простір пошуку у алгоритмах пошуку з поверненням, завдяки чому підвищується ефективність роботи. Суть методу полягає в тому, щоб повертатись не на один крок назад, як у бектрекінгу, а відразу на декілька.

Обхід дерева пошуку алгоритмом з поверненням
Ілюстрація зворотного переходу: сірий вузол не відвідується

Визначення

Коли алгоритм пошуку з поверненням перебрав усі можливі значення змінної, він повертається до попередньої змінної і або надає їй наступного значення, або повертається ще вище. Інакше кажучи, якщо $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ — поточна підстановка ( $x_{i}$ — змінна, $a_{i}$ — її значення) і алгоритм вже перебрав усі можливі значення для $x_{k+1}$ , то рішення, що починається з поточної підстановки, не існує. Після цього алгоритм переходить на рівень вище (де поточною підстановкою є $x_{1}=a_{1},\ldots ,x_{k}-1=a_{k}-1$ ) і або змінює значення $x_{k}$ на наступне, або повертається ще на рівень вище.

Щоб довести, що при жодному значенні $x_{k+1}$ ми не досягнемо розв'язку, не обов'язково перебирати усі такі значення. Якщо алгоритм може довести, що існує індекс $j<k$ такий, що префікс $x_{1},\ldots ,x_{j}=a_{1},\ldots ,a_{j}$ ніяким чином не може бути доповнений до рішення, він може одразу перейти до зміни $x_{j}$ , не перебираючи піддерево поточної підстановки. Індекс $j$ , для якого алгоритм може довести вищезазначену властивість, називається «безпечним стрибком».


Для поточної підстановки $x_{1}x_{2}x_{3}x_{4}$ були перевірені усі можливі значення $x_{5}$ , і всі вони виявились невдалими. Алгоритм з поверненням переходить до $x_{4}$ і намагається присвоїти їй нове значення.	Замість повернення на попередній крок алгоритм проводить додаткові обрахунки і встановлює, що підстановки $x_{1}x_{2}x_{5}=211$ , $x_{1}x_{5}=22$ і $x_{1}x_{2}x_{5}=213$ не є частинами будь-якого розв'язку.	В результаті встановлюється, що поточна підстановка $x_{1}x_{2}$ не є частиною розв'язку, тому алгоритм переходить безпосередньо до $x_{2}$ і намагається присвоїти їй нове значення.

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

Різні алгоритми визначають безпечність переходів по-різному, проте більш трудомісткі алгоритми визначення можуть окупатися за рахунок того, що більш високі переходи дозволяють економити час на переборі піддерев.

Зворотний перехід на листках дерева

Найпростішим випадком, в якому можливий зворотний перехід, є ситуація, коли усі можливі значення змінної є недопустимими. Наприклад, у задачі виконання обмежень поточна підстановка може задовольняти усім обмеженням, але може не існувати таких її розширень, що також задовольняють обмеженням. Така ситуація, коли усі значення змінної $x_{k+1}$ конфліктують із поточною підстановкою $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$ , а сама змінна $x_{k+1}$ є листком (тобто не має нащадків), називається «листовим глухим кутом».

Алгоритм із зворотним переходом за авторством Gaschnig робить перехід лише на листках. Інакше кажучи, він відрізняється від пошуку з поверненням лише тим, що може не перевіряти піддерева листків (тобто не перебирати усі можливі значення змінної $x_{k+1}$ ).

Безпечний перехід може бути знайдений визначенням для кожного значення $a_{k+1}$ найкоротшого префікса підстановки $x_{1},\ldots ,x_{k}=a_{1},\ldots ,a_{k}$ , що не сумісний з підстановкою $x_{k+1}=a_{k+1}$ . Інакше кажучи, якщо $a_{k+1}$ — допустиме значення змінної $x_{k+1}$ , то алгоритм має перевірити допустимість наступних підстановок:

$x_{1}=a_{1}$	…	$x_{k-1}=a_{k-1}$	$x_{k}=a_{k}$	$x_{k+1}=a_{k+1}$
$x_{1}=a_{1}$	…	$x_{k-1}=a_{k-1}$		$x_{k+1}=a_{k+1}$
…
$x_{1}=a_{1}$				$x_{k+1}=a_{k+1}$

Найменший індекс, для якого знайдена несумісність, є безпечним стрибком для випадку, коли $x_{k+1}=a_{k+1}$ є єдиним допустимим значенням для $x_{k+1}$ . Оскільки зазвичай змінні можуть мати декілька допустимих значень, алгоритм виконує вищенаведені обрахунки для усіх, після чого із знайдений безпечних переходів обирається максимальний максимальний.

На практиці алгоритм може перевіряти вищенаведені умови одночасно із перевіркою підстановки $x_{k+1}=a_{k+1}$ .

Зворотний перехід на внутрішніх вузлах

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

Внутрішній вузол представляє таке присвоювання значення, що не порушує уже існуючої відповідності обмеженням. Якщо не існує розв'язку, що розширює цю підстановку, попередній алгоритм завжди здійснює повернення на попередній крок, а не стрибок.

Для внутрішніх вузлів стрибок не може здійснюватись так само, як і для листків. Дійсно, якщо якісь присвоювання значень змінній $x_{k+1}$ потребують продовження пошуку у піддереві, отже, вони відповідають обмеженням, і не має сенсу шукати префікс, котрий ці обмеження порушує.

В таких випадках безперспективність присвоювання $x_{k+1}=a_{k+1}$ для поточної підстановки $x_{1},\ldots ,x_{k}$ доводить рекурсивний пошук. Алгоритм «знає», що для даної підстановки не існує розв'язку, тому що він повертається у цю точку замість того, щоб знайти розв'язок і зупинитись.

Ці повернення зумовлені «глухими кутами», точками, в яких алгоритм довів несумісність підстановки із обмеженнями. Для того, щоб зробити стрибок, алгоритм має «зрозуміти», що рішення не вдається знайти саме через «глухі кути». Безпечними переходами будуть індекси префіксів, котрі перетворюють ці глухі кути у часткові підстановки, що не відповідають умовам.


В цьому прикладі алгоритм повернувся до змінної $x_{k+1}$ після того, як перевірив усі можливі значення і виявив, що усі вони недопустимі.	Друга вершина залишається недопустимою навіть коли з її часткової підстановки видалити змінні $x_{k+1}$ та $x_{k}$ (зверніть увагу на те, що значення змінної зберігається у її нащадках)	Інші недопустимі підстановки залишаються такими навіть без $x_{k-2}$ , $x_{k-1}$ і $x_{k}$	Алгоритм може здійснити стрибок до $x_{k-2}$ , так як це найменша змінна, що входить у всі недопустимі рішення. Для неї буде спробуване нове значення.

Іншими словами, після перевірки усіх значень $x_{k+1}$ алгоритм може перейти до змінної $x_{i}$ за тієї умови, що поточна істинна підстановка $x_{1},\ldots ,x_{i}$ несумісна із усіма істинними підстановками $x_{k+1},x_{k+2},...$ у листках візлів, що є нащадками $x_{k+1}$ .

Спрощення

У процесі пошуку переходу для змінної $x_{k+1}$ чи її предків змінні у кольоровій області можуть бути проігноровані.

Через потенційно велику кількість вузлів у піддереві змінної $x_{k+1}$ під час обробки цього піддерева збирається інфрмація, необхідна для безпечного стрибка із цієї змінної. Пошук безпечного стрибка може бути спрощений завдяки двом речам. Перше: хоча алгоритм і шукає безпечний стрибок, він не користується найвищим з можливих.

Друге можливе спрощення полягає у тому, що вузли піддерева змінної $x_{l}$ , що були пропущені стрибком, можуть бути проігноровані при пошуку стрибка для змінної $x_{l}$ . Точніше кажучи, вершини від $x_{m}$ до $x_{l}$ , що були пропущені стрибком, ніяк не пов'язані із піддеревом змінної $x_{m}$ і з іншими її піддеревами.

Дійсно, якщо алгоритм пішов від вершини $x_{l}$ до $x_{m}$ якимсь шляхом, але потім перестрибнув назад, він міг би просто перейти від $x_{l}$ до $x_{m}$ напряму. Таким чином, стрибок вказує на те, що вершини між $x_{l}$ та $x_{m}$ не мають відношення до піддерева вершини $x_{m}$ . Інакше кажучи, стрибок показує, що відвідування цієї частини дерева пошуку було помилкою. Завдяки цьому при пошуку стрибка із вершини $x_{l}$ або якогось з її предків ця частина дерева може бути проігнорована.

Змінні, значень яких достатньо для доведення несумісності у піддереві вершини, накопичуються у вершині і відправляються (після видалення змінної, що відповідає вершині) у вище по дереву на зворотному ході.

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

Зворотний перехід на графах

Суть зворотного переходу на графах полягає у тому, що безпечний стрибок може бути знайдений перевіркою того, які із змінних $x_{1},\ldots ,x_{k}$ пов'язані із змінними $x_{k+1},x_{k+2},...$ , що представлені листовими вузлами. Кожна змінна $x_{i}$ ( $i>k$ ), що представлена листком і пов'язана із змінною $x_{i}$ , може бути використана для пошуку безпечних стрибків. Зокрема, коли всі значення змінної $x_{k+1}$ вже перебрані, ця множина містить індекси змінних, для яких не має змісту пробувати піддерево змінної $x_{k+1}$ . В результаті алгоритм може безпечно перестрибнути до найвищого індексу з цієї множини.

Той факт, що вершини, пропущені стрибком, можуть бути проігноровані, використовується наступним алгоритмом. Коли ми повертаємось із листового вузла, предку цього вузла (у випадку стрибка — вузлу, у який стрибаємо) відправляється множина змінних, що пов'язані із цим вузлом. Кожна внутрішня вершина підтримує таку саму множину. Кожного разу, коли вершина отримує множину від котрогось із своїх нащадків, отримана множина додається до вже існуючої у вузлі. Коли ми повертаємось чи стрибаємо із вузла, змінна вузла видаляється із множини, після чого множина відправляється у вершину, в котру здійснюється стрибок/перехід. Алгоритм працює завдяки тому, що у кожній вершині підтримується список змінних, котрого достатньо, щоб довести відсутність розв'язку у піддереві даного вузла. Так як множини відправляються лише коли ми покидаємо вузол, множини із вузлів, котрі ми перестрибуємо, просто ігноруються.

Зворотний перехід, що базується на конфліктах (або зворотний перехід, що управляється конфліктами)

conflict-based backjumping conflict-directed backjumping

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

Хоча порушена умова у кожному листку не впливає на безпеку стрибка, вибір умови із найбільшим індексом підвищує «висоту» стрибка. Через це алгоритм із зворотним переходом, що управляється конфліктами, впорядковує умови таким чином, що обмеження для змінних із меншими індексами мають перевагу перед обмеженнями зі змінними із більшими індексами.

Формально кажучи, обмеження $C$ отримує перевагу перед обмеженням $D$ в тому випадку, коли найбільший індекс змінної у $C$ , але не в $D$ менший за найвищий індекс змінної у $D$ , але не в $C$ . Іншими словами, після виключення спільних змінних перевага надається обмеженню із найменшими індексами.

У листовому вузлі алгоритм надає перевагу індексу $i$ такому, що $x_{1},\ldots ,x_{i}$ вступає у протиріччя із останньою змінною, що була обчислена у вузлі. Серед обмежень, що були порушені при цьому обчисленні, алгоритм обирає найвигіднішу (критерії див. вище), після чого вибирає усі індекси, що менші за $k+1$ . Таким чином, коли алгоритм приходить до змінної $x_{k+1}$ , найменший знайдений індекс є безпечним стрибком.

На практиці цей алгоритм спрощується завдяки збору усіх індексів у єдину множину замість створення множини для кожного значення $k$ . Зокрема алгоритм збирає у кожній вершині усі множини, що приходять від нащадків (як і раніше, лише від тих, що не були пропущені під час стрибку). При поверненні із вузла із множини видаляється змінна, що відповідає вузлу, після чого множина відправляється у точку стрибку/переходу.

Алгоритм із зворотним переходом, що управляється конфліктами, був запропонований для задачі виконання обмежень Патріком Просером у 1993-у році.