В този урок ще научите какво е алгоритъм за проследяване. Също така ще намерите пример за подход за проследяване.
Алгоритъмът за проследяване е алгоритъм за решаване на проблеми, който използва подход на груба сила за намиране на желания изход.
Подходът на грубата сила изпробва всички възможни решения и избира желаните / най-добрите решения.
Терминът backtracking предполага, че ако текущото решение не е подходящо, тогава се върнете и опитайте други решения. По този начин в този подход се използва рекурсия.
Този подход се използва за решаване на проблеми, които имат множество решения. Ако искате оптимално решение, трябва да изберете динамично програмиране.
Държавно космическо дърво
Дървото на пространственото състояние е дърво, представящо всички възможни състояния (решение или неразрешение) на проблема от корена като начално състояние до листа като крайно състояние.
Държавно космическо дърво
Алгоритъм за връщане назад
Backtrack (x), ако x не е решение, върнете false, ако x е ново решение
Примерен подход за обратно проследяване
Проблем: Искате да намерите всички възможни начини да подредите 2 момчета и 1 момиче на 3 пейки. Ограничение: Момичето не трябва да е на средната пейка.
Решение: Има общо 3! = 6 възможности. Ще изпробваме всички възможности и ще получим възможните решения. Рекурсивно изпробваме всички възможности.
Всички възможности са:
Всички възможности
Следното дърво на пространството на състоянията показва възможните решения.
Държавно дърво с всички решения
Приложения за алгоритъм за връщане назад
- За да намерите всички хамилтонови пътеки в графика.
- За решаване на проблема с N Queen.
- Проблем с решаване на лабиринт.
- Проблемът с турнето на рицаря.
