"Информатика", Семёнов А.Л., Рудченко Т.А.
Дерево перебора — схема, которая помогает организованно находить все возможные результаты выбора. Каждый шаг выбора изображают отдельным уровнем, а возможные решения — ветвями. Полный путь от начала до конца дерева задаёт один готовый вариант. Для подмножеств на каждом шаге решают, включать очередной элемент или нет, поэтому для n элементов получается 2ⁿ подмножеств. Такой способ помогает ничего не пропустить и не повторить.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Дерево перебора вариантов — схема, в которой каждый путь от корня до конечной вершины задаёт один полный вариант. Представь развилки на маршруте: каждый поворот соответствует сделанному выбору. Такая схема нужна, чтобы увидеть все возможные результаты и не смешивать их.
Корень дерева — начальная вершина, от которой начинается построение вариантов. Это исходная точка, в которой ещё не принято ни одного решения. Корень помогает понять, откуда начинать чтение схемы и в каком порядке идти по ней.
Ветвь дерева — переход от одного выбора к следующему; на ветвях указывают возможные решения. Например, ветви могут быть подписаны названиями напитков или словами «взять» и «не брать». По этим подписям можно восстановить, какие решения привели к результату.
Дерево перебора подмножеств — дерево, в котором для каждого элемента рассматривают два решения: включить его в подмножество или не включать. Подмножество — это набор, составленный из некоторых элементов исходного множества. Такое дерево удобно, когда нужно проверить все возможные составы набора, включая пустой.
Задачу о выборе удобно сначала представить последовательностью решений. Например, если выбирают напиток, а затем булочку, сначала определяют возможные напитки, а после каждого из них — возможные булочки. Каждый шаг становится отдельным уровнем дерева, потому что так видно, какое решение принимается следующим и от чего оно зависит.
Корень соответствует началу выбора, когда результат ещё не собран. Промежуточная вершина показывает, что часть решений уже принята, но остаются следующие шаги. Конечная вершина появляется только после последнего решения: если остановиться раньше, некоторые признаки результата останутся неизвестными, и готовый вариант определить нельзя.
Чтобы восстановить вариант, нужно пройти от корня к конечной вершине и прочитать подписи всех пройденных ветвей по порядку. Каждая конечная вершина отвечает одному пути, поэтому для полного списка проходят дерево последовательно: сначала одну ветвь до конца, затем следующую. Такой порядок помогает не пропустить сочетания и не записать один путь дважды.
Дерево подмножеств строят по тому же принципу, но на каждом уровне рассматривают очередной элемент исходного набора. От каждой вершины проводят две ветви: элемент включают или не включают. К следующему уровню переходят после обоих возможных решений, поскольку иначе часть составов не будет рассмотрена.
Для каждого из n элементов есть два независимых решения, поэтому число путей можно найти умножением двух на себя n раз: 2ⁿ. Например, для трёх элементов получится 2 × 2 × 2 = 8 путей и, значит, 8 подмножеств. Это правило работает, если каждый элемент рассматривается отдельно и дополнительных ограничений на выбор нет.
| Что сравниваем | Дерево перебора вариантов | Дерево перебора подмножеств |
|---|---|---|
| Что обозначают уровни | Очередные шаги выбора | Очередные элементы набора |
| Что означают ветви | Возможные решения на шаге | Включить элемент или не включать |
| Что задаёт путь от корня до конца | Один полный вариант | Одно подмножество |
| Когда вариант считается готовым | Когда сделаны все предусмотренные выборы | Когда рассмотрены все элементы |
| Число конечных вариантов | Зависит от числа выборов и их исходов | Для n элементов равно 2ⁿ |
Чтобы выбрать подходящий способ, сначала посмотри, что именно обозначают шаги: разные признаки результата или элементы одного набора. Затем проследи, что записано на ветвях, и проверь, дошёл ли путь до конца. Таблица помогает отличить общий перебор вариантов от особого случая с подмножествами.
Задача 1. Для завтрака можно выбрать один из двух напитков и одну из двух булочек. Построй дерево всех возможных завтраков и укажи их число.
Ответ: 4 завтрака. Мы рассмотрели каждый напиток с каждой булочкой, поэтому ни одно сочетание не потерялось.
Задача 2. Из трёх разных книг составляют набор, выбирая любые книги или не выбирая ни одной. Построй дерево перебора подмножеств и выпиши все наборы.
Ответ: 8 наборов. Чтобы проверить список, можно применить правило 2³ = 8 и убедиться, что выписано столько же результатов.
Задача 3. Для четырёх предметов построй дерево перебора подмножеств, определи число подмножеств и найди набор, в который входят только первый и третий предметы.
Ответ: всего 16 подмножеств; нужный набор — первый и третий предметы. Подписи пути показывают состав набора, а не просто порядок уровней.
Промежуточную вершину иногда принимают за готовый вариант, хотя после неё ещё предстоит сделать выбор. Так происходит, когда ученик видит уже знакомую часть результата и забывает о следующих шагах. Проверь себя: у готового пути должны быть приняты решения по каждому признаку или каждому элементу.
Если пропустить ветвь или пройти одну и ту же ветвь дважды, список получится неполным или с повторами. Обычно это случается, когда дерево читают не по порядку. Проверяй, что из каждой вершины пройдены все ветви, а каждый путь до конца записан ровно один раз.
Порядок уровней можно ошибочно принять за состав результата: например, решить, что элемент включён, потому что его уровень встретился первым. На деле уровень лишь показывает, какой элемент сейчас рассматривают. Состав подмножества определяют только решения «взять» или «не брать» на ветвях.
Иногда забывают набор, в который не входит ни один элемент, потому что он кажется пустым и потому будто бы не считается. Но ему соответствует полноценный путь, на котором каждый раз выбирают «не брать». Для проверки списка подмножеств найди этот путь и сравни общее число результатов с 2ⁿ.
Для работы с деревом нужно уметь последовательно выполнять выбор и читать схему из вершин и соединяющих их линий. Если пока трудно прослеживать маршрут, начни с простого дерева и называй каждую ветвь вслух. Такой навык помогает понимать, в каком порядке принимаются решения и что уже известно на каждом шаге.
Перебор вариантов пригодится в комбинаторных задачах, где требуется найти все сочетания, а также при составлении алгоритмов, проверяющих разные решения. Алгоритм может пройти по ветвям дерева и оценить каждый полный вариант по заданному условию. Поэтому аккуратное построение дерева помогает не только записать ответы, но и организовать проверку.
Что в дереве перебора называют корнем?
Корень — начальная вершина дерева, от которой начинают строить варианты. Он обозначает состояние до того, как сделан первый выбор.
Как понять, что путь по дереву задаёт готовый вариант?
Путь готов, если он дошёл от корня до конечной вершины и на нём приняты решения по всем шагам выбора. Прочитай указания на ветвях этого пути: вместе они и составят вариант.
Почему у каждого элемента в дереве подмножеств две ветви?
Для очередного элемента есть ровно два решения: включить его в подмножество или не включать. Каждая ветвь фиксирует одно из этих решений.
Как определить, сколько подмножеств можно составить из нескольких элементов?
Если элементов n и каждый можно независимо включить или не включить, число подмножеств равно 2ⁿ. Например, для трёх элементов это 2³ = 8.
Нужно ли считать подмножеством набор, в который не входит ни один элемент?
Да, пустой набор тоже считается подмножеством. В дереве ему соответствует путь, на котором для каждого элемента выбрано «не брать».
Дерево перебора вариантов. Дерево перебора подмножеств
