Пошук з вертанням (англ. backtracking), також пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який поступово будує кандидатів на розв'язок, і відкидає кожного неповного кандидата c («вертається») як тільки визначає, що c не може бути доповненим до вірного розв'язку.[1][2][3]
Класичний приклад використання пошуку з вертанням — це задача про вісім ферзів, в який потрібно знайти розташування восьми ферзів на стандартній шахівниці таким чином, щоб жоден ферзь не атакував іншого. В звичайному підході пошуку з вертанням, неповні кандидати це розташування k ферзів в перших k рядах дошки, всі в різних рядах і стовпцях. Будь-який неповний розв'язок, що містить два ферзі, які атакують один одного має бути відкинутий, бо він не може бути доведеним до повного правильного розв'язку.
Пошук з вертанням може бути застосований тільки до задач, що дозволяють поняття «неповних кандидатів на розв'язок» і порівняно швидку перевірку на можливість доповнення кандидата до вірного розв'язку. Це корисно, наприклад, для знаходження значення у невпорядкованій таблиці. За можливості застосування, пошук з вертанням часто значно швидший ніж повний перебір всіх можливих кандидатів, через виключення великої кількості кандидатів однією перевіркою.
Пошук з вертанням — це важливе знаряддя для розв'язання проблеми відповідності обмеженням, таких як кросворди, судоку та багато інших головоломок. Часто це найзручніший (якщо не найефективніший) підхід для розбору, для задачі пакування рюкзака та інших задач комбінаторної оптимізації. Це також базис для так званих мов логічного програмування таких як Icon, Planner і Prolog. Пошук з вертанням також використовується в рушії змін (diff) для програмного забезпечення MediaWiki.
Пошук з вертанням покладається на подані користувачем процедури, які визначають задачу для розв'язання, природу неповних кандидатів і як вони доповнюються до повних кандидатів. Тому це швидше метаевристика ніж конкретний алгоритм — хоча, на відміну від інших метаевристик, вона гарантовано знаходить всі розв'язки скінченної проблеми за обмежений час.
Англомовний термін «backtrack» був винайдений американським математиком D. H. Lehmer в 1950-х.[4] Піонерська мова опрацювання рядків SNOBOL (1962) можливо першою забезпечила вбудовані засоби загального пошуку з вертанням.
Алгоритм пошуку з вертанням перераховує множину неповних кандидатів що, в принципі, можуть бути доповнені кількома шляхами для отримання всіх можливих розв'язків даної задачі. Доповнення будується покроково, послідовністю кроків розширення кандидата.
Концептуально, неповні кандидати є вузлами деревоподібної структури, потенційне дерево пошуку. Кожний неповний кандидат є батьком кандидатів відмінних від нього на один крок розширення; листям дерева є кандидати які не можуть бути розширені далі.
Алгоритм пошуку з вертанням обходить це дерево пошуку рекурсивно, від кореня донизу, пошуком в глибину. В кожному вузлі c, алгоритм перевіряє чи може c бути доповнене до вірного розв'язку. Якщо ні, ціле піддерево з коренем в c пропускається (обрізається). Інакше, алгоритм (1) перевіряє чи є c вірним розв'язком, і якщо так повідомляє про це користувача; і (2) рекурсивно обходить усі піддерева c. Обидва тести і дочірні вузли кожного вузла визначаються за допомогою поданих користувачем процедур.
Внаслідок цього, актуальне дерево пошуку яке обходить алгоритм становить лише частину потенційного дерева. Загальна ціна алгоритму це кількість вузлів актуального дерева помножена на вартість отримання і обробки кожного вузла. Цей факт має бути врахованим коли обирається потенційне дерево і реалізується тест на обрізання.
Для застосування пошуку з вертанням для певного класу задач, потрібно мати дані P для конкреної задачі, що має бути розв'язана, і шість підпрограм, корінь, відмова, прийняття, перший, наступний, і вихід. Ці підпрограми мають отримувати дані P як параметр і мають бути такими:
- корінь(«P»): повертає неповний кандидат в корені дерева пошуку.
- відмова(P,c): повертає істину тільки якщо неповний кандидат c невартий завершення.
- прийняття(P,c): повертає істину якщо c є розв'язком P, і хибу якщо ні.
- перший(P,c): продукує перше розширення кандидата c.
- наступний(P,s): продукує інше наступне розширення кандидата, після розширення s.
- вихід(P,c): прийняти розв'язок c з P, як підходяще для застосування.
Пошук з вертанням зводиться до виклику bt(root(P)), де bt наступна рекурсивна підпрограма:
procedure bt(c)
якщо відмова(P,c) тоді вийти
якщо прийняття(P,c) тоді вихід(P,c)
s ← перший(P,c)
доки s ≠ Λ робити
bt(s)
s ← наступний(P,s)
- ↑ Дональд Кнут (1968). Мистецтво програмування. Addison-Wesley.
- ↑ Thomas H. Cormen; Charles E. Leiserson, Ronald R. Rivest, Cliff Stein (1990). Introduction to Algorithms. McGraw-Hill.
- ↑ Gurari, Eitan (1999). CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms. Архів Backtracking algorithms оригіналу за 17 березня 2007. Процитовано 19 січня 2011.
- ↑ Rossi, Francesca; Beek, Peter Van; Walsh, Toby (August 2006). Constraint Satisfaction: An Emerging Paradigm. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Амстердам: Elsevier. с. 14. ISBN 978-0-444-52726-4. Процитовано 30 грудня 2008.
Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.
