Дерево возможных вариантов
Дерево возможных вариантов — это схема, показывающая все последовательности выборов, которые алгоритм перебирает при поиске решения. Каждый путь от корня до конечной вершины задаёт один полный вариант.
Построение начинают с корня — исходного состояния задачи. На каждом уровне дерева выбирают один элемент, значение или действие. Если выборов несколько, вершина получает несколько потомков. Построение дерева вариантов помогает не пропустить ни один случай. Порядок ветвей можно выбирать произвольно, но при одинаковом порядке удобнее сравнивать результаты перебора вариантов.
Если на \(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 независимых варианта. Сколько конечных путей в дереве?
Главное
- Дерево возможных вариантов показывает все последовательности выбора.
- Путь от корня до листа — один полный вариант решения.
- Число вариантов при независимых выборах находят умножением числа возможностей на каждом этапе.