Организация и функционирование компьютеров


Использование указателей для обработки деревьев - часть 4


            write (f, (path[k])^.data);

            if  (path[k])^.down<>Nil  then

                begin      path [k+1] :=(path[k])^.down;

                                k:=k+1

                end

            else

                begin  while (k>0) and ( (path[k])^.right=Nil)  do  k:=k-1;

                             if  k>0  then           path [k] := (path[k])^.right

                end

        end

end;

Другой интересный случай - когда дерево составляют не объекты, а ситуации. Предположим, действительность описывается иерархической структурой ситуаций и нам нужно отыскать ситуацию, к которой относится рассматриваемый нами случай. Пусть мы умеем определять, описывает ли текущая ситуация данный случай или нет. Кроме того, если ситуация не соответствует нашему случаю, пусть мы умеем определять, может ли соответствовать случаю ситуация, подчиненная данной. Другими словами, если x - ситуация, а y - случай, то задана функция  agree(x,y), которая возвращает:

  • -1, если случай противоречит ситуации;
  • +1, если случай может быть согласован с ситуацией;
  • 0, если случай полностью соответствует ситуации.

Предположим также, что мы умеем переходить от текущей ситуации как к ситуации?сына (вниз по дереву ситуаций), так и к ситуации, следующей за данной среди  сыновей ситуации?отца для данной (вправо по дереву ситуаций). Тогда обход множества ситуаций в поисках нужной напоминает вышеприведенную процедуру обхода вершин дерева, причем стратегия обхода зависит от значения функции agree(x,y):

  • если agree(x,y)=0, то текущая ситуация является искомой;
  • если agree(x,y)=-1, то бессмысленно анализировать подчиненные ситуации, то есть с точки зрения поиска текущая ситуация тупиковая и необходимо сделать “шаг вправо”;
  • если agree(x,y)=+1, то следует перейти к подчиненной ситуации, то есть сделать “шаг вниз”.

Обозначенный выше метод перебора ситуаций называется методом ветвей и границ. В качестве примера можно привести задачу расстановки на шахматной доске восьми ферзей таким образом, чтобы они не били друг друга.


- Начало -  - Назад -  - Вперед -



Книжный магазин