Дерево возможных вариантов
Дерево возможных вариантов — это схема, которая показывает все последовательности выборов или исходов в виде ветвей, выходящих из одной или нескольких вершин. С его помощью удобно не пропустить варианты и посчитать их количество.
Дерево строят слева направо или сверху вниз. Сначала записывают исходную ситуацию, затем из неё проводят ветви для всех возможных первых выборов. От каждой полученной вершины проводят ветви для следующих выборов. Конечные вершины соответствуют полным вариантам. Такой приём является частью метода перебора вариантов.
Как считать варианты по дереву
Чтобы получить число всех вариантов, можно пересчитать конечные вершины. Если на каждом из \(k\) последовательных шагов есть соответственно \(n_1,n_2,\ldots,n_k\) возможностей и каждый выбор можно сочетать с любым следующим выбором, то число путей равно произведению:
У Маши есть 2 футболки и 3 юбки. На первом уровне дерева — 2 ветви для футболок, от каждой из них — по 3 ветви для юбок. Поэтому конечных вариантов одежды \(2\cdot3=6\): каждая футболка сочетается с каждой юбкой.
Дерево возможных вариантов не является таблицей вариантов, хотя обе схемы помогают перечислять результаты. В дереве важно видеть порядок шагов и связи между ними. Если выборы зависят друг от друга, число ветвей на разных уровнях может быть различным.
У замка есть 3 цифры, каждая выбирается из набора \(\{1,2,3,4\}\), повторения разрешены. Сколько конечных вершин будет в дереве вариантов?
Если некоторые ветви приводят к одинаковому результату, сначала решите, считаются ли они разными исходами. Для случайного опыта полный набор конечных исходов образует пространство элементарных исходов. После подсчёта вариантов полезно проверить результат подсчётом двумя способами.
Главное
- Дерево вариантов показывает последовательность выборов ветвями.
- Каждый путь от начала до конца — один полный вариант.
- При независимых последовательных выборах число вариантов находят умножением числа возможностей на шагах.