Автор работы: Пользователь скрыл имя, 07 Июня 2014 в 16:59, курсовая работа
Процедурные (ИМПЕРАТИВНЫЕ) языки программирования требуют полного описания последовательности шагов (команд), которые нужно предпринять, чтобы решить задачу . К ним относятся СИ, ПАСКАЛЬ, АССЕМБЛЕР.
ПРОЛОГ — язык ДЕКЛАРАТИВНЫЙ. Он базируется на естественных для человека логических принципах. Нужно уметь составить формальное описание задачи, используя понятия объектов различных типов и отношений между ними. Иными словами, нужно описать все ФАКТЫ (ИСТИННЫЕ УТВЕРЖДЕНИЯ) и ПРАВИЛА (позволяющие ВЫВЕСТИ из уже имеющихся истинных утверждений новые), описывающие данную ситуацию. Затем пользователь задает вопрос или, пользуясь терминологией Пролога, задает ЦЕЛЬ.
member(H,[H|_]). % недетерминированная
member(X,[_|T]):- % процедура
member(X,T). % отыщет при возвратах
% всех соседок
/*
Конец программы
Процедура sosed обязана своей недетерминированностью процедуре member, входящей в ее состав. Эта процедура при возвратах будет пропускать первую вершину из списка соседок и искать соседку в хвосте списка.
Задача о поиске гамильтонова цикла на неориентированном графе — классическая задача теории графов и классическая 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).
/*
Конец программы
Будем искать пути на графе, ребрам которого приписаны веса, указанные в скобках (рис. 8.4).
рис. 8.4
Естественно возникает задача о поиске минимального пути от A до Z, если под длиной (стоимостью) пути понимать сумму весов входящих туда ребер. Такой граф будем хранить в виде утверждений базы данных — списков инцидентности graph1.
Процедура поска пути way, кроме нахождения пути, должна будет вычислять еще его стоимость. Поэтому к ней нужно будет добавить еще два аргумента — стоимость текушего пути (SW) и стоимость окончательного решения (S). Ей будет соответствовать описание
way1(uzl,list,integer,list,
и первый вызов из процедуры верхнего уровня show_min
way1(Z, [A], 0, Solution, S),
где 0 — стоимость начального пути и S — стоимость решения.
Аналогично, процедуры sosed1 и member1 должны иметь в качестве аргументов стоимость соответствующего ребра и список стоимостей ребер к вершинам — соседкам.
sosed1(uzl,uzl,integer)
member1(uzl,list,list1,
Процедура member1, выбирая очередную соседку из списка соседок, будет выбирать стоимость соответствующего ребра из списка стоимостей:
member1(Y,[Y|_],[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,
sosed1(uzl,uzl,integer)
member1(uzl,list,list1,
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)),
% не
существует пути стоимости
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) будет согласован.
Турбо-Пролог ориентирован на работу с реляционными БД. Можно указать следующее соответствие понятий:
База данных Турбо-Пролога |
Реляционная база данных |
предикат БД |
Отношение |
объект(аргумент) |
Атрибут |
отдельное утверждение |
Элемент отношения |
количество утверждений |
Мощность |
Пусть в разделе clauses имеется следующий факт:
member_party(”Вольфович”,50,
Предикат member_party имеет четыре аргумента: партийное имя, возраст, членский взнос (в рублях), отметка об уплате.
Поскольку введенная ранее терминология Турбо-Пролога прилагается к реляционным базам данных, то все понятия приобретают новое значение:
набор атрибутов Name,Age,Pay и Payment называется реляционной схемой отношения member_party, где арность отношения равна четырем и мощность отношения равна одному.
Совокупность утверждений предиката member_party составляет СТАТИЧЕСКУЮ БД, так как эти утверждения являются частью программного кода и не могут быть изменены во время выполнения программы. Также в Турбо-Прологе имеются специальные средства и для организации динамических баз данных, и для работы с внешними базами данных, расположенными на жестком диске. Рассмотрим подробно способы организации динамических БД.
Раздел database в Турбо-Прологе предназначен для описания предикатов базы данных. Все различные утверждения этих предикатов составляют динамическую базу данных Турбо-Пролога.
database
dmember_party(name,age,pay,
Такая база данных располагается в оперативной памяти, и во время работы программы из нее можно удалять любые содержащиеся в ней утверждения и добавлять новые. В этом состоит ее отличие от статической базы данных, где утверждения вписаны в программный код раз и навсегда, и не могут быть изменены. Если БД состоит из статической и динамической части, то предикаты динамической БД имеют другое имя, но ту же самую форму представления данных.
Все отличие предиката dmember_party по сравнению с member_party заключается лишь в одной лишней букве терма. Добавление латинской буквы d — обычный способ различать предикаты динамической и статической баз данных.
domains
name,payment=symbol
age,rubel=integer
pay=integer
database
dmember_party(name,age,pay,
predicates
member_party(name,age,pay,
В ДИНАМИЧЕСКОЙ БАЗЕ ДАННЫХ МОГУТ СОДЕРЖАТЬСЯ ТОЛЬКО ФАКТЫ (НЕ ПРАВИЛА).
В этом состоит отличие Турбо-Пролога от других реализаций языка Пролог.
Утверждения статической БД могут быть считаны в динамическую БД сразу после активизации программы (для этой цели используются предикаты asserta и assertz, которые будут рассмотрены ниже).
Другая важная особенность динамической базы данных состоит в том, что такая база может быть записана на диск, а также считана с диска в оперативную память (встроенные предикаты save и consult).
В Турбо-Прологе имеются специальные встроенные предикаты для работы с динамической базой данных. Таковыми являются asserta, assertz, retract, retracrall, save, consult.
Предикаты asserta, assertz и retract позволяют занести факт в заданное место динамической БД и удалить из нее уже имеющийся факт.
Предикат asserta заносит новый факт в базу данных, располагающуюся в оперативной памяти компьютера (резидентная БД). Новый факт помещается перед всеми уже внесенными утверждениями данного предиката. Этот предикат имеет такой синтаксис:
asserta(Clause)
Таким образом, чтобы поместить в БД утверждение о новом члене партии перед уже имеющимся там утверждением (стоящим в настоящий момент в базе данных на первом месте), необходимо следующее предикатное выражение:
asserta(member_party(”Кузьмич”
Предикат assertz так же, как и asserta, заносит новые утверждения в базу данных. Однако он помещает новое утверждение за всеми уже имеющимися в базе утверждениями того же предиката. Синтаксис предиката столь же прост:
assertz(Clause)
Предикат retract удаляет утверждение из динамической БД. Его синтаксис таков:
retract(Existing_clause)
Если в базе данных НЕТ УТВЕРЖДЕНИЯ, которое вы пытаетесь удалить, то retract ОКОНЧИТСЯ НЕУДАЧЕЙ.
Предположим, что вы хотите удалить из базы данных второе утверждение. Для этого необходимо написать выражение:
retract(member_party(”Кузьмич”
Если вы хотите удалить из БД всех членов, не уплативших взносы, то можно воспользоваться предикатом:
retractall(member_party(_,_,_,
Предикат retractall ВСЕГДА УСПЕШЕН, даже при попытке удалить что-то из абсолютно пустой БД.
Предикат retract имеет важную особенность — он ПЕРЕДОКАЗЫВАЕТСЯ ПРИ ВОЗВРАТАХ (в отличие от asserta, assertz и retractall). Поэтому при применении предиката retract существует опасность непредсказуемого изменения программы. В дальнейшем будут рассмотрены приемы, позволяющие решить эту проблему.
Информация о работе Основы программирования на языке Turbo Prolog