Пример 5.3.4.
Goal
Clauses
Predicates
Domains
s=symbol
l= s*
preemn (s, l)
gs(s)
solve (l, l, l)
sol
sol:- solve ([S], P), write(“Sol=”,P), nl.
solve(V, [V]):- gs(V).
solve(V,[V|P]):- preemn (V, [V1|N]), solve(V1, P).
solve(V, P):- preemn(V,[]), P=resh.net,write(P),nl.
sol.
Программа представляет собой реализацию стратегии поиска в глубину на корневом дереве. Ее называют поиском в глубину потому, что программа ведет поиск, выбирая самую глубокую вершину для построения пути - ту, которая расположена дальше всех от начальной вершины. На рис. 5.10.показано, в каком порядке посещаются узлы. Этот порядок соответствует трассировке выполнения программы при поиске цели sol.
Рис.5.9. Схема поиска с возвратами
Рис.5.10. Схема поиска в глубину.
Поиск в глубину в наибольшей степени приемлем для рекурсивного стиля программирования на языке Турбо- Пролог так как сама система при выполнении цели проверяет варианты по принципу поиска в глубину.
Поиск в глубину может привести к процессу, разворачивающемуся вдоль некоторого бесполезного пути, поэтому нужно ввести некоторую процедуру возвращения: после того как в ходе процесса строится вершина с глубиной, превышающей некоторую граничную глубину, раскрывается вершину наибольшей глубины, не превышающей этой границы, и т.д. При этом возникает определенное затруднение, связанное с тем, что подходящий предел необходимо устанавливать заранее. Если этот предел будет установлен слишком низким (т.е. меньшим по сравнению с длиной любого пути решения), поиск завершится неудачей. А если предел будет установлен слишком высоким, поиск потребует лишних затрат времени. Для преодоления этой сложности можно выполнять поиск в глубину итеративно, постепенно изменяя предел глубины, начиная с очень низкого предела глубины и постепенно увеличивая этот предел до тех пор, пока не будет найдено решение. Этот метод называется итеративным углублением. Его можно реализовать путем модификации программы примера 5.3.2, введя параметр максимальной глубины.
/*Программа: поиск в глубину*/