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

 

    member(H,[H|_]).   % недетерминированная

    member(X,[_|T]):-  % процедура

       member(X,T).    % отыщет при возвратах

                       % всех соседок 

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

Процедура sosed обязана своей недетерминированностью процедуре member, входящей в ее состав. Эта процедура при возвратах будет пропускать первую вершину из списка соседок и искать соседку в хвосте списка.

4. ПОИСК ГАМИЛЬТОНОВЫХ ЦИКЛОВ

Задача о поиске гамильтонова цикла на неориентированном графе — классическая задача теории графов и классическая NP-полная задача с точки зрения классификации задач по степени их вычислительной сложности.

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

Единственный недостаток такой программы то, что каждый цикл будет находиться и печататься дважды. Например, цикл 1-2-5-4-3-1 будет найден как замыкание пути 1-2-5-4-3 и при замыкании пути 1-3-4-5-2. Чтобы существенно не усложнять программу, смиримся с двойной печатью каждого цикла.

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

gami(A, Solution):-

  % путь выходит из A и заканчивается  в любой вершине

   way(_, [A], Solution),

   % замкнется ли он в гамильтонов цикл ?

   full_cycle(A, Solution).

/*     Программа 9.4 «Гамильтоновы  циклы» */

domains

   uzl=integer

   list=uzl*

 

predicates

 

   show_cycle

   num_uzl(integer)

   graph(list)

   gami(uzl,list)

   way(uzl,list,list)

   full_cycle(integer,list)

   full(integer,list)

   sosed(uzl,uzl)  

   member(uzl,list)

  

goal

   show_cycle.

  

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_cycle:-

      write("Начало цикла "),readint(A),nl,

      gami(A, Solution), write(Solution),

      nl, fail.

 

 gami(A, Solution):-

    way(_, [A], Solution),

    full_cycle(A, Solution).

       

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

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

    sosed(X,Y),

    not(member(Y,Was1)),

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

         

full_cycle(A, [H|S]):-

    sosed(H, A),!, % путь замыкается в цикл,

    num_uzl(N),    % N — число вершин графа,   

    full(N, [H|S]).% в цикле все вершины графа

 

full(0,[]):-!.      % в пустом пути 0 вершин

full(N, [_|T]):-    % в цикле ровно N вершин

   N1=N-1,

   full(N1, T).

              

sosed(X,Y):-

   graph([X|T]),

   member(Y,T).  

 

member(H,[H|_]).     

member(X,[_|T]):-    

   member(X,T).   

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

5. ПОИСК ПУТИ МИНИМАЛЬНОЙ СТОИМОСТИ

Будем искать пути на графе, ребрам которого приписаны веса, указанные в скобках (рис. 8.4).

рис. 8.4

Естественно возникает задача о поиске минимального пути от A до Z, если под длиной (стоимостью) пути понимать сумму весов входящих туда ребер. Такой граф будем хранить в виде утверждений базы данных — списков инцидентности graph1.

Процедура поска пути way, кроме нахождения пути, должна будет вычислять еще его стоимость. Поэтому к ней нужно будет добавить еще два аргумента — стоимость текушего пути (SW) и стоимость окончательного решения (S). Ей будет соответствовать описание

way1(uzl,list,integer,list,integer)

и первый вызов из процедуры верхнего уровня show_min

way1(Z, [A], 0, Solution, S),

где 0 — стоимость начального пути и S — стоимость решения.

Аналогично, процедуры sosed1 и member1 должны иметь в качестве аргументов стоимость соответствующего ребра и список стоимостей ребер к вершинам — соседкам.

sosed1(uzl,uzl,integer)

member1(uzl,list,list1,integer)

Процедура member1, выбирая очередную соседку из списка соседок, будет выбирать стоимость соответствующего ребра из списка стоимостей:

member1(Y,[Y|_],[Stoim|_],Stoim)

Затем они (соседка Y и стоимость Stoim) будут передаваться в процедуру sosed1. Процедура way1, получив их из процедуры sosed1, после соответствующей проверки, добавит Y к текущему пути, а вес ребра — к текущей стоимости.

way1(Z, [X|Was],SW, Sol,S):-

    sosed1(X,Y,St),   % St — вес ребра (X-Y).

    not(member(Y,Was)),  

    SW1=SW+St,

    way1(Z, [Y,X|Was],SW1, Sol,S).  

SW1 — стоимость текущего пути, S — стоимость решения.

Нетрудно, немного изменив программу поиска пути, находить всевозможные пути от A до Z с их стоимостями. Но нам нужен один-единственный путь — путь минимальной стоимости.

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

Реализуем декларативную идею поиска минимального пути. Словами ее можно выразить так:

«мы сгенерировали путь, который будет минимальным, потому что невозможно сгенерировать путь меньшей стоимости». На Прологе это можно записать примерно так:

show_min:- 

   way1(Z, [A], 0, Solution, MinS),

   not(way1(Z, [A], 0, _, S),

   S < MinS).   

Анонимная переменная стоит на месте НЕСУЩЕСТВУЮЩЕГО пути, вид которого нас не интересует.

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

вначале way1 найдет некий путь Solution. Затем правило not будет генерировать пути и проверять, что их стоимость больше стоимости MinS. Если найдется путь меньшей стоимости, not даст отказ, и произойдет возврат к way1, которая сгенерирует новый путь Solution и т.д.

Наконец, будет найден такой путь Solution, для которого not сгенерирует ВСЕ пути, но ни один не окажется меньше. not даст успех, и все правило show_min окончится успехом.

В случае большого количество путей (например, для полного графа) выполнение этого правила приведет к КОМБИНАТОРНОМУ ВЗРЫВУ. В следующей главе будет показано, как существенно уменьшить число переборов.

Поскольку встроенный предикат not не может иметь в качестве аргумента более одного предиката, конъюнкцию way1(Z, [A], 0, _, S), S < MinS

нужно записать в виде отдельного правила:

min_way(Z, A, MinS):-

   way1(Z, [A], 0, _, S),

   S < MinS.

/* Программа 8.5 «Поиск пути от A до Z        */

/* минимальной стоимости»                     */

domains

 

   uzl=integer

   list=uzl*

   list1=integer*

 

predicates

 

   num_uzl(integer)

   graph1(list,list1)

   show_way1

   min_way(uzl,uzl,integer)

   show_min

   way1(uzl,list,integer,list,integer)

   sosed1(uzl,uzl,integer)  

   member1(uzl,list,list1,integer)

   member(uzl,list)

 

goal

   show_min.% показать путь минимальной  стоимости

  

clauses

 

   num_uzl(5). % число вершин графа

 

   graph1([1,2,3,4],[3,0,2]).

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

   graph1([3,1,2,4],[0,4,0]).

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

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

              

   show_min:-

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

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

      way1(Z, [A], 0, Solution, MinS),

      not(min_way(Z, A, MinS)),

% не  существует пути стоимости меньшей, чем MinS

      write("MIN ", Solution," ст.= ", MinS).

  

   min_way(Z, A, MinS):-

      way1(Z, [A], 0, _, S),

      S < MinS.

% находим  путь стоимости S меньшей, чем MinS.

 

   way1(Z, [Z|Was],S, [Z|Was],S).

   way1(Z, [X|Was],SW, Sol,S):-

       sosed1(X,Y,St),  % St — вес ребра (X-Y).

       not(member(Y,Was)),

       SW1=SW+St,

       way1(Z, [Y,X|Was],SW1, Sol,S).

         

   sosed1(X, Y, St):-

      graph1([X|T], LS),     

      member1(Y, T, LS, St). 

          

  member1(H,[H|_],[S|_],S).   

  member1(X,[_|T],[_|ST],S):- 

     member1(X,T,ST,S).

% детерминированная  процедура 

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

member(H,[H|_]):-!.

member(X,[_|T]):-

    member(X,T).

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

В заключение рассмотрим более подробно свойства предиката not. Этот предикат определяется следующим образом:

not(P):-

   P,!,fail.

not(P):- true.

Пусть P — детерминированный предикат. Если P истинен, то комбинация ! и fail вызывают отказ цели not(P), без возможности ее повторного передоказательства. Если P ложен, то второе правило согласует not(P) как истину.

В нашей программе P(min_way) недетерминированный предикат.

Если P истинен, то аналогично детерминированному P not(P) дает отказ.

Если P ложен, то прежде, чем произойдет переход на второе правило и согласование not(P), система переберет всевозможные способы передоказательства P (в нашей программе min_way сгенерирует всевозможные пути и сравнит их стоимости с минимальной). Если ВСЕ эти решения окажутся ложными, то только тогда not(P) будет согласован.

ГЛАВА 9. ДИНАМИЧЕСКАЯ БАЗА ДАННЫХ

1. ТУРБО-ПРОЛОГ И РЕЛЯЦИОННЫЕ БАЗЫ  ДАННЫХ

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

База данных Турбо-Пролога	Реляционная база данных
предикат БД	Отношение
объект(аргумент)	Атрибут
отдельное утверждение	Элемент отношения
количество утверждений	Мощность

Пусть в разделе clauses имеется следующий факт:

member_party(”Вольфович”,50,100,”n”).

Предикат member_party имеет четыре аргумента: партийное имя, возраст, членский взнос (в рублях), отметка об уплате.

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

набор атрибутов Name,Age,Pay и Payment называется реляционной схемой отношения member_party, где арность отношения равна четырем и мощность отношения равна одному.

Совокупность утверждений предиката member_party составляет СТАТИЧЕСКУЮ БД, так как эти утверждения являются частью программного кода и не могут быть изменены во время выполнения программы. Также в Турбо-Прологе имеются специальные средства и для организации динамических баз данных, и для работы с внешними базами данных, расположенными на жестком диске. Рассмотрим подробно способы организации динамических БД.

2. ОПИСАНИЕ ПРЕДИКАТОВ ДИНАМИЧЕСКИХ  БД

Раздел database в Турбо-Прологе предназначен для описания предикатов базы данных. Все различные утверждения этих предикатов составляют динамическую базу данных Турбо-Пролога.

database

dmember_party(name,age,pay,payment)

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

Все отличие предиката dmember_party по сравнению с member_party заключается лишь в одной лишней букве терма. Добавление латинской буквы d — обычный способ различать предикаты динамической и статической баз данных.

domains

   name,payment=symbol

   age,rubel=integer

   pay=integer

 

database

   dmember_party(name,age,pay,payment)

 

predicates

   member_party(name,age,pay,payment)

В ДИНАМИЧЕСКОЙ БАЗЕ ДАННЫХ МОГУТ СОДЕРЖАТЬСЯ ТОЛЬКО ФАКТЫ (НЕ ПРАВИЛА).

В этом состоит отличие Турбо-Пролога от других реализаций языка Пролог.

Утверждения статической БД могут быть считаны в динамическую БД сразу после активизации программы (для этой цели используются предикаты asserta и assertz, которые будут рассмотрены ниже).

Другая важная особенность динамической базы данных состоит в том, что такая база может быть записана на диск, а также считана с диска в оперативную память (встроенные предикаты save и consult).

3. ВСТРОЕННЫЕ ПРЕДИКАТЫ ASSERTA, ASSERTZ, RETRACT, RETRACTALL, SAVE, CONSULT

В Турбо-Прологе имеются специальные встроенные предикаты для работы с динамической базой данных. Таковыми являются asserta, assertz, retract, retracrall, save, consult.

Предикаты asserta, assertz и retract позволяют занести факт в заданное место динамической БД и удалить из нее уже имеющийся факт.

Предикат asserta заносит новый факт в базу данных, располагающуюся в оперативной памяти компьютера (резидентная БД). Новый факт помещается перед всеми уже внесенными утверждениями данного предиката. Этот предикат имеет такой синтаксис:

asserta(Clause)

Таким образом, чтобы поместить в БД утверждение о новом члене партии перед уже имеющимся там утверждением (стоящим в настоящий момент в базе данных на первом месте), необходимо следующее предикатное выражение:

asserta(member_party(”Кузьмич”,65,10,”y”))

Предикат assertz так же, как и asserta, заносит новые утверждения в базу данных. Однако он помещает новое утверждение за всеми уже имеющимися в базе утверждениями того же предиката. Синтаксис предиката столь же прост:

assertz(Clause)

Предикат retract удаляет утверждение из динамической БД. Его синтаксис таков:

retract(Existing_clause)

Если в базе данных НЕТ УТВЕРЖДЕНИЯ, которое вы пытаетесь удалить, то retract ОКОНЧИТСЯ НЕУДАЧЕЙ.

Предположим, что вы хотите удалить из базы данных второе утверждение. Для этого необходимо написать выражение:

retract(member_party(”Кузьмич”, 65,10,”y”))

Если вы хотите удалить из БД всех членов, не уплативших взносы, то можно воспользоваться предикатом:

retractall(member_party(_,_,_,”n”))

Предикат retractall ВСЕГДА УСПЕШЕН, даже при попытке удалить что-то из абсолютно пустой БД.

Предикат retract имеет важную особенность — он ПЕРЕДОКАЗЫВАЕТСЯ ПРИ ВОЗВРАТАХ (в отличие от asserta, assertz и retractall). Поэтому при применении предиката retract существует опасность непредсказуемого изменения программы. В дальнейшем будут рассмотрены приемы, позволяющие решить эту проблему.