Основы программирования на языке Turbo Prolog

Идея следующая:

1. Сравниваются головы H1 и H2 исходных списков. Меньший из этих элементов становится головой целевого списка S.

2. Остатки исходных списков с помощью concsort соединяются в хвост целевого.

concsort([H1|T1],[H2|T2],[H1|T]):-

   H1<=H2,!,

   concsort(T1,[H2|T2],T).

concsort([H1|T1],[H2|T2],[H2|T]):-

   concsort([H1|T1],T2,T).

Так как мы заранее не знаем, какой из списков L1, L2 кончится раньше, то необходимо иметь два граничных условия:

concsort([],L,L).

concsort(L,[],L).

/* Программа 7.3 «очень быстрая сортировка».  */

domains

   list=integer*

 

predicates

% очень  быстрая сортировка

   supersort1(list,list)

% разделение  на два примерно равных списка

   div2(list,list,list)

% соединение  двух отсортированных списков

   concsort(list,list,list)

 

goal

   supersort1([1,7,95,1,9,3],L),write(L),nl.   

 

clauses

 

supersort1([],[]).

supersort1([X],[X]).

supersort1(L,S):-

    div2(L,L1,L2),

    supersort1(L1,S1),

    supersort1(L2,S2),

    concsort(S1,S2,S).

 

div2([],[],[]).

div2([X],[X],[]).

div2([X,Y|L],[X|L1],[Y|L2]):-

     div2(L,L1,L2).

 

concsort([],L,L).

concsort(L,[],L).

concsort([H1|T1],[H2|T2],[H1|T]):-

    H1<=H2,!,

    concsort(T1,[H2|T2],T).

concsort([H1|T1],[H2|T2],[H2|T]):-

    concsort([H1|T1],T2,T).

/*        Конец программы       */

Упражнение 7.1.

Напишите сортировку методом «пузырька», согласно следующему алгоритму:

% рекурсивное  правило bubble:

1. Переставляем  первую неупорядоченную пару  элементов.

2. Сортируем  пузырьком получившийся переставленный список.

% граничное  условие bubble:

3. Если  такой пары нет (процедура перестановки change дала отказ), значит, исходный список уже отсортирован.

Перестановку двух элементов списка осуществит рекурсивная процедура change:

1. Если  первые два элемента списка неупорядочены, то переставляем их.

2. Иначе  пропускаем первый элемент и  вызываем change для хвоста списка.

5. КОМПОНОВКА ДАННЫХ В СПИСОК

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

Предописание встроенного предиката findall выглядит следующим образом:

fidall(Variable_name,Predicate_expression,List_name)

Variable_name обозначает здесь объект входного предиката Predicate_expression, а List_name является именем переменной выходного списка. Переменная должна относиться к домену списков, объявленному в разделе domains.

Для пояснения только что сказанного, рассмотрим предикат male из программы 2.1 «РОДСТВЕННИКИ» главы 2.

Соберем в список всех мужчин рассматриваемой семьи. Вначале в разделе domains опишем соответствующий список:

domains

   name = symbol

   list = symbol*

и составим этот список Mlist с помощью предиката findall:

goal

   findall(X, male(X), Mlist), write(Mlist).

Предикат findall может работать не только с фактами, но и с правилами. Соберем в список Slist всех сестер:

goal

   findall(X, sister(X,_), Slist), write(Slist).

или всех сестер и братьев beth:

goal

   findall(X,sister(beth,X),Blist), write(Blist).

Упражнение 7.2.

Собирите в список всех родственников бэт и удалите повторяющиеся элементы. Для удаления из списка кратностей запрограммируйте процедуру delcrat следующему алгоритму:

1. Пустой  список — список без кратностей.

2. Если  голова списка H принадлежит хвосту списка T (member(H,T)), то вызываем delcrat для хвоста списка.

3. Если  голова списка H не принадлежит хвосту списка T, то H является головой целевого списка, а хвост целевого списка T’ получается после удаления кратностей из хвоста T: delcrat(T,T’).

ГЛАВА 8. ПРОГРАММИРОВАНИЕ АЛГОРИТМОВ С ВОЗВРАТОМ. ПРЕДСТАВЛЕНИЕ ГРАФОВ 
В TURBO PROLOG

1. ЗАДАЧА О ВЕСАХ

Рассмотрим задачу о наборе заданного веса с помощью имеющегося разновеса всеми возможными способами. Отдельно рассмотрим два случая:

1) отсутствие  в разновесе кратных гирь, то  есть гирь с одинаковым весом;

2) наличие в разновесе кратных гирь.

РАЗЛИЧНЫМИ будем считать наборы с точностью до перестановки гирь. Для этого генерировать наборы будем в ЛЕКСИКОГРАФИЧЕСКОМ порядке (вернее, в порядке обратном лексикографическому), т. е. вначале найдем все наборы, содержащие самую тяжелую гирю, затем наборы, содержащие вторую по тяжести гирю и.т.д. Внутри наборов гири будут упорядочены таким же образом в порядке убывания.

Алгоритм с возвратом будет генерировать наборы следующим образом:

если очередная гиря G меньше текущего веса VES, который нужно набрать, то

— переносим гирю G из разновеса в решение;

— пытаемся набрать уменьшенный вес VES1 (VES-G) гирями весом не более G.

Если для VES1 в разновесе нет подходящей гири или VES1=0 (нашли решение), то происходит ВОЗВРАТ:

— последняя добавленная гиря G из решения возвращается в разновес;

— текущим весом становится VES (VES1+G), а текущей гирей — гиря весом G-1. Если такой гири в разновесе нет, то берем гирю G-2 и т.д.

Различие в работе алгоритма для случая кратных и однократных гирь заключается в следующем:

1) в случае  кратных гирь после добавления G к решению уменьшенный вес набирается гирями веса £ G,

2) в случае  однократных гирь уменьшенный  вес набирается гирями веса <G (начиная с G-1).

При возврате (после генерации всех наборов веса VES, начинающихся с гири G) и в первом, и во втором случае дальнейшие разложения веса VES строятся, начиная с гири G-1. Благодаря этому, в случае кратных гирь мы избегаем повторяющихся наборов.

Для разновеса [5,4,3,2,1,1,1] алгоритм с возвратом построит следующие решения:

[5] [4,1] [3,2] [3,1,1 ] [2,1,1,1]

Дерево поиска, которое строит алгоритм с возвратом, изображено на рис. 8.1.

рис. 8.1

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

Идея поиска:

1. Нулевому  весу соответствует решение — пустой список.

2. При  наборе непустого веса берем  первую гирю из текущего разновеса. Хвост разновеса становится текущим  разновесом, а уменьшенный вес — текущим весом.

3. При возврате (или закончились гири, или первая гиря разновеса оказалась недопустимой) первую гирю разновеса убираем и набираем текущий вес с помощью хвоста разновеса.

Таким образом, для непустого веса имеются два неисключающих друг друга правила:

или берем первую гирю, или пропускаем ее.

Благодаря этим трем правилам, мы получим всевозможные наборы веса без повторений.

/* Программа 8.1 «ВЕСЫ». Назначение:     */

/* демонстрация  алгоритма с возвратом    */

domains

   list=integer*

 

predicates           

   solve1(list,integer,list) % однократные гири

 

goal

   write("Вес ",5," можно набрать: "),nl,

   solve1([5,4,3,2,1], 5, S),

   write(S),nl,fail.

 

clauses

 

/*** Правила  однократной процедуры solve1 ***/

   solve1(_,0,[]):-!.

   solve1([H|T],Ves,[H|T1]):-

      H <= Ves,

      Ves1=Ves-H,

      solve1(T,Ves1,T1). 

   solve1([_|T],Ves,S):-

      solve1(T,Ves,S).         

/*   Конец программы                      */

Если убрать ! из правила для нулевого веса, в последнее правило нужно добавить условие Ves>0. Иначе после печати найденного решения произойдет возврат на последнее правило solve1 и это решение будет повторено столько раз, сколько гирь в хвосте T.

Рассмотрим случай кратных гирь.

Согласно алгоритму, при возврате должен происходить сдвиг с гири G на гирю G-1(или меньшую), иначе мы будем получать повторяющиеся решения (например, для трех гирь 1 решение [4,1] будет повторено три раза). В первом случае это происходило автоматически, когда при возврате пропускалась голова разновеса. Если в разновесе будут стоять подряд повторяющиеся гири, то, пропустив голову, мы можем попасть на гирю такого же веса.

Будем хранить разновес в виде двух списков:

в первом — различные веса, имеющиеся в разновесе,

во втором — их кратности.

Так, разновес [5,4,3,2,2,1,1,1] будет представлен в виде двух списков: [5,4,3,2,1] и [1,1,1,2,3].

Правило выбора первой гири преобразуется в правило для однократной гири и правило для кратной гири.

/* Программа 8.2 «КРАТНЫЕ ВЕСЫ». Назначение: */

/* демонстрация  алгоритма с возвратом        */

 

domains

   list=integer*

 

predicates           

   solve(list,list,integer,list) % кратные гири

  

goal

   write("Вес ",5," можно набрать: "),nl,

   solve([5,4,3,2,1],[2,1,1,2,3], 5, S),

   write(S),nl,fail.

  % 1-й список solve содержит веса гирь.

  % 2-й список solve содержит кратности  гирь.

  % 3-й список solve содержит разложение  веса.

 

clauses

 

/*** Правила  кратной процедуры solve   ***/      

   solve(_,_,0,[]):-!.

    % 1-я альтернатива: набрали нужный  вес.

    % Переход на нижние правила solve  запрещен.

    % Возврат на цель solve верхнего уровня.

    % ! можно заменить условием Ves>0 в последнем  
        правиле.

 

   solve([H|T],[1|CT],Ves,[H|T1]):-

      H <= Ves,

      Ves1=Ves-H,

      solve(T,CT,Ves1,T1).

    % 1-я альтернатива: однократная гиря H.

 

   solve([H|T],[N|CT],Ves,[H|T1]):-

      N>1,

      N1=N-1,

      H <= Ves,

      Ves1=Ves-H,

      solve([H|T],[N1|CT],Ves1,T1).

     % 2-я альтернатива: N-кратная гиря H. 

     % Набор Ves1 начинается N-1-кратной H.

 

  solve([_|T],[_|T1],Ves,S):-

     solve(T,T1,Ves,S).

     % Возврат для 1 и 2 альтернатив:

     % H пропускается, берется следующая гиря.

/*         Конец программы             */

Из приведенных примеров видно, что ПРОГРАММИСТУ НЕ НУЖНО СЛЕДИТЬ ЗА ВОССТАНОВЛЕНИЕМ ИСХОДНОЙ СИТУАЦИИ ПРИ ВОЗВРАТЕ:

удаление гири из решения и возвращение ее в разновес, восстановление текущего веса — это при возврате АВТОМАТИЧЕСКИ ДЕЛАЕТ САМА СИСТЕМА. Для того чтобы система могла осуществить возврат, правило solve было сделано НЕДЕТЕРМИНИРОВАННЫМ (или берем первую гирю, или пропускаем ее).

2. ПРЕДСТАВЛЕНИЕ ГРАФОВ В TURBO PROLOG

Графы в Прологе могут представляться многими способами. Рассмотрим некоторые из них на модельном графе (рис. 8.2).

рис. 8.2

Первый способ — перечислить ребра графа в виде утверждений базы данных (для неориентированного графа каждое ребро повторяется дважды):

after(1,2). after(2,1). after(1,3). after(3,1).

after(1,4). after(4,1). after(2,3). after(3,2).

after(2,5). after(5,2). after(3,4). after(4,3).

after(5,4). after(4,5).

Однако, для многих алгоритмов более предпочтительным представлением являются СПИСКИ ИНЦИДЕНТНОСТИ (когда к каждой вершине прицеплен список соседок — смежных с ней вершин):

graph([1,2,3,4]).

graph([2,3,1,5]).

graph([3,1,2,4]).

graph([4,1,3,5]).

graph([5,2,4]).

Голова списка — сама вершина, хвост — список ее соседок.

Граф можно хранить в виде динамической структуры — списка списков — и передавать ее в качестве аргумента из процедуры в процедуру:

domains

   uzl=integer

   list=uzl*

   llist=list*

 

<.............>

 

goal

   Graph =   [[1,2,3,4],[2,1,3,5],[3,1,2,4],[4,1,3,5],[5,2,4] ], <....>.

Для «нагруженных» графов, ребрам которых приписаны веса (или стоимости) нужно произвести некоторые изменения:

у предиката after появится третий аргумент — вес ребра:

after1(1,2,3).

after1(2,1,3).  /* вес ребра 1-2 равен 3*/;

у предиката graph появится второй аргумент — список весов соответствующих ребер:

graph1([5,2,4], [5,1]).

/* вес  ребра 5-2 равен 5, ребра 5-4 равен 1  */.

К динамическому списку списков, представляющему граф, нужно добавить еще один список списков — с весами соответствующих ребер.

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

num_reb(7).

num_uzl(5).

3. ПОИСК ПУТИ НА НЕОРИЕНТИРОВАННОМ  ГРАФЕ

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

[Z|Solution]

Алгоритм с возвратом будет искать пути следующим образом:

— начальный путь будет состоять из единственной вершины [A];

— пусть текущий путь оборвался на вершине X. Чтобы продолжить текущий путь на один шаг, найдем соседку вершины X — вершину Y. Если она не принадлежит текущему пути, продолжим его до вершины Y:

[Y,X|Was] /* Was — текущий путь до вершины X */;

— если из очередной вершины Y попали в Z (нашли решение) или в тупик (у вершины Y нет допустимых соседок), то производим возврат:

вместо вершины Y находим другую допустимую соседку Y’ вершины X и продолжаем путь из Y’.

Дерево поиска, построенное алгоритмом с возвратом, показано на рис. 8.3.

рис. 8.3

Составим процедуру поиска пути way.Она будет иметь три аргумента:

вершина — конец пути; текущий (частичный) путь; решение (полный путь)

и состоять из двух правил: правила окончания рекурсии, когда путь заканчивается вершиной Z:

way(Z, [Z|Was], [Z|Was]).

и правила продолжения пути на один шаг с вызовом дальнейшей рекурсии

way(Z, [X|Was], Sol):-

   sosed(X,Y),

   not(member(Y,Was)),  

   way(Z, [Y,X|Was], Sol).

Все возможные пути будут получаться из-за недетерминированности процедуры sosed, которая при возвратах будет подставлять на место Y поочередно всех соседок вершины X.

/* Программа 8.3 «Поиск всех путей от A до Z»  */

 

domains

    uzl=integer

    list=uzl*

 

predicates

 

    graph(list)

    show_way

    way(uzl,list,list)

    sosed(uzl,uzl)  

    member(uzl,list)

  

goal

    show_way.

  

clauses

 

   num_uzl(5).

 

    graph([1,2,3,4]).

    graph([2,1,3,5]).

    graph([3,1,2,4]) .

    graph([4,1,3,5]).

    graph([5,2,4]).

 

    show_way:-

       write("Начало пути "), readint(A),

       write("Конец пути "), readint(Z),

       way(Z, [A], Solution), write(Solution),

       nl, fail.

 

    % путь окончился в Z

    way(Z, [Z|Was], [Z|Was]).

    way(Z, [X|Was], Sol):-

       sosed(X,Y),

       % Y не содержится в пути

       not(member(Y,Was)), 

       % продолжили путь до Y

       way(Z, [Y,X|Was], Sol).

   

    sosed(X,Y):-

       graph([X|T]),  % T — список соседок X

       % Y — принадлежит списку соседок X

       member(Y,T).