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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Спрощення

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

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

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

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

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

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

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

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

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

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

conflict-based backjumping conflict-directed backjumping

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

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

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

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

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

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