Бектрекинг

Бектрекинг (на английски: backtracking, в превод „търсене с връщане“) е общо название на клас от алгоритми, които намират всички или някои решения на изчислителни задачи, по-специално задачи за удовлетворяване на ограничения (constraint satisfaction problems). При този вид алгоритми решението се образува стъпка по стъпка, като за всяка стъпка се проверява дали удовлетворява поставените ограничения. При нарушаване на някое ограничение се отменя последната стъпка и се търси друга възможност. При изчерпване на възможностите се отменя предпоследната стъпка и т.н. до получаване на решение или до изчерпване на всички възможности.

Класически пример за използването на бектрекинг е задачата за осемте царици, която търси всички възможни варианти осем царици да бъдат разположени на стандартна шахматна дъска така, че никоя царица да не атакува друга. В стандартния бектрекинг подход, частичното кандидат-решение представлява разположение на $k$ царици в първите $k$ реда от дъската, така че никои две царици да не са споделят общ ред или стълб на дъската. Кандидат-решения, които съдържат взаимно атакуващи се царици, биват изоставяни от алгоритъма.

Бектрекингът може да се прилага само към задачи, които поддържат концепцията за „частично кандидат-решение“ и правят сравнително бърза проверка дали частичното кандидат-решение може да бъде завършено в пълно, валидно решение. Бектрекингът обаче е неприложим за търсене на дадена стойност в ненаредена таблица. Когато е приложим, бектрекингът често е много по-бърз от подхода на пълното изчерпване (brute force enumeration) на всички пълни кандидат-решения, тъй като позволява с една проверка да бъдат елиминирани голям брой безперспективни кандидат-решения (при изобразяването на пространството от решенията като дърво, това означава, че с една проверка може голям клон от дървото да се отстрани като безперспективна посока на търсене).

Бектрекингът е важен подход за решаване на задачи за удовлетворяване на ограниченията, като например задачи за решаване на кръстословици, криптоаритметика, судоку и други интелектуални игри. Често това е най-удобната техника за парсиране, за решаване на задачата за раницата и други задачи за комбинаторна оптимизация. Той е в основата и на т.нар. езици за логическо програмиране като Icon, Planner и Prolog.

Бектрекингът зависи от потребителски зададени процедури в „черна кутия“, които дефинират задачата за решаване, характера на кандидат-решенията и механизмът, по който частичните решения се превръщат в пълни. Следователно, това е по-скоро метаевристичен алгоритъм, отколкото такъв със специфицирани правила, въпреки че за разлика от много метаевристики, гарантирано намира всички решения на краен проблем за ограничено време.

Терминът „бектрекинг“ е въведен от американския математик Дерик Хенри Лемър през 1950-те. Езикът за обработка на низове SNOBOL от 1962 година вероятно е първият, който предлага вградена бектрекинг функционалност.

Описание на метода

Бектрекинг алгоритъмът номерира списък от частични кандидат-решения, които по принцип могат да бъдат завършени по различни начини, за да дадат всички възможни решения на дадена задача. Завършването на частичното решение се извършва постъпково (инкрементално) с поредица от стъпки по разширяване на решението.

Концептуално, частичните кандидат-решения се представят като възли от дървовидна структура от данни, т.е. пространството на решенията се изразява като дърво. Всеки възел (без кореновия) има само един родителски възел. Всяко частично кандидат-решение е родителски възел за кандидат-решенията, които се различават от него само с по една стъпка на разширяване, а листата на дървото са частични кандидат-решения, които няма накъде повече да бъдат разширявани.

Бектрекинг алгоритъмът обхожда рекурсивно дървото на търсене от корена надолу към листата в дълбочина (depth-first). На всеки възел $c$, алгоритъмът проверява дали c може да бъде завършено до валидно решение. Ако не може, цялото поддърво с корен в $c$ се отстранява. В противен случай, алгоритъмът (1) проверява дали самият кандидат $c$ е валидно решение, и ако да, съобщава за това на потребителя и (2) рекурсивно номерира всички поддървета на $c$. Тези две проверки ке дефинират по зададени от потребителя процедури.

Следователно, фактическата част от дървото на търсене, която бива обходена от алгоритъма, е само част от потенциалното цяло дърво. Съвкупната „цена“ на алгоритъма е броят фактически обходени възли, умножен по цената за достъпване и обработване на всеки възел. Тази цена следва да се отчита при избиране на структурата на потенциалното дърво на търсене и при определянето на условията на проверката за отстраняване на безперспективни части от дървото.

Източници

Тази страница частично или изцяло представлява превод на страницата Backtracking в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​