Схема за изчислително обратно проследяване
Нека опишем някакъв набор Â комбинаторни проблеми, за които алгоритъмът за обратно проследяване е очевидно приложим.
Нека бъде М0, Медин, . Мн-1 - n крайни линейно подредени множества и G - набор от ограничения (условия), които присвояват вектори на формата v = (v0, vедин, . vk) Т (vj Î Mj; j = 0, 1, . к; к £ н-1), булево G(v) Î вярно, Невярно>. Вектори v = (v0, vедин, . vk) T за което G(v) = вярно, да се обадим частични решения. Освен това нека има конкретно правило , според която могат да бъдат декларирани някои от частичните решения цялостни решения. Тогава могат да се формулират следните задачи за търсене:
Намерете всички цялостни решения или установете липсата им.
Намерете поне едно цялостно решение или установете липсата му.
Най-често подобни задачи се формулират и решават, когато се зададе следващото правило върху частични решения [13, с. 321-322; 46, c.66-75]:
Общият метод за решаване на горните проблеми е последователно компонентно увеличение на вектора v отляво надясно, започвайки от v0, и последващи тестове с неговите ограничения G и правилото .
По-долу, на някои подобни на Паскал псевдокодове, са дадени три схеми за решаване на проблеми чрез метода на грубата сила с обратно проследяване: нерекурсивна версия за намиране на всички решения (схема 1), рекурсивна версия за намиране на всички решения (схема 2) рекурсивна версия за намиране на едно решение (схема 3).
Съгласно схема 1 се намират всички решения на проблема, ако има такива, и работата приключва, когато j = 0. Неговата рекурсивна версия, показана на схема 2, е много по-проста и по-очевидна.
Схема 1. Нерекурсивна версия на схемата за обратно проследяване за намиране на всички решения
Генерирането на всички решения съгласно схема 2, ако има такива, се организира чрез обаждане връщане назад(0) . Намирането на едно решение съгласно схема 3, ако има такова, се извършва чрез извикване: връщане назад (0, „няма намерено решение“) . Имайте предвид, че в диаграми 2 и 3 връщането не се появява изрично, като естествена част от изпълнението на рекурсивния механизъм.