Искусный просмотр больших древовидных структур
Рассмотрим теперь специальную постановку задачи. Пусть дано множество М в качестве листьев дерева и функция
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
Многие проблемы могут быть представлены по этой схеме. Сюда же относится и проблема выполнимости.
Пример (проблема выполнимости как проблема поиска по дереву).
Проблема выполнимости для булевского выражения может трактоваться по этой схеме следующим образом. Пусть п есть число идентификаторов в выражении. Представим их конкретизацию в виде последовательности длины п логических значений - так, что i-й элемент последовательности является значением i-го идентификатора. Предположим, что булевское выражение задано в форме вычислительного предписания а, которое для конкретизации х с помощью вызова а(х) вычисляет значение выражения для этой конкретизации.
fct baum = ( seq bool х ) set seq bool:
if length(x) ³ n then {x}
else baum(<trie> о x) È baum(<false> о x)
fi
fct suchemin = ( set seq bool s ) scq bool:
if ÷sç = I then some seq bool x: x Î s
else scq bool x = some seq bool z: z Î s;
scq bool у == suchemin(s\{x});
if a(x) Ü a(y) then x
else у
fi
По вызову baum(e) порождаются все возможные различные последовательности длины п логических значений. По вызову suchemin из множества всех этих последовательностей выбирается та минимальная по времени построения последовательность, для которой a(x) дает значение «истина»; если не существует ни одной такой последовательности, то в качестве результата выдается просто самая первая из построенных последовательностей. Таким образом, через (suchemin(baum(e)) решается проблема выполнимости для булевского выражения.
Рекурсивная структура функции baum дает возможность улучшить эффективность алгоритма, если применить:
· умелое отсечение трасс, которые не обещают успеха (см. далее а/р-отсечение, бэктрекинг);
· умелый выбор порядка просмотра (см.
ниже greedy).
Если мы умело выберем порядок просмотра, то «рано» найдем минимальное решение и затем своевременно отбросим неминимальные трассы. Для этого важно, в частности, охватывать совместно («сплавлять») порождение множества и поиск минимума.
Пример (оптимизация поиска в проблеме выполнимости). Более оптимальным является вычислительное предписание
fct suche = (seq bool x) scq bool:
if length(x) = n then x
else seq bool s == <trne> о x;
if fail(a, s) then suche(<false> о x)
else seq bool
у = suche(s);
if a(y) then у
else suche(<false> о x)
fi
fi
fi
При этом мы предполагаем, что - если fail(a, x) дает значение true (т. е. a(x) == false),
для всех последовательностей z справедливо высказывание
length(z о x) == n Þ a(z о x) == false.
Алгоритм suche всегда выдает логическую последовательность, причем если а выполнимо, то выдается последовательность, для которой а справедливо.
Выбор для программы метода улучшения эффективности при решении сложных проблем требует умения, знаний и опыта. Полезен тщательный анализ проблемы. Чем больше мы знаем о проблеме и ее свойствах, тем лучше мы может применить оптимизации.
