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

Коли алгоритм пошуку з поверненням перебрав усі можливі значення змінної, він повертається до попередньої змінної і або надає їй наступного значення, або повертається ще вище. Інакше кажучи, якщо ${\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}}$ або якогось з її предків ця частина дерева може бути проігнорована.

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

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