 |
|
|
|
Основные процедуры для работы с деревьями
Основные процедуры для работы с деревьями Иерархические структуры доминируют в мире. Систем, построенных на основе бескомпромиссного иерархического подхода, немного, так как такой подход выглядит труднореализуемым. Однако его применение повысит вероятность того, что ваша система в конце концов не окажется в тупике. Статья содержит реализации основных («штатных») процедур для работы с деревьями, включая реализацию алгоритма эвристического поиска. Я попытался продемонстрировать преимущества алгоритма обхода «в ширину» при работе с большими деревьями. Отличительной особенностью алгоритма является то, что он не использует инструментов, создающих неопределенность с точки зрения требований к памяти, таких как рекурсия, очереди и т. п. Основные процедуры для работы с деревьями В системах обработки информации иерархические объекты моделируются деревьями. Схема на рис. 1 демонстрирует связи между объектами, формирующими ветвь дерева.
Рисунок 1. Схема ветви дерева На языке C# эта схема может быть реализована с помощью следующей структуры: public struct ObjectN // объект (узел дерева) { public string J_NAME; // имя объекта public long J_TYPE; // тип объекта(носитель знаний) public long IDF, // указатель на «отца» IDB, // указатель на «брата» ID1C; // указатель на первого потомка } Дерево моделируется массивом структур ObjectN: public static ObjectN[] obj = new ObjectN[]; В качестве идентификатора объекта выступает индекс массива. В реальных системах дерево может храниться в файле, записи которого имеют структуру ObjectN. В этом случае номер записи файла будет являться идентификатором объекта. Схема, показанная на рис. 1, позволяет легко строить и модифицировать деревья произвольного размера и конфигурации. Проблемы с добавлением узлов и вставкой ветвей отсутствуют (имеется в виду отсутствие проблем с перенастройкой системы связей между объектами). Например, для добавления нового узла необходимо знать индекс свободной ячейки массива и идентификатор объекта-«отца»: FreeCell = getfreecell(); obj[FreeCell].IDF = FatherIdentifier; obj[FreeCell].IDB = obj[FatherIdentifier].ID1C; obj[FatherIdentifier].ID1C=FreeCell; Все запросы к иерархически организованным структурам реализуются в процессе обхода узлов дерева. Основной целью обхода является выделение из сложной структуры отдельных фрагментов – целевых объектов. Существуют два основных метода обхода древовидных структур: «depth first» обход (обход в глубину, далее DF-обход) и «breadth first» обход (обход в ширину, далее BF-обход). Маршрут DF-обхода показан на рис. 2.
Рисунок 2. Схема DF-обхода Общее направление обхода – поперек дерева. В процессе обхода для обработки (например, для формирования списка целевых объектов) хаотично выдаются узлы разного уровня. С первых шагов курсор уходит вглубь и, если дерево большое, нескоро вновь окажется на поверхности. Этот метод обхода по смыслу не соответствует иерархической структуре. Преимущества метода связаны с процедурой его реализации и заключаются в том, что каждый узел при DF-обходе посещается только один раз. Проблем с исключением из маршрута неперспективных участков (отсечение ветвей на основе знаний об объектах) не существует. Маршрут BF-обхода показан на рис. 3.
Рисунок 3. Схема BF-обхода Общее направление обхода – сверху вниз. В процессе обхода для обработки последовательно выдаются узлы одного уровня. Курсор предпочитает держаться ближе к поверхности, т.е. к исходному узлу дерева. Можно надеяться, что в этой достаточно ограниченной зоне сосредоточены либо сами целевые объекты, либо промежуточные целевые объекты (т.е. объекты, при посещении которых может быть выполнена процедура отсечения, см. далее). Этот метод обхода, по-видимому, наиболее соответствует иерархической структуре. Недостатки метода связаны с процедурой его реализации. Узлы в процессе BF-обхода посещаются более одного раза. Отсечение ветвей выполнить труднее, чем при DF-обходе. Работа с большими деревьями невозможна без использования процедуры отсечения ветвей. Решение об отсечении принимается на основе знаний об отношениях между встреченными и целевыми объектами. Например, мы знаем, что бесперспективно искать письма в фотоальбоме. В случае дефицита знаний принятие решения об отсечении в данном узле невозможно. В этом случае встает вопрос о том, куда двигаться дальше: уходить в глубину, т.е. совершать DF-обход, или оставаться на поверхности, т.е. совершать BF-обход. На мой взгляд, второй вариант более безопасен по причине, которая уже упоминалась при обсуждении особенностей BF-обхода. Преимущества BF-обхода могут быть использованы в процедурах поиска объектов. Например, нужно найти файл mpwt.doc. Полный адрес файла: docsdescsourvar1ver1mpwt.doc. Было бы неплохо иметь возможность вместо полного адреса вводить отдельные узловые точки. В этом случае задание на поиск объекта могло бы выглядеть так: desc;var1;mpwt.doc. Папки desc и var1 являются промежуточными целевыми объектами. Для того чтобы выполнить задание, процедура поиска должна быстро просканировать близлежащие уровни и выполнить необходимые отсечения. Я думаю, что полезной стратегией поиска могла бы быть такая: как можно быстрее найти хотя бы один целевой объект, получить от него дополнительную информацию, использовать эту информацию для уточнения района дальнейшего поиска. BF-обход хорошо подходит для этой стратегии. Работа с иерархическими структурами изначально ориентирована на использование знаний. В структуре ObjectN элементом, предназначенным для выполнения функции носителя знаний, является тип объекта. Тип объекта можно рассматривать как ссылку на абстрактный объект, обладающий типовыми свойствами. Это эквивалентно понятию «класс» в языках программирования. Разработчику иерархического специализированного приложения придется выстроить собственную систему работы со знаниями. Такие понятия, как абстрактные объекты, типовые структуры объектов, типовые свойства и отношения объектов и т. п., должны храниться в базе знаний системы. Например, файл отношений между абстрактными объектами может выглядеть так, как представлено в таблице. Файл отношений между абстрактными объектами
Знания из этой таблицы могут быть использованы для принятия решений об отсечении неперспективных ветвей. В процессе обхода дерева объектов можно отбрасывать все объекты (ветви), не совместимые с разыскиваемым объектом. Нерекурсивная процедура descent реализует на языке C# алгоритм BF-обхода дерева объектов. Вместе со встроенной возможностью отсечения ветвей она также реализует алгоритм эвристического поиска: public static int descent(long SourceObj,int TravDepth) // SourceObj - указатель исходного узла обхода // TravDepth - лимит глубины обхода { long[] Router = new long[TravDepth]; // маршрутизатор int Lev, // счетчик уровней дерева cur; // вспомогательный указатель уровня bool EOTree, // признак завершения дерева EOLev; // признак завершения уровня long ObjPnt, // вспомогательный указатель объекта FirstCh; // указатель на первого потомка исходного узла FirstCh=obj[SourceObj].ID1C; EOTree=false; Lev=0; while (!EOTree && Lev<TravDepth) {// цикл по уровням EOTree=true; ObjPnt=FirstCh; Lev=Lev+1; cur=1; EOLev=false; while (!EOLev) {// DF-обход фрагмента дерева глубиной Lev // спуск по левому краю ветви while (cur < Lev) { Router[cur]=ObjPnt; cur=cur+1; // Здесь может быть вставка – фрагмент кода,реализующий отсечение ObjPnt=obj[ObjPnt].ID1C; if (ObjPnt<1) break; // узел не имеет потомков } // выпуск очередной порции узлов уровня Lev while (ObjPnt>0) { Console.WriteLine("object: {0}",obj[ObjPnt].J_NAME); // здесь может быть процедура обработки объекта EOTree=EOTree && (obj[ObjPnt].ID1C<1); ObjPnt=obj[ObjPnt].IDB; } // подняться по массиву Router до первого ненулевого указателя на объект cur=cur-1; while (cur>0) { ObjPnt=obj[Router[cur]].IDB; if (ObjPnt>0) break; cur=cur-1; } if (cur == 0) EOLev=true; } // обход фрагмента дерева глубиной Lev } // цикл по уровням return(0); } Выпуск узлов уровня Lev осуществляется в результате DF-обхода верхней части (от уровня 1 до уровня Lev) дерева, но только узлы уровня Lev выпускаются. В процессе BF-обхода дерева с количеством уровней L каждый узел, лежащий на уровне Lev, посещается L-Lev+1 раз. В момент посещения каждого узла его полная генеалогия хранится в массиве Router. Как видно, BF-обход является надстройкой над DF-обходом. Эта избыточность алгоритма иногда может обернуться его преимуществом. Так как процедура постоянно откатывается назад, она имеет возможность в это время подкорректировать параметры отсечения ветвей и соответственно границы района поиска объектов. Отсечения неперспективных объектов возможны с помощью следующей процедуры: // фрагмент кода, реализующий отсечение // compatible – функция, определяющая совместимость объектов // target_j_type - тип целевого объекта if (!compatible(obj[ObjPnt].J_TYPE, target_j_type)) { ObjPnt=0; break; // как если бы узел не имел потомков } Процедура наследования свойств реализуется с помощью посещения предков объекта и получения от них недостающей информации. while (ObjPnt != RootPnt) { // if (информация получена) break; ObjPnt=obj[ObjPnt].IDF; } Эту процедуру можно использовать в процессе обработки выделенных объектов, т.е. после того, как процедура обхода выполнила свою задачу, сформировав список целевых объектов. Заключение В случае больших деревьев маловероятно то, что полная информация об отношениях между объектами доступна. BF-обход с использованием (там, где это возможно) отсечений – наиболее подходящая процедура для работы с такими деревьями. Удачи! |
АЛЕКСАНДР ЯМПОЛЬСКИЙ
Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
