Бэктрекин без рекурсии на Python

Опубликовано 03 November 2016 в Python

В Питоне нет оптимизации хвостовой рекурсии и достаточно жесткий лимит на рекурсивные вызовы. Это может вызвать затруднения при решении задач с помощью алгоритма бэктрекинга: лимита хватает на поиск решения судоку, но он может оказаться слишком низким, если количество решений для проверки в задаче довольно высоко.

Тем не менее, реализация бэктрекинга с рекурсией на Питоне элегантна, легко читаема и понятна. Отказываться от нее имеет смысл только для "тяжелых" задач.

def backtrack(self, solution):
    if solution in self.seen_solutions:
        return
    if self.reject(solution):
        return
    if self.accept(solution):
        self.output(solution)
    for child_solution in self.child_solutions(solution):
        self.backtrack(child_solution)

Когда сложность задачи достигнет лимита рекурсивных вызовов, можно переключиться на шаблон без рекурсии. Он уже не так элегантен как рекуррентное решение, но он не так страшен как мог бы быть. К тому же, он использует те же вспомогательные функции, что и его собрат с рекурсией.

def backtrack(self, solution):
    solution_stack = [self.child_solutions(solution)]
    while True:
        current_generator = solution_stack[-1]
        solution = next(current_generator, None)
        while solution:
            if self.reject(solution):
                solution = next(current_generator, None)
                continue
            if self.accept(solution):
                self.output(solution)
            if not self.solution_is_complete(solution):
                solution_stack.append(self.child_solutions(solution))
                current_generator = solution_stack[-1]
            solution = next(current_generator, None)
        solution_stack = solution_stack[:-1]
        if not solution_stack:
            return

---
Возник вопрос? Мне всегда можно написать в Twitter: avkorablev

Наслаждайся