3. Дерево решений
 

Программу, содержащую разветвления, можно представить в виде двоичного дерева, называемого деревом решений. Каждый внутренний узел дерева представляет одну из точек разветвления в программе и соответствует условию (правилу), по которому осуществляется движение по правой или левой ветви. Возможные результаты (решения задачи) представляются листьями.

Если для конкретных исходных данных задача имеет одно единственное решение, то оно находится движением по соответствующим ветвям дерева, пока не будет достигнут лист с искомым решением. Длина пути от вершины дерева до отдельных листьев дерева, зависящая от конкретных исходных данных, может быть различна. В наихудшем случае, соответствующем самому длинному пути, временная сложность решения задачи равна высоте дерева решений. Иногда высота дерева определяется как функция от размера задачи. Рассмотрим дерево решений для задачи упорядочения трех чисел a, b и с в порядке возрастания их значений. Условие движения по ветвям дерева определяется сравнением пары чисел. Пусть все числа имеют разные значения. Дерево решений можно представить, как показано на рис.

Рис. Дерево решений упорядочения трех чисел

Часто возникают задачи, когда необходимо найти все возможные решения или для нахождения подходящего решения приходится перебирать все или большинство возможных решений. В этом случае требуется посетить все или некоторое количество листьев дерева по некоторому порядку, например левым смешанным обходом дерева (Inorder).
Пример.

Пусть имеется кодовый замок с n двоичными переключателями («вкл»-«выкл»). Число возможных комбинаций ключа равно 2ⁿ. Попытаемся открыть замок наугад, не зная кода. Построим дерево решений, оно будет иметь высоту n и 2ⁿ листьев. Длина пути до всех листьев одна и та же и равна n. Решение задачи сводится к полному перебору всех n-мерных векторов с нуль -единичными элементами. Для открытия замка придется сделать максимум 2ⁿ, в среднем 2ⁿ/2 попытки. Временная сложность нахождения одного решения О(n), а всех 2ⁿ решений не превышает О(n*2ⁿ), т.е. является экспоненциальной. Дерево решений для этой задачи будет иметь следующий вид:

Рис. Дерево решений поиска ключа

Дерево решений строится только для удобства разработки и анализа алгоритма, а в программе, естественно, никакого дерева нет.

В чем различие двух рассмотренных деревьев решений? В задаче сортировки направление движения по ветвям дерева полностью и однозначно определяется исходными данными (заданными значениями а, b, с), поэтому решение находится не больше чем за три шага, т.е. при любых исходных данных за два или три шага мы достигаем того из листьев, который определяет искомое решение.

В задаче с кодовым замком исходные данные не задаются, просто ставится задача нахождения среди 2ⁿ возможных решений той комбинации кода, которая является ключом, открывающим замок. Таким образом, движение по ветвям дерева определяется не значениями исходных данных, а некоторыми общими правилами. В приведенном варианте дерева решений движение по левой ветви добавляет в код единичный бит, а движение по правой ветви — нулевой бит. Следовательно, любые 4 ветви, ведущие от корня к одному из листьев, дают 4-мерный вектор-код одного из возможных решений.