Поиск на деревьях
Введение
Решение некоторых задач можно сформулировать как поиск определённого узла на дереве.
Например, в ханойских башнях с тремя дисками и стержнями
дерево пространства состояний имеет вид:
Начиная с корня дерева (узел с именем 000) необходимо найти узел с именем 111 (все диске на втором стержне). В этом документе мы рассмотрим неинформативные методы поиска, когда отсутствует информация о том, где расположен на дереве искомый узел. В результате приходится последовательно перебирать все узлы на дереве. Проще всего обходить дерево в глубину или ширину.
Поиск в глубину
В качестве примера перебора в глубину, напишем функцию, вычисляющую число узлов на дереве. Рекурсивная её версия имеет вид:
function numNodes1 (tr)
{
var num = 0;
if(tr.ar)
for(var i=0; i < tr.ar.length; i++) // рекурсивно для ветвей
num += numNodes1(tr.ar[i]); // складываем узлы на них
return 1+num; // сумма этого и потомков
}
Для дальнейших обобщений, перепишем эту функцию в
нерекурсивном виде. Для этого введём стек узлов open:
function numNodes2 (tr)
{
var open = [ tr ]; // стек узлов (сначала корень)
var num = 0; // число узлов в дереве
while( open.length ){ // пока стек не пустой
num++;
var n = open.pop(); // выталкиваем последний узел
if(n.ar)
for(var i=0; i < n.ar.length; i++) // и всех его потомков запихиваем в стек
open.push(n.ar[i]);
}
return num;
}
Если ставится задача поиска узла, удовлетворяющего некоторому критерию, то функция numNodes2 (дополненная проверкой выполнения этого критерия) называется поиском в глубину. Она наиболее эффективна для относительно не глубоких деревьев.
Поиск в ширину
Если вместо n = open.pop() поставить n = open.shift(), (т.е. помещать (push) узлы в конец очереди, а брать их с её начала), то получится функция numNodes3, реализующая поиск в ширину. Впрочем, массивы очень медленно вставляют элементы в начало, поэтому для поиска в ширину лучше использовать списки:
function numNodes3 (tr)
{
var open = new List(tr); // список ( см. list.js )
var num = 0; // число узлов в дереве
while( open.length ){ // пока список не пустой
num++;
var n = open.shift(); // берем первого в списке
if(n.ar)
for(var i=0; i < n.ar.length; i++) // и всех его потомков
open.push(n.ar[i]); // запихиваем в конец списка
}
return num;
}
Этот метод опускается по дереву "слоями".
При этом он вынужден хранить существенно больше узлов в очереди, чем при поиске в глубину.
Тем не менее, если дерево очень глубокое (а искомый узел находится на конечной глубине),
поиск в ширину (в отличии от поиска в глубину) этот узел гарантированно находит.
Поиск с итеративным углублением
Ещё одна возможность называется поиском с итеративным углублением. В этом методе дерево просматривается в глубину сначала до глубины 1. Затем поиск начинается заново и ведётся до глубины 2. Потом снова возвращаемся в корень и спускаемся до глубины 3 и т.д. (шаг увеличения глубины можно сделать большим, чем 1). Процесс заканчивается, когда исчерпаются все узлы или достигается некоторое предельное значение глубины. Ситуация аналагична дайверу, который, планируя поставить рекорд глубины погружения, при каждом очередном дайве погружается всё глубже.
Хотя в этом методе приходится повторно просматривать узлы, для глубоких леревьев он оказывается эффективнее поиска в ширину. Дело в том, что число узлов с глубиной обычно существенно растёт так, что наибольшая их доля приходится на нижний слой (где находится искомый узел). Поэтому повторные пробеги от корня дерева, оказываются не столь затратным по времени, а вот память для хранения списка узлов радикально сокращается по сравнению с поиском в ширину.
Когда глубина дерева неизвестна, поиск с итеративным углублением, обычно, оказыватся наиболее эффективным. Его реализация для подсчёта числа узлов приведена ниже. В этой функции в каждом узле запоминается его глубина на дереве, чтобы при извлечении узла из стека, знать сколько ещё потомков необходимо породить.
function numNodes4 (tr)
{
var depth = 1; // текущая максимальная глубина
var num = 0; // число узлов в дереве
var finish = false;
while( !finish ){ // не закончилось дерево, углубляемся
tr.d = 0; // храним глубину узла
open = [ tr ]; // в стек узлов сначала корень
num = 0; // счётчик числа узлов
finish = true;
while( open.length ){ // пока cтек не пустой
num++;
var n = open.pop(); // берём последний
if(n.d >= depth){ // достигли максимальной текущей глубины
if(n.ar && n.ar.length > 0) // ниже узлы ещё есть,
finish = false; // дерево не закончилось
continue; // смотрим остальные в стеке
}
if(n.ar)
for(var i=0; i < n.ar.length; i++){ // для всех потомков
n.ar[i].d = n.d+1; // запоминаем глубину
open.push(n.ar[i]); // и вталкиваем в стек
}
}
depth++; // глубину погружения можно увеличить и сильнее
}
return num;
}
Анимирование поиска
Визуализация различных способов обхода дерева приведена ниже (малиновый узел - тот, который извлекается из очереди, салатные - находся в очереди, а фиолетовые - уже пройдены):
Сравнение быстродействия
Сравним быстродействие этих функций и максимальные размеры требуемых списков. Создадим сначала дерево глубиной depth с числом ветвлений в каждом узле branches, а затем по-очереди, по loops раз запустим все 4 функции (поиск в ширину со списком - numNodes3 и массивом - numNodes3a):
| создать: | ms | ||
| рекурсия numNodes1: | ms | ||
| в глубину numNodes2: | ms, max len: | ||
| в ширину numNodes3: | ms, max len: | ||
| в ширину numNodes3a: | ms, max len: | ||
| заглубление numNodes4: | ms, max len: |