Декларативное программирование

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]

© 2003 И.А. Дехтяренко

6.4. Задачи поиска

Задачи, о которых пойдет речь, формулируются следующим образом:

Найти в заданном множестве X элемент(ы) x, удовлетворяющие заданным условиям K(x).

Очевидный способ решать такого рода задачи - поочередно перебирать элементы множества X и проверять выполнение условий K(x) для каждого элемента. Столь же очевидно, что этот способ не очень хорош, если множество X (пространство перебора) содержит много элементов или даже бесконечно.

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

Задачи на удовлетворение ограничений.

Часто пространство перебора X является декартовым произведением множеств X₁,...,X_n. В этом случае задачу обычно называют проблемой удовлетворения ограничений и формулируют следующим образом.

Найти значения переменных x₁ ..., x_n , областями значений которых являются множества X₁,...,X_n, удовлетворяющие одновременно всем заданные ограничения K_i(x₁,..., x_n).

Криптоарифметика.

Замечательный пример такого рода - криптоарифметические задачи занимательной математики. Вот наиболее известный пример

  SEND
 +MORE
 -----
 MONEY

Простейшее решение основано на методе "образовать и проверить". Мы перебираем все возможные значения для переменных и проверяем выполнение заданных условий.

solve([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]) :-
    digit(S), digit(E), digit(N), digit(D),
    digit(M), digit(O), digit(R), digit(Y),
    S\==0, M\==0,
    all_different([S,E,N,D,M,O,R,Y]),
              1000*S + 100*E + 10*N + D
     +        1000*M + 100*O + 10*R + E
    =:=
    10000*M + 1000*O + 100*N + 10*E + Y.

digit(D) :- between(0,9,D).

Предикат all_different введен с целью избежать необходимости выписывать длинный ряд неравенств (E\==S, N\==S, N\==E, и т.д.)

all_different([]).

all_different([X|Xs]):-
    \+ member(X,Xs), all_different(Xs).

Мы можем запустить эту программу и в конце концов получить ответ.

?- solve(X).
X = [9, 5, 6, 7]+[1, 0, 8, 5]=[1, 0, 6, 5, 2] 

Yes

Однако, чтобы дождаться ответа потребуется изрядная доля терпения. Пространство перебора в данном случае выбрано крайне неудачно - оно содержит 10⁸ элементов. Но его легко можно сократить, если учитывать некоторые из ограничений в процессе генерации. Прежде всего - это условие, что все значения переменных различны. Оно сокращает пространство перебора до 10!/2!, то есть примерно в 50 раз. Соответственно уменьшается и время работы программы.

solve([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]) :-
    range(0,9,L0),
    selects([S,E,N,D,M,O,R,Y],L0),
    S\==0,  M\==0,
               1000*S + 100*E + 10*N + D
      +        1000*M + 100*O + 10*R + E
     =:=
     10000*M + 1000*O + 100*N + 10*E + Y.

Предикат selects уже встречался, а range(A,B,L) возвращает список L чисел от A до B.

selects([],_).
selects([X|Xs],Ys) :- select(X,Ys,T), selects(Xs,T).

range(N,N,[N]).
range(M,N,[M|Ns]):- M < N, M1 is M+1, range(M1,N,Ns).

Понятно, что лучше всего отсекать ненужные варианты как можно раньше. Например, некоторого ускорения можно добиться учитывая ограничения S\==0 и M\==0 в процессе генерации.

range(0,9,L0),
select(S,L0, L1), S\==0,
и т.д.

Более существенное усовершенствование - пересмотреть структуру ограничений. Для этого вспомним, как выполняется сложение столбиком, и определим предикат adc - сложение двух однозначных чисел с переносом.

adc(A, B, Res, Cin, Cout) :-
    Sum  is A + B + Cin,
    Res  is Sum mod 10,
    Cout is Sum // 10.

Теперь можно внедрить ограничения в процесс генерации и тем самым сократить пространство перебора более чем в 1000 раз.

solve([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]) :-
    range(0,9,L0),        select(D,L0,L1),
                          select(E,L1,L2),
    adc(D, E, Y, 0, C1),  select(Y,L2,L3),
                          select(N,L3,L4),
                          select(R,L4,L5),
    adc(N, R, E, C1, C2), select(O,L5,L6),
    adc(E, O, N, C2, C3), select(S,L6,L7), S\==0,
                          select(M,L7,L8), M\==0,
    adc(S, M, O, C3, M).

Забавы ради можно придать программе "красивый" вид, используя нотацию DCG.

solve(X):- range(0,9,L),solve(X,L,_).

solve([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]) -->
                            d(D),d(E),
    {adc(D, E, Y, 0, C1)},  d(Y),d(N),d(R),
    {adc(N, R, E, C1,C2)},  d(O),
    {adc(E, O, N, C2,C3)},  f(S),f(M),
    {adc(S, M, O, C3,
               M)}.

d(X) --> select(X).
f(X) --> select(X),{X\==0}.

И все-таки, согласитесь, первоначальное решение подкупает своей очевидностью.

Задача о ферзях.

На шахматной доске размером NxN требуется расставить N ферзей, так, чтобы они не били друг друга.

Если представить позицию в виде набора из координат x и y всех ферзей, то задачу можно сформулировать как задачу на удовлетворение ограничений.

Найти набор значений для x₁,y₁,x₂,y₂,...,x_N,y_N, из множества [1..N] такой, что для всех различных i и j выполняются условия:

1. x_i =/= x_j (ферзи не стоят на одной вертикали);
2. y_i =/= y_j (ферзи не стоят на одной горизонтали);
3. |x_i - x_j| =/= |y_i - y_j| (ферзи не стоят на одной диагонали).

Можно попытаться решить эту задачку методом перебора

queens(N,Ys-Xs) :-
    range(1,N, Ns),
    length(Xs, N), members(Xs,Ns),
    length(Ys, N), members(Ys,Ns),
    safe(Ys-Xs).

Однако размер пространства перебора N^2N должен насторожить. Для классического случая N=8 придется рассмотреть порядка 10¹⁴ вариантов. Заметим, что среди координат x ферзей x₁,x₂,...,x_N ровно один раз встречается каждое из чисел 1,2,...,N. Таким образом, номера ферзей можно рассматривать как координаты x и достаточно перебирать только координаты y. Новая формулировка задачи:

Найти набор (y₁,y₂,...,y_N), 1<y_i<N такой, что для всех различных i и j выполняются условия:

1. y_i =/= y_j
2. |y_i - y_j| =/= | i-j |.

Новая схема перебора будет выглядеть так

queens(N,Ys) :-
    range(1,N, Ns),
    length(Ys, N),
    members(Ys, Ns),
    safe(Ys).

Теперь пространство перебора содержит N^N (для N=8 -10⁷) вариантов, что уже лучше, но все еще многовато. Если учесть, что среди координат y ферзей y₁,y₂,...,y_N каждое из чисел 1,2,...,N также встречается ровно один раз, можно еще раз переформулировать задачу.

Найти набор различных (y₁,y₂,...,y_n), 1<y_i<N, такой что |y_i - y_j| =/= | i-j | при i =/= j.

Конечно это, по сути, то же самое, просто мы переносим условие y_i =/= y_j из множества ограничений в определение пространства перебора. Процедура перебора изменяется незначительно.

queens(N,Ys) :-
    range(1,N, Ns),
    length(Ys, N),
    selects(Ys, Ns),
    safe(Ys).

Пространство перебора сокращается с N^N до N!, что для N=8 означает 40 320 и уже приемлемо. Теперь можно записать процедуру проверки.

safe([Y|Ys]) :- noattack(Y,Ys), safe(Ys).
safe([]).
noattack(Y,Ys)  :-   noattack(Y,Ys,1).
noattack(_,[],_).
noattack(Q,[Y|Ys],D) :-
    abs(Q-Y) =\= D,
    D1 is D+1,
    noattack(Q,Ys,D1).

Однако факториал есть факториал и если для N=8 время поиска всех ответов измеряется секундами, то для N=10 это уже минуты, а для N=12 - часы. Ничего поделать с природой задачи мы не можем - невозможно сделать из свиньи скаковую лошадь. Но можно получить более быструю свинью. Мы можем, как и в предыдущем примере, переместить проверку ограничений в процедуру генерации. Выбирая положение очередного ферзя, будем проверять его совместимость с расставленными ранее. Тем самым мы объединим процедуры selects и safe в одну процедуру place_queens. Эта процедура имеет дополнительный аргумент Board, содержащий список уже расставленных ферзей.

queens(N,Ys) :-
   range(1,N,Ns),
   length(Ys,N),
   place_queens(Ys,Ns,[]).
place_queens([Y|Ys], Ns, Board) :-
    select(Y, Ns, Ns1),
    noattack(Y, Board),
    place_queens(Ys, Ns1, [Y|Board]).
place_queens([],_,_).

В сравнении с предыдущей эта программа выполняется раз в 20 быстрее при N=8, а кроме того время вычислений пропорционально уже N!^0.7.

Заметим, что процедура place_queens сама содержит пару из генератора и теста. Мы сначала выбираем положение ферзя посредством select, а затем проверяем его на совместимость, вызывая noattack. Заманчиво объединить и эти две процедуры. Однако, чтобы такое объединение имело смысл, необходимо научиться выбирать только допустимые положения. Для этого потребуется нечто большее, чем просто список уже расставленных ферзей. В своей знаменитой статье [1] Никлаус Вирт использовал два булевых массива представляющих /-диагонали и \- диагонали. Мы несколько модифицируем эту идею, и будем использовать два списка Us и Ds, содержащие переменные, "охраняющие" диагонали. Каждая переменная представляет одну диагональ. При размещении очередного ферзя переменная из списка Ys связываетя с номером ферзя, но одновременно мы будем связывать соответствующие переменные из списков Us и Ds. Поскольку переменная может только иметь одно значение, как только она связана, никакой другой ферзь уже не может оказаться на той же диагонали (этот же трюк мы применяли при раскраске карты). Процедура place_queens после выбора положения для ферзя "сдвигает" Us и Ds на одну позицию в разные стороны.

queens(N,Ys) :-
    range(1,N, Ns),
    length(Ys, N),
    place_queens(Ns,Ys,_,_).
place_queens([N|Ns], Ys, Us, [D|Ds]):-
    place1(N, Ys, Us, [D|Ds]),
    place_queens(Ns, Ys, [U|Us], Ds).
place_queens([], _, _, _).
place1(N,[N|_], [N|_],[N|_]).
place1(N,[_|Cs],[_|Us], [_|Ds]):- place1(N,Cs,Us,Ds).

Такое усовершенствование дает выигрыш в скорости в 2-3 раза, но в целом оказывается не очень существенным. Пространство перебора остается, по сути, тем же самым. Ускоряется лишь проверка возможности очередного выбора. Тем не менее, эта программа иллюстрирует важный метод решения задач, называемый распространением ограничений (constraints propagation). Каждый выбор значения для очередной переменной ограничивает возможность выбора для других переменных.

Распространение ограничений - довольно общий принцип, допускающий разнообразные реализации. Важный способ реализации этого метода - вести явный учет возможных значений для каждой переменной, в нашем случае - возможных положений для каждого ферзя. Этот метод называется "просмотром вперед" (forward checking). Заведем список пар (номер ферзя : список допустимых положений). Вначале каждый ферзь получает полную свободу, его список имеет вид [1,2,...N]. Размещая очередного ферзя, мы удаляем атакованные им позиции из допустимых положений оставшихся ферзей, ограничивая тем самым возможность выбора.

queens(N, Queens) :-
    range(1,N, Ns),
    init_vars(Ns, Ns, V),
    place_queens(V,Queens).
init_vars([X|Xs],Ys,[X:Ys|V]) :-
    init_vars(Xs,Ys,V).
init_vars([], _, []).
place_queens([X:Ys|V],[X-Y|Qs]) :-
    member(Y, Ys),
    prune(V, X, Y, V1),
    place_queens(V1,Qs).
place_queens([],[]).
prune([Q:Ys|Qs], X,Y, [Q:Ys1|Ps]) :-
    sublist(noattacks(X,Y,Q), Ys, Ys1),
    Ys1 \== [],
    prune(Qs, X,Y, Ps).
prune([], _,_, []).
noattacks(X1,Y1,X2,Y2) :-
    Y1 \== Y2,
    abs(Y2 - Y1) =\= abs(X2 - X1).

Встроенный предикат sublist - аналог функции filter. Он возвращает список тех элементов списка, для которых выполняется указанный предикат. В сущности, это более быстрый способ выполнить

findall(T, (member(T,Ys),noattacks(X,Y,Q,T)) , Ys1)

Обратите внимание на проверку Ys1 \== [] . Если для какого либо из еще не размещенных ферзей не остается свободных мест, prune завершается неудачей. Таким образом, предполагаемое положение ферзя отвергается сразу.

Теперь предположим, что мы не стали включать указанную проверку в prune. Тогда, вместо того чтобы тупо расставлять ферзей одного за другим, разумно сначала убедиться, что среди не размещенных ферзей нет таких, которые нельзя разместить. Далее надо посмотреть, нет ли таких ферзей, для которых существует всего один вариант размещения и, если есть, выбрать именно такого. Аналогично, в общем случае лучше выбирать того ферзя, для которого осталось меньше всего свободных мест. Итак, мы можем усовершенствовать программу, изменив порядок расстановки ферзей. Поскольку теперь ферзи необязательно будут размещаться по порядку, результат будем представлять в виде списка пар X-Y.

place_queens(V, [X-Y|Qs]) :-
    queen_to_place(V,X:Ys,V1),
    member(Y, Ys),
    prune(V1, X, Y, V2),
    place_queens(V2,Qs).
place_queens([], []).

Процедура queen_to_place выбирает ферзя подлежащего размещению из списка не размещенных. Если запишем просто

queen_to_place([V|Vs],V,Vs).

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

queen_to_place([V|Vs], Q, Vx) :- select_boundest(Vs, V, Q, Vx).
select_boundest([], Q, Q, []).
select_boundest([X|Xs], Q, Qm, [Q|R]) :-
    shorter(X, Q), !,
    select_boundest(Xs, X, Qm, R).
select_boundest([X|Xs], Q, Qm, [X|R]) :-
    select_boundest(Xs, Q, Qm, R).
shorter(_:L1, _:L2) :- length(L1,N1), length(L2,N2), N1<N2.

При сокращении пространства перебора надо соотносить размер этого сокращения с затратами на его реализацию. На небольших досках эта программа оказывается даже медленнее - затраты на реализацию более сложной схемы съедают весь выигрыш от сокращения. Тем не менее, с ростом N сокращение играет все большую роль. Время, выполнения программы растет как квадратный корень из N!, а это означает, что мы сможем решить задачу для досок большего размера.

Упражнение.

Процедура queen_to_place допускает очевидное усовершенствование. Найдите и реализуйте его.

Упражнение.

Задача о раскраске карты (или о раскраске вершин графа) - более важный пример задачи на удовлетворение ограничений. Решите ее, используя мето просмотра вперед.

Стоит упомянуть и другие возможности. Кроме выбора "самого ограниченного" ферзя, полезным может оказаться и выбор "самого ограничивающего", то есть такого, который отнимает у других наибольшее число полей. Можно выбирать и "самого ограничивающего" из "самых ограниченных". Возможен и более глубокий просмотр, когда производится проверка на совместимость еще не размещенных ферзей. Например, если два ферзя претендуют на одну и ту же строку продолжать поиск бессмысленно.

Поиск на графах.

Другой важный случай пространства поиска - множество путей в некотором графе. Многие задачи можно сформулировать следующим образом:

• Дано некоторое исходное состояние.
• Определено множество целевых состояний. Это множество может состоять из одного элемента, а может задаваться некоторым правилом, определяющим, что цель достигнута.
• Определено множество операций, которые можно использовать для изменения текущего состояния.
• Требуется найти последовательность операций, приводящих к целевому состоянию.

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

Начнем с простейшего случая, когда граф представляет собой просто бинарное отношение на множестве вершин. То есть мы абстрагируемся от различных атрибутов, присущих дугам и рассматриваем бинарное отношение arc(A,B) которое означает что в графе имеется дуга из A в B. В простых примерах можно явно перечислить все дуги, в более сложных это отношение определяется программой. Неориентированный граф можно представить как ориентированный, поставив в соответствие каждому ребру две дуги.

arc(A,B) :- edge(A,B); edge(B,A).

Другое практически важное представление основано на идее окрестности вершины. Граф определяется отношением neighborhood(A,NB), связывающим вершину со списком ее соседей. Подобным образом мы представляли граф, раскрашивая карту. Нетрудно определить процедуры позволяющие переходить от одного представления к другому.

arc(A,B):- neighborhood(A,NB),member(B,NB).
neighborhood(A,NB):- setof(B,arc(A,B),NB).

Рефлексивно-транзитивное замыкание.

В терминах arc, мы можем определить другое бинарное отношение connected означающее, что две вершины связаны нектоторым путем. С математической точки зрения мы строим рефлексивно-транзитивное замыкание отношения arc, то есть наименьшее отношение, включающее arc, и обладающее свойствами рефлексивности и транзитивности. Эти условия можно прямо записать на Прологе.

connected(A,A) .
connected(A,B) :- connected(A,C), connected(C,B).
connected(A,B) :- arc(A,B).

Очевидно, бесполезно пытаться запустить эту программу¹. Но несложными рассуждениями нетрудно получить логически эквивалентное определение, которое вполне пригодно в качестве программы.

connected(A,A).
connected(A,B) :- arc(A,C), connected(C,B).

Эта программа выполняет поиск в глубину (Depth-First Search, DFS), основываясь на стратегии вычислений Пролога. Она хорошо работает на конечных деревьях и приемлемо на конечных бесконтурных графах, которые в процессе поиска разворачиваются опять же в конечные деревья. Но если дерево поиска бесконечно, программа вполне может попасть на бесконечную ветвь и остаться там навсегда.

Бесконечные ветви в дереве поиска возникают, если граф конечен, но имеет циклы.

arc(a,b). arc(b,a).
arc(b,c). arc(c,d).
?- connected(a,d).

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

arc(X,Y) :- succ(X,Y).
arc(X,Y) :- succ(Y,X).

?- connected(1,0).

Итак, нам потребуется некоторый метод устранения бесконечных ветвей из дерева поиска.

Для конечных графов, мы можем вести учет просмотренным вершинам. Определим новое отношение connected(A,B,S), означающее что A и B связаны путем, не проходящим ни через одну из вершин множества S. Для представления множества проще всего использовать список, в который будем добавлять просмотренные вершины.

connected(A, A, _) .
connected(A, B, S) :-
    arc(A,C),
    \+ member(C, S),
    connected(C,B,[C|S]).
connected(A,B) :- connected(A,B,[]).

Легко видеть что для этой программы, дерево поиска конечно, даже если граф имеет циклы. Число вершин в списке S не может превзойти общего количества вершин в графе.

Поиск с ограничением на глубину.

Другой метод борьбы с бесконечностью - ограничить глубину поиска. Пусть отношение connected_b(A, B, N) означает что A и B связаны путем, длины не более чем N.

connected_b(A, A, _).
connected_b(A, B, N) :-
    N>0,
    arc(A,C),
    N1 is N-1, connected_b(C,B,N1).

Теперь если известна верхняя граница длины самого короткого пути от одной вершины до другой (диаметр графа), мы можем указать ее в качестве значения для N. Например

connected(A,B) :- connected_b(A,B,1000).

Эту программу можно использовать для поиска на бесконечных или очень больших графах. Если решение существует и находится не слишком далеко, оно будет найдено. Подойдет она и для графа с циклами - бесконечные ветви будут отсекаться по достижению заданной глубины.

Метод последовательных углублений

Как быть, если у нас нет никакой априорной оценки для глубины поиска? В таком случае можно использовать методику, называемую последовательным или итерационным углублением. Начиная с малого значения N, хотя бы и c 1, мы пробуем последовательно все большие значения, пока некоторое из них не даст решение. В результате получится "поиск в глубину с итерационным углублением" (Depth-First Iterative Deepening, DFID). Можно записать внешнюю процедуру, которая итерационно вызывает процедуру с ограничением и останавливается когда решение найдено. Например

connected_i(A,B,N) :- connected_b(A,B,N).
connected_i(A,B,N) :- N1 is N+1, connected_i(A,B,N1).
connected(A,B) :- connected_i(A,B,1).

Однако что будет если мы вызовем connected для несвязанных вершин? Очевидно, connected_b будет все время завершаться неудачей, а connected_i будет упрямо увеличивать глубину поиска и вновь вызывать connected_b. Дело в том, что программа не различает, почему поиск завершился неудачно: то ли потому что все возможности исчерпаны, то ли потому, что достигнута граница на глубину поиска. Можно добавить соответствующую проверку

connected_i(A,B,N) :- connected_b(A,B,N).
connected_i(A,B,N) :- reach_bound(A,B,N), N1 is N+1, connected_i(A,B,N1).
reach_bound(_, _, 0).
reach_bound(A, B, N) :-
    N>0,
    arc(A,C),
    N1 is N-1, reach_bound(C,B,N1).

но это удвоит объем работ.

Другая возможность - воспользоваться побочным эффектом. Определим динамически изменяемый факт (попросту флаг) bound, который будет означать, что неудача, возможно, вызвана ограничением на глубину поиска и будем проверять его, прежде чем углублять поиск.

:- dynamic bound/0.
connected_i(A,B,N) :-
    connected_b(A,B,N).
connected_i(A,B,N) :-
    bound, retract(bound),
    N1 is N+1, connected_i(A,B,N1).
connected_b(A, A, _) .
connected_b(_, _, 0) :- 
    assert(bound), fail.
connected_b(A, B, N) :-
    N>0,
    arc(A,C),
    N1 is N-1, connected_b(C,B,N1).

Это уже мало напоминает логическое программирование, но, к сожалению, нет естественного способа передавать эту информацию. Еще одна проблема - поскольку мы сняли ограничение на глубину поиска, циклы в графе снова могут доставить неприятности. Разумеется, можно применить запоминание просмотренных вершин или установить еще одно ограничение на глубину.

Поиск в ширину

Мы можем вообще отказаться от поиска в глубину и реализовать другую стратегию поиска. Многообещающе выглядит поиск в ширину (Breadth-First Search, BFS). Проще всего применить ту же схему, что и при обходе двоичного дерева. Поскольку нам потребуется получать сразу все соседние вершины, удобно будет использовать соответствующее преставление графа.

Определим отношение reach(S, B) означающее, что одна из вершин множества S связана с B. Пусть A содержится в S, причем A\=B. Очевидно, соотношение не нарушится, если мы подставим вместо A множество ее соседей.

connected(A,B) :- reach([A],B).
reach([A|_], A).
reach([A|As], B) :-
    neighbours(A,Ns),
    append(As,Ns,Zs),
    reach(Zs,B).

Соседи каждой вершины добавляются в конец списка вершин, так что все соседи данной вершины будут просмотрены прежде чем соседи этих соседей. Это и означает поиск в ширину. Заметим что если вместо append(As,Ns,Zs) подставить append(Ns,As,Zs) все соседи вершины попадут в начало списка и мы получим обычный поиск в глубину, но уже не использующий механизм отката.

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

DFID против BFS

Поиск в ширину, как и поиск с последовательным углублением находит кратчайший путь между вершинами. Действительно, сначала рассматриваются все вершины, достижимые за один шаг, затем за два и т.д. Его недостаток - большие требования к памяти.

Пусть пространство поиска переставляет собой дерево, каждая вершина которого имеет b потомков. Тогда на глубине k находится b^k вершин, а общее количество вершин в дереве с n уровнями

1+b+b²+...+bⁿ = (bⁿ⁺¹-1)/(b-1)

При поиске в ширину каждый уровень дерева должен запоминаться до того, как будет просмотрен следующий, так что придется одновременно помнить bⁿ вершин. Поиск в глубину потребует места только для bn вершин. Однако при итерационном углублении мы каждый раз повторяем все вычисления, проделанные на предыдущих итерациях. Это кажется возмутительным, но на самом деле, дело обстоит не так плохо.

Обычный перебор будет обрабатывать каждую вершину один раз, а итерационный - просмотрит вершину, расположенную на глубине k, n-k раз. Итого придется рассмотреть

n+(n-1)b+(n-2)b²+...+ bⁿ < bⁿ⁺²/(b-1)²

вершин. То есть, при достаточно больших n метод последовательных углублений потребует в b/(b-1) раз больше времени, что не так уж и много. Итак, BFS требует порядка O(bⁿ) времени и памяти, а DFID - O(bⁿ) времени и O(n) памяти. Поскольку память - очень ценный ресурс, DFID считается оптимальным во всех отношениях.

Слабое место в этих рассуждениях - предположение, что граф является деревом. На других графах результаты могут оказаться не столь однозначными. Например, для "ромбического" графа результаты будут явно в пользу BFS, а для графов с циклами, возможно, придется дополнительно тратить память, чтобы учитывать просмотренные вершины.

Разумеется, рассмотренные методы применим не только для поиска на графах, но для и для любых программ, в тех случаях, когда стратегия вычислений Пролога оказывается неудовлетворительной. Например, мы можем преобразовать программу так, чтобы каждая процедура получила два дополнительных аргумента: ограничение на число шагов и разность между этим ограничением и числом шагов, фактически использованных. Например, предложение

p(X, Z):-  q(X, Y), r(Y, Z).

преобразуется в

p(X, Z, B, D):-
    B>0,
    B1 is B-1, q(X, Y, B1, D1),
    r(Y, Z, D1, D).

Сначала мы вызываем первую подцель q с уменьшенным ограничением (B1=B-1). В случае успеха q возвращает оставшееся число шагов (D1). Это число передается следующей подцели r в качестве нового ограничения. Преобразовав таким образом каждое предложение программы, мы получим новую версию программы с ограничением на глубину поиска.

Подобные преобразования лучше делать автоматически и некоторые Пролог-системы имеют соответствующие средства для этого. Так в Ciao можно объявить

:- iterative(connected/2,10,next).

connected(A,A).
connected(A,B) :- arc(A,C), connected(C,B).

next(X,Y) :- Y is X + 5.

Это означает что предикат connected/2 должен выполняться с последовательным углублением, начиная с  границы 10, а следующее ограничение определяется предикатом next, то есть увеличивается на 5. А вот следующее определение приведет к поиску в ширину.

connected(A,A) <- .
connected(A,B) <- arc(A,C), connected(C,B).

Процедуры поиска.

Разобравшись с основными методами, перейдем собственно к процедурам поиска. Пусть задача определяется тремя предикатами.

arc(State, Op, NewState)

Оператор Op преобразует состояние State в состояние NewState.

solution(State)

Состояние State является решением.

starting(State)

State - исходное состояние.

Наша задача - написать процедуру solve, которая возвращает последовательность операторов, преобразующих исходное состояние в некоторое состояние, являющееся решением задачи. Вообще, последнее может быть заранее неизвестным, поэтому будем возвращать пару из состояния и последовательности операторов.

Начнем с простого поиска в глубину.

search(State,Path, State-Path) :- solution(State).
search(State,Path, Answer) :-
    arc(State,Op,NewState),
    search(NewState,[Op|Path], Answer).

Процедура solve просто вызывает search с начальными параметрами а затем обращает полученный список операторов, поскольку они накапливаются в обратном порядке.

solve(State,Answer) :-
    starting(Start),
    search(Start,[], State-Path),
    reverse(Path,Answer).

Теперь добавим дополнительный аргумент - список просмотренных состояний.

solve(State,Answer) :-
    starting(Start),
    search(Start,[], [Start], State-Path),
    reverse(Path,Answer).
search(State,Path,_, State-Path) :- solution(State).
search(State,Path, Seen, Answer) :-
    arc(State,Op, NewState),
    \+ member(NewState, Seen),
    search(NewState,[Op|Path], [NewState|Seen], Answer).

Процедура поиска в ширину в целом аналогична reach, но оперирует парами вида (состояние, последовательность операторов).

solve(State,Answer) :-
    starting(Start),
    search([d(Start,[])], [Start], d(State,Path)),
    reverse(Path,Answer).
search([d(State,Path)|_],_, d(State,Path)) :-
    solution(State).
search([d(State,Path)|FR], Seen, Answer) :-
    findall(d(NewState,[Op|Path]),
           (arc(State, Op, NewState), \+ member(NewState, Seen)),
            NBs),
    mark(NBs, Seen, NewSeen),
    append(FR,NBs,NewFR),   % BFS
    search(NewFR, NewSeen, Answer).

Процедура mark добавляет новые состояния к списку уже просмотренных.

mark([], Seen, Seen).
mark([d(State,_)|Ns], Seen, NewSeen) :-
    mark(Ns,[State|Seen], NewSeen).

Для того, чтобы заставить программу выполнять поиск в глубину, достаточно изменить одну строчку в определении search, так чтобы новые вершины добавлялись в начало списка, то есть вместо

append(FR,NBs,NewFR),  %DFS

написать

append(NBs,FR,NewFR),  %DFS

На основе этой процедуры можно реализовать метод последовательных углублений. Два дополнительных параметра потребуются для ограничения на глубину и для флага. Мы устанавливаем флаг в bound, когда длина какого либо пути превосходит текущее ограничение. Это избавляет нас от необходимости прибегать к некрасивым трюкам с пробочными эффектами.

solve(State,Answer) :-
    starting(Start),
    search([d(Start,[])],1, normal, [Start], d(State,Path)),
    reverse(Path,Answer).
search([d(State,Path)|_], _, _,  _, d(State,Path)) :-
    solution(State),!.
search([d(_,Path)|FR],Lim, _, Seen, Answer) :-
    length(Path,N), N > Lim,!,
    search(FR, Lim, bound, Seen, Answer).
search([d(State,Path)|FR], Lim, WF, Seen, Answer) :-
    findall(d(NewState,[Op|Path]),
           (arc(State, Op, NewState), \+ member(NewState, Seen)),
            NBs),
    mark(NBs, Seen, NewSeen),
    append(NBs, FR, NewFR),
    search(NewFR, Lim, WF, NewSeen, Answer).
search([], B, bound, _, Answer) :-
   B1 is B+1,
   starting(S0),
   search([d(S0,[])],B1, normal,[],Answer).

Попробуем применить эти процедуры для решения простых задач.

Волк, коза и капуста.

Фермеру надо перевезти волка, козу и капусту с левого берега на правый. При этом в лодку можно взять лишь одно из трех, но нельзя оставить без присмотра козу с капустой и козу с волком.

Разумеется, пространство состояний можно представлять по-разному. Вот один из возможных способов. Структура st(F,W,G,C) отражает местоположение фермера, волка, козы и капусты. Каждая компонента структуры принимает значение l, если соответствующий объект находится на левом берегу и r, если на правом. Возможные операторы - перемещение фермера или фермера вместе с каким либо грузом с одного берега на другой.

starting(st(l,l,l,l)).
solution(st(r,r,r,r)).
arc(S,Op,S1):- move(S,Op,S1), safe(S1).
move(st(X,W,G,C), alone(X,Y),  st(Y,W,G,C)) :- opposite(X,Y).
move(st(X,X,G,C), wolf(X,Y),   st(Y,Y,G,C)) :- opposite(X,Y).
move(st(X,W,X,C), goat(X,Y),   st(Y,W,Y,C)) :- opposite(X,Y).
move(st(X,W,G,X), cabbage(X,Y),st(Y,W,G,Y)) :- opposite(X,Y).
opposite(l,r).
opposite(r,l).
safe(st(X,_,X,_)).
safe(st(X,X,_,X)).

Любая из рассмотренных процедур, кроме самой первой легко находит решение.

?- solve(State, Answer).
State = st(r, r, r, r)
Answer = [g(l, r), a(r, l), w(l, r), g(r, l), c(l, r), a(r, l), g(l, r)]

Упражнение.

A) Три миссионера и три каннибала пытаются переправиться с левого берега реки на правый. Но лодка вмещает не более двух человек, а если на одном из берегов каннибалов окажется больше, чем миссионеров, последним грозит участь Кука.
B) Количество миссионеров и каннибалов возросло до пяти, но и вместительность лодки повысилась. Теперь можно перевозить сразу троих.

Упражнение.

A) Вариант предыдущей задачи. Три очень ревнивых мужа вместе со своими женами желают переправиться через реку. Лодка опять же вмещает не более двух человек, а ни один из мужей не может оставить свою жену без присмотра в обществе других мужчин.
B) То же самое, но теперь супружеских пар пять, зато посредине реки есть остров.

Упражнение.

Задачи на переливание - классика занимательной математики.
Имеется три сосуда, емкостью 1л, 0.5л и 0.3л. Литровый сосуд доверху наполнен ценной жидкостью, два других пусты. Переливая жидкость из одного сосуда в другой, вы можете отмерить определенное количество жидкости и выпить ее. За это вы должны точно распределить оставшуюся жидкость поровну по трем сосудам. Тривиальный вариант с выпиванием всей жидкости недопустим (ибо побьют).

Упражнение.

Пусть каждой дуге графа приписано некоторое положительное число - стоимость. Модифицируйте процедуру поиска в ширину так, чтобы она находила путь наименьшей стоимости. Для этого надо рассматривать вершины в порядке увеличения стоимости пути (а не длины пути как в BFS).
У вас получится поиск по критерию стоимости (Uniform-Cost Search, UCS).

Потренировавшись на кошках, перейдем к более сложным задачам.

Игра «N²-1».

Это обобщение знаменитой игры «15». Имеется поле размером NxN клеток, на котором расположено N²-1 пронумерованных фишек. Требуется выстроить фишки в определенном порядке.

Начнем с более простого варианта игры «8» и попытаемся найти оптимальную последовательность ходов, приводящих из исходного состояние в целевое.

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

starting(p(8,7,6, 5,4,3, 2,1,9)).
solution(p(1,2,3, 4,5,6, 7,8,9)).
arc(St, Op, NewSt) :-
    functor(NewSt, p, 9),
    arg(X,St,9),
    operator(Op, X, X1),
    arg(X, NewSt, D),
    arg(X1, St, D),
    arg(X1, NewSt, 9),
    update(9, St, NewSt).

update(0, _, _) :- !.
update(N, St, NewSt) :-
    arg(N, NewSt, D),
    (var(D) -> arg(N, St, D);true),
    M is N-1, update(M, St, NewSt).

operator(u, X, X1) :- X > 3, X1 is X-3.
operator(d, X, X1) :- X < 7, X1 is X+3.
operator(l, X, X1) :- X mod 3 =\= 1, X1 is X-1.
operator(r, X, X1) :- X mod 3 =\= 0, X1 is X+1.

Объединив эти определения с программой поиска в ширину, мы можем найти кратчайшее решение из 30 ходов. Но потребуется очень много терпения, чтобы дождаться ответа. На моем компьютере вычисления заняли 7 часов, хотя общее число состояний (9!/2 = 181440) не уж так и велико. SWI-Prolog - далеко не самая эффективная реализация, да и наше представление данных далеко от оптимального. Оптимизированная программа, написанная на языке более близком компьютеру, решает ту же задачу меньше чем за секунду. Но все ухищрения оказываются бессильными перед ростом сложности с возрастанием размера поля. Для классических пятнашек у нас просто не хватит памяти. Чтобы представить себе сложность задачи предположим, что мы в состоянии обрабатывать 10 миллионов вершин в секунду. Следующая таблица демонстрируетет потребность в  в памяти и во времени для решения задачи с помощью двух популярных методов.

Эвристический поиск.

Важный метод сокращения перебора - использование оценочных "эвристических" функций, позволяющих грубо оценить, насколько "хорошим" (или "плохим") является текущее состояние. Например, простая оценочная функция для программы игры в шахматы может представлять собой сумму ценности имеющихся на доске фигур (конечно, ценность фигур соперника должна быть отрицательной). В задачах поиска пути оценочная функция оценивает длину оптимального от данной вершины до целевой. Прокладывая путь на пересеченной местности, мы можем оценивать степень близости к цели как евклидово расстояние до нее sqrt(|XX₀|² + |YY₀|²) или как "манхэттенское расстояние" |XX₀|+|YY₀|, если мы путешествуем по Нью-Йорку.

При наличии "идеальной" оценочной функции необходимость в переборе отпадает - мы просто выбираем из всех соседних вершин оптимальную. Но если оценочная функция далека от идеала, такая "жадная" стратегия заведет нас в "яму" из которой не будет выхода. Чтобы гарантировать получение результата, необходимо обеспечить возможность отступления. Мы можем взять за основу процедуру поиска в глубину или в ширину и модифицировать ее так, чтобы она учитывала оценочную функцию. К описанию задачи добавляется предикат h(State,Val), вычисляющий эту функцию. Чтобы не перевычислять ее каждый раз, добавим значение оценки в структуру описывающую состояние. Причем поместим ее на первое место с тем, чтобы можно было использовать стандартные операции сравнения.

solve(State, Answer) :-
   starting(S),
   h(S,Val),
   search([d(Val,S,[])], [S], d(_,State,Path)),
   reverse(Path,Answer).

search([d(Val,State,Path)|_], _, d(Val,State,Path)) :-
    solution(State).
search([d(_,State,Path)|FR], Seen, Answer) :-
    findall(d(_,NewState,[Op|Path]),
            (arc(State,Op,NewState), \+ member(NewState, Seen)),
            NBs),
    checklist(hvalue, NBs),
    mark(NBs, Seen, NewSeen),
    join(NBs, FR, NewFR),
    search(NewFR, NewSeen, Answer).

mark([], Seen, Seen).
mark([d(_,State,_)|Sts], Seen, NewSeen) :-
    mark(Sts,[State|Seen],NewSeen).

Встроенный предикат checklist(Pred,List) применяет предикат ко всем элементам списка. Обычное его назначение - проверить, что все элементы удовлетворяют некоторому условию. Но в нашем случае мы не проверяем, а устанавливаем этот факт, присваивая значения оценки с помощью предиката hvalue.

hvalue(d(Val,State,_)) :- h(State,Val).

Предикат join определяет последовательность обработки вершин. Определив его соответствующим образом, получим эвристический поиск в глубину,

join(Ns,FR,FR1):- sort(Ns,Ns1), append(Ns1,FR,FR1).

или в ширину

join(Ns,FR,FR1):- sort(Ns,Ns1), merge(Ns1,FR,FR1).

Встроенная процедура merge выполняет слияние упорядоченных списков и является составной частью сортировки слиянием. Таким образом, это просто более эффективный способ выполнить

join(Ns,FR,FR1):- append(Ns,FR,NF), sort(NF,FR1).

Эти два метода известны под названиями "восхождение на гору" (hill climbing), и "сначала-лучший" (best-first search). Чтобы применить их к нашей головоломке, надо придумать подходящую оценочную функцию. Простейшая оценка - количество фишек не на своих местах оказывается слишком малоинформативной. Гораздо лучшие результаты дает сумма "манхэттенских" расстояний от каждой фишки до ее законного места.

h(B, HV) :-  sumdist(9,B, 0, HV).
sumdist(0, _, S, S) :- !.
sumdist(N, B, A, S) :-
    arg(N, B, P),
    mdist(N, P, D),
    A1 is A + D,
    M is N-1,
    sumdist(M, B, A1, S).
mdist(A, B, D) :-
  Ax is (A-1) mod 3, Ay is (A-1) // 3,
  Bx is (B-1) mod 3, By is (B-1) // 3,
  D is abs(Ax-Bx) +  abs(Ay-By) .

Теперь решение находится достаточно быстро (за несколько секунд) но оно далеко от оптимального. Поиск "сначала лучший" дает около 60 ходов, а "восхождение на гору" - свыше 100. Вообще, эвристический поиск в глубину слишком чувствителен к качеству оценочной функции и для нашей задачи непригоден.

Алгоритм A*

Чтобы получить наилучшее решение, мы должны не просто выбирать самое многообещающее продолжение, но учитывать и уже пройденный путь. Удобнее это делать, если есть некоторая простая связь между оценочной функцией и длиной пути. Но наша функция как раз имеет такую связь. Она дает оценку длины пути от данного состояния к целевому. Причем эта оценка всегда занижена. А это означает, что мы можем изменить критерий упорядочивания вершин и выбирать ту из них, для которой сумма длины уже пройденного пути и оценки пути, который предстоит пройти, минимальна. Все, что нам осталось сделать - изменить процедуру оценки.

hvalue(d(Val,State,Path)) :-
    h(State,Vs),
    length(Path,Vp),
    Val is Vs + Vp.

Новая версия программы находит действительно оптимальное решение за приемлемое время (за несколько минут). В литературе по искусственному интеллекту этот метод носит имя "Алгоритм A*". Иногда используют "взвешенный A*", когда какой либо составляющей придают больший вес.

hvalue(d(Val,State,Path)) :-
    h(State,Vs),
    length(Path,Vp),
    weight(Wh,Wp),
    Val is Wh*Vs + Wp*Vp.

В крайнем случае, когда Wh = 0 мы получим более громоздкую реализацию поиска в ширину. В другом крайнем случае, когда Wp = 0, получаем поиск "сначала лучший". Идея состоит в том, чтобы пожертвовать оптимальностью решения ради скорости. В нашем случае программа с weight(3,1) находит путь длины 42 за доли секунды, weight(2,1) дает путь близкий к оптимальному (34 хода) за 10 секунд, а weight(3,2) находит оптимальное решение примерно за минуту.

Алгоритм IDA*

Наличие оценочной функции позволяет организовать более интеллектуальное отсечение при поиске с ограничением на глубину. Мы можем отсекать ветви несколько раньше, как только оценка длины пути вместе с длиной уже пройденного пути превзойдет заданное ограничение. Поскольку эвристическая функция не переоценивает длину предстоящего пути, мы можем быть уверены, что отсекаемые ветви будут заведомо длиннее. Комбинируя эту идею с методом итерационного углубления, получим популярный "алгоритм IDA*" (Iterative Deepening A*). В отличие от DFID, ограничение на глубину при переходе к следующей итерации можно увеличивать большими шагами. Новое ограничение можно смело установить равным минимальной оценке всех отброшенных на предыдущей итерации вершин. Эту оценку мы будем передавать вместо флага.

solve(State, Answer) :-
    starting(Start),
    h(Start,Val),
    search([d(Val,Start,[])],Val,0,[Start],d(_,State,Path)),
    reverse(Path,Answer).
search([d(Val,State,Path)|_], _, _,  _, d(Val,State,Path)) :-
    solution(State).
search([d(Val,_,_)|FR], Lim,B, Seen, Answer) :-
    Val > Lim,!,
    adjust_bound(Val,B,B1),
    search(FR, Lim,B1, Seen, Answer).
search([d(_,State,Path)|FR], Lim,B, Seen, Answer) :-
    findall(d(_,NewState,[Op|Path]),
           (arc(State, Op, NewState), \+ member(NewState, Seen)),
            NBs),
    checklist(hvalue, NBs),
    mark(NBs, Seen, NewSeen),
    append(NBs, FR, NewFR),!,
    search(NewFR, Lim,B, NewSeen, Answer).
search([], _, B, _, Answer) :-
   B>0,
   starting(Start),
   h(Start,Val),
   search([d(Val,Start,[])],B,0,[Start],Answer).
adjust_bound(V,B,B) :- B>0,B =< V,!.
adjust_bound(V,B,V).

Упражнение.

Мы рассмотрели несколько упрощенные варианты эвристического поиска. "Настоящие" A* и IDA* находят путь наименьшей стоимости. Какие изменения необходимо внести в программы? Как должна изменится оценочная функция?

К сожалению, эвристический поиск не решает всех проблем. Используя IDA* с "манхэттенской" эвристикой можно найти оптимальное рещение для игры «15», но для игры «24» потребуется около 65000 лет. Это, конечно, меньше чем 10²³, но практически одно и то же. Используя  более совершенную оценочную функцию удалось решить и эту задачу [2]. Правда, решение в сложных случаях занимало по три месяца, а для вычисления оценочной функции требуется база на полмиллиарда соcтояний.

¹ Опять левосторонняя рекурсия. Это "ж-ж-ж" неспроста.

[1] Wirth N. Program Development by Stepwise Refinement. Communications of the ACM 14(4), 1971

[2] Korf, R.E., Taylor, L.A. Finding optimal solutions to the twenty-four puzzle, Proceedings of the Thirteenth National Conference onArtificial Intelligence, 1996

[ Содержание | 1 | 2 | 3 | 4 | 5 | 5.1 | 5.2 | 5.3 | 5.4 | 5.5 | 5.6 | 5.7 | 5.8 | 5.9 | 6 | 6.1 | 6.2 | 6.3 | 6.4 | 6.5 | 7 | 7.1 | Литература ]