Построение дерева вариантов
Дерево вариантов — это схема, показывающая все последовательности выборов в задаче. По дереву удобно находить число возможных результатов, отбрасывать неподходящие ветви и проверять решения заданий ЕГЭ-24 и ЕГЭ-27.
Что такое дерево вариантов
Дерево вариантов строят сверху вниз. В верхней точке находится начальное состояние задачи. Из неё выходят ветви — возможные действия или выборы на первом шаге. Из каждой получившейся точки проводят ветви следующих действий. Точки называют вершинами, а последовательности ветвей от начала до конца — путями или маршрутами.
Дерево вариантов — граф, в котором каждая ветвь соответствует одному выбору, а каждый путь от корня до конечной вершины — одному полному варианту решения. Корень — начальная вершина. Лист — конечная вершина, из которой дальше выборов нет. Глубина дерева — число шагов от корня до листа.
Перед построением дерева полезно определить, что означает один шаг: выбор символа, переход автомата, действие исполнителя или решение «да/нет». Если разные действия приводят к одинаковому состоянию, их всё равно учитывают как разные пути, когда требуется посчитать способы получения результата.
Как строить дерево решений
- Запишите начальное состояние в корне.
- Определите все разрешённые действия на текущем шаге.
- Проведите по одной ветви для каждого действия и подпишите её.
- Для каждой новой вершины снова найдите разрешённые действия.
- Остановите ветвь, если получен нужный результат, нарушено условие или достигнута заданная длина.
- Посчитайте подходящие листья или пути.
Если из вершины выходят \(a\) вариантов первого шага, а после каждого из них — по \(b\) вариантов второго шага, то число двухшаговых путей равно \(a\cdot b\). Если пути распадаются на непересекающиеся группы, число всех путей равно сумме количеств в группах.
Формула (1) применяется, когда на каждом уровне число выборов известно и выборы не зависят от предыдущих действий. Если число доступных действий меняется, нужно считать ветви по уровням или отдельно рассматривать разные случаи.
Подписывайте ветви короткими обозначениями: \(0\), \(1\), «Л», «П», «+», «−». Путь тогда можно прочитать как слово или последовательность команд. Это особенно полезно вместе с бэктрекингом, где после каждого шага проверяют текущее состояние и возвращаются к предыдущему выбору.
Подсчёт путей и отсечение ветвей
В задачах на исполнителей дерево часто строят не до одинаковой глубины. Одна ветвь может раньше прийти к цели, а другая — стать невозможной. Успешный путь засчитывают один раз, даже если одинаковый результат получен разными последовательностями команд: нужно внимательно понять, спрашивается ли число путей, число конечных чисел или число различных последовательностей.
Допустимый путь — последовательность действий, которая не нарушает условия задачи и заканчивается требуемым результатом. Ветвь, на которой условие уже нарушено, можно не продолжать: это [[pruning-rule:правило отсечения ветвей]].
Если действия образуют строки фиксированной длины, дерево можно строить уровнями. На уровне \(i\) находятся все состояния после \(i\) действий. Иногда удобнее не рисовать всю схему, а хранить состояния в таблице или перебирать их программой. Такой переход от одного состояния к следующему связан с задачами о [[finite-automaton-word:распознавании слова конечным автоматом]] и с [[automaton-transition-table:таблицей переходов автомата]].
Из корня выходят 3 ветви, а из каждой получившейся вершины — 2 ветви. Сколько путей длины два существует?
Разобранный пример: команды исполнителя
Исполнитель начинает с числа \(1\). За один шаг он может выполнить одну из команд: «прибавить 1» или «умножить на 2». Требуется определить, сколько различных последовательностей из трёх команд приводят к числу \(5\).
В каждом узле сначала выписываем оба действия, но продолжаем только те ветви, которые могут привести к \(5\). Так дерево показывает именно последовательности команд, а не только промежуточные числа.
Показать краткое решение Ответ
Полное дерево имеет \(2^3=8\) путей. Подстановка команд показывает, что число \(5\) получается двумя путями: \(1\xrightarrow{+1}2\xrightarrow{\times2}4\xrightarrow{+1}5\) и \(1\xrightarrow{\times2}2\xrightarrow{\times2}4\xrightarrow{+1}5\). Ответ: \(2\).
Обратите внимание: последовательности AAA и УAA приводят к одному промежуточному и конечному числу \(4\), но это разные пути. Если бы спрашивалось число различных конечных результатов, их считали бы иначе. При большом дереве можно использовать [[backtracking-solution:решение методом перебора с возвратом]], сохраняя текущую глубину, значение и выбранные команды.
Дерево для слов и комбинаций
При составлении слова длины \(k\) из алфавита дерево имеет \(k\) уровней. Если на каждом уровне разрешены все \(m\) символов и повторения допустимы, количество слов равно \(m^k\). Если символ нельзя использовать повторно, число вариантов уменьшается на каждом уровне: \(m(m-1)(m-2)\ldots\).
Условие может запрещать отдельные переходы: например, после цифры \(1\) нельзя ставить цифру \(0\). Тогда дерево строят с учётом последнего символа или другого необходимого состояния. Такой способ близок к [[backtracking-state:состоянию перебора]]: состояние должно содержать всю информацию, от которой зависят дальнейшие действия.
1. Забывают ветви. Сначала выпишите все разрешённые действия, только потом исключайте невозможные. 2. Смешивают пути и результаты. Разные пути могут приводить к одному числу. 3. Умножают там, где выборы зависят друг от друга. Если число ветвей меняется, используйте разбор по случаям. 4. Продолжают невозможную ветвь. После нарушения условия её нужно отсечь. 5. Считают промежуточные вершины вместо листьев. Ответом обычно являются полные пути, если это прямо не оговорено.
Как решать задания на экзамене
- Уточнить, что считается вариантом: путь, команда, слово или конечный результат.
- Определить начальное состояние и условие остановки.
- Нарисовать первые уровни дерева, чтобы увидеть закономерность.
- Отметить запрещённые переходы и отсечь невозможные ветви.
- Проверить ответ другим способом: формулой, таблицей или короткой программой.
Для задач, где требуется найти все варианты, полезно изучить [[combinatorial-enumeration:перебор комбинаций]] и [[permutation-generation:построение перестановок]]. Если действия нужно выполнять до достижения цели, дерево можно исследовать рекурсивно; при этом важно понимать [[recursion-stack:стек рекурсивных вызовов]].
Быстрая проверка
Главное
- Дерево вариантов показывает последовательность выборов: корень — начало, листья — завершённые варианты.
- Число независимых последовательных выборов находят умножением, а непересекающиеся случаи объединяют сложением.
- Разные пути могут иметь один результат, поэтому заранее определите, что именно нужно посчитать.
- Невозможные ветви отсекают сразу; это уменьшает дерево и предотвращает ошибки.
- Для сложных задач применяют перебор, бэктрекинг, таблицу состояний или программу.