Конспект установочных лекций по комплексному курсу Информатика, Теория информации


Искусный просмотр больших древовидных структур


Рассмотрим теперь специальную постановку задачи. Пусть дано множество М в качестве листьев дерева и функция

f: М ® О,

где О - множество с линейным порядком. Требуется найти элемент х из М, для которого f(x) минимальна. Точнее говоря, ищется элемент х Î М, для которого справедливо

f(x) - min {f(y): у Î М}.

Обратим внимание, что упомянутые выше NP-полные проблемы могут быть приведены к этой форме. Эффективный поиск в пространстве поиска состоит, в частности, в комбинации порождения множества и исследования его элементов при исключении запоминания всего множества. Если множество порождается рекурсивно, то принцип порождения определяет на дереве вызовов древовидное упорядочение элементов рассматриваемого множества. Схематически такую проблему можно представить приведенным ниже алгоритмом. Алгоритм baum рекурсивно порождает множество, в котором должен производиться поиск решения, а алгоритм suchemin берет это множество в качестве входа и ищет в нем элемент, для которого функция f принимает наименьшее значение. При этом пусть заданы: предикат vollstandig, который проверяет, является ли исследуемый элемент х нужным элементом просматриваемого множества; функции gi, которые представляют альтернативы для построения элементов множества, и функция k, обозначающая степень разветвления. Эти функции соответствуют принятию решения о выборе в недетерминированном дереве вычислений Т-машины

  fct baum = (m x) set m:

         if vollstandig(x)        then

{x}

                                else    È    baum(gi(x)) fi

                                     1 £ i £ k(x)

  fct suchemin = (set m s) m:

         if ÷sç = 1           then    some m x: xÎs

else m

x = some m z: zÎs

       m y = suchemin(s\{x});

       if  f(x)£f(y)         then

x

                                  else   y

       fi

fi

Многие проблемы могут быть представлены по этой схеме. Сюда же относится и проблема выполнимости.

Пример (проблема выполнимости как проблема поиска по дереву).


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



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