Дерево возможных нұсқа
Дерево возможных нұсқа — это схема, показывающая все последовательности выборов, которые алгоритм перебирает при поиске решения. Каждый путь от корня до конечной вершины задаёт один полный вариант.
Построение начинают с корня — исходного состояния задачи. На каждом уровне дерева выбирают один элемент, значение или действие. Если выборов несколько, вершина получает несколько потомков. Построение дерева нұсқа помогает не пропустить ни один случай. Порядок ветвей можно выбирать произвольно, но при одинаковом порядке удобнее сравнивать результаты перебора нұсқа.
Если на \(m\) этапах число нұсқа равно соответственно \(k_1, k_2, \ldots, k_m\), то всего получится \(N\) конечных путей. При одинаковом числе нұсқа \(k\) на каждом этапе формула упрощается: \(N = k^m\). Если некоторые варианты запрещены, фактическое число листьев будет меньше.
Нужно составить двузначное число из цифр \(1\), \(2\) и \(3\) без повторений. В корне выбираем цифру десятков: 3 варианта. Из каждой такой вершины выбираем цифру единиц: 2 варианта. Дерево содержит \(3 \cdot 2 = 6\) листьев: 12, 13, 21, 23, 31, 32. Каждый лист — отдельное Шешім.
Дерево нұсқа описывает пространство шешімдер, а дерево рекурсивных вызовов показывает, какие вызовы функции возникают во время работы программы. Иногда они похожи, но это разные схемы: один вызов может проверять несколько вариантов или сразу отсекать ветвь.
На практике дерево часто обходят с помощью бэктрекинга: алгоритм делает выбор, углубляется по ветви, а затем возвращается назад и пробует следующий вариант. Полный перебор посещает все допустимые листья, если отсечение ветвей перебора не разрешает пропустить заведомо неподходящую ветвь.
На трёх этапах подряд есть по 2 независимых нұсқа. Сколько конечных путей в дереве?
Главное
- Дерево возможных нұсқа показывает все последовательности выбора.
- Путь от корня до листа — один полный нұсқа шешімдер.
- Число нұсқа при независимых выборах находят умножением числа возможностей на каждом этапе.