Съдържание:
Определение - Какво означава Backtracking?
Обратното проследяване е алгоритъм за заснемане на някои или всички решения на дадени изчислителни проблеми, особено за проблеми с удовлетворяването на ограниченията. Алгоритъмът може да се използва само за проблеми, които могат да приемат концепцията за „частично решение на кандидата“ и позволява бърз тест, за да се види дали кандидатът може да бъде цялостно решение. Обратното проследяване се счита за важна техника за решаване на проблеми и задачки за удовлетвореност. Освен това се счита за чудесна техника за разбор и също така е в основата на много езици за логическо програмиране.
Техопедия обяснява Backtracking
Обратното проследяване помага за решаването на цялостен проблем чрез намиране на решение на първия подпроблем и след това рекурсивен опит за решаване на други подпроблеми въз основа на решението на първия брой. Ако текущият проблем не може да бъде разрешен, стъпката се връща назад и следващото възможно решение се прилага към предишни стъпки и след това продължава по-нататък. Всъщност едно от ключовите неща при отстъпването е рекурсия. Той се разглежда и като метод за изчерпателно търсене с помощта на разделяне и завладяване. Алгоритъмът за обратно приключване приключва, когато няма повече решения на първия подпроблем.
Обратното проследяване е алгоритъм, който може да помогне за постигането на недетерминизъм. Нужно е първоначално търсене на дадено пространство за издаване. Използва се предимно в езици за логическо програмиране като Prolog. Навсякъде, където може да се приложи отстъпването, той е по-бърз от грубата сила, тъй като елиминира голям брой кандидати с един тест.
