Алгоритм «пошук з поверненням» (backtracking)

Abstract

Алгоритм «пошук із поверненням» (backtracking) є одним із класичних методів вирішення завдань комбінаторного пошуку. Розв'язання задачі методом пошуку із поверненням зводиться до послідовного розширення часткового рішення. Якщо на черговому кроці таке розширення провести не вдається, то повертаються до більш короткого часткового рішення та продовжують пошук далі. Цей алгоритм дозволяє знайти всі рішення поставленого завдання, якщо вони існують. Для прискорення методу намагаються обчислення організувати в такий спосіб, щоб якомога раніше виявляти свідомо невідповідні варіанти. Найчастіше це дозволяє значно зменшити час перебування рішення.