Материал: Волченков Логическое программирование язык пролог 2015

этой структуры – переменная Bk, обозначающая k-е «распознанное» тело, 2-й аргумент – тип грани.

С указанной задачей успешно справляется следующая программа (код 10.2):

К этой программе должны быть присоединены так называемые правила распознавания, содержащие семантику (свойства) рёбер:

Код 10.3

vr(левая_грань:B, правая_грань:B, выпуклое_ребро).

vr(правая_грань:B1, левая_грань:B2, вогнутое_ребро). vr(правая_грань:B, X, down_ребро).

vr(X, левая_грань:B, up_ребро).

pr(горизонт_грань:B, правая_грань:B, выпуклое_ребро).

pr(правая_грань:B1, горизонт_грань:B2, вогнутое_ребро). pr(X, горизонт_грань:B, up_ребро).

pr(правая_грань:B, X, down_ребро).

nr(левая_грань:B, горизонт_грань:B, выпуклое_ребро).

nr(горизонт_грань:B1, левая_грань:B2, вогнутое_ребро). nr(горизонт_грань:B, X, down_ребро).

nr(X, левая_грань:B, up_ребро).

141

Распознавание реализуется путём сопоставления образцов,

представленных кодом 10.3, с целями C, находящимися в правой части правила: solution(A) :- C.

На первом шаге распознавания цель pr(фон, R2, E1) успешно сопоставляется с образцом pr(X, горизонт_грань:B, up_ребро). Результат сопоставления:

R2 = горизонт_грань:B,

X = фон,

E1 = up_ребро.

На втором шаге цель nr(горизонт_грань:B, фон, E2) успешно сопоставляется с образцом nr(горизонт_грань:B, X, down_ребро). Результат сопоставления:

X = фон,

E2 = down_ребро.

И так далее.

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

Довольно быстро (так как дедукция реализуется только «на уровне сопоставления образцов») указанный процесс приводит к

результату, который был представлен ранее: R1 = B1 : левая_грань,

R2 = B1 : горизонт_грань,

…

R10 = B2 : горизонт_грань.

Для большей привлекательности ввода и вывода данных код 10.2 можно модернизировать:

patrec :-

write('Введите имя файла с правилами для распознавания'), nl, write(' (ai_patrec2): '), read(G), reconsult(G), write('Введите имя файла с данными об изображении'),

142

nl, write(' (ai_patrec3): '), read(D), reconsult(D), patrecdata(A, B),

assert((solution(A) :- B)), % Подготовить список целей.

side_list(A, X) :- var(X), !, name(X, [A]).

% Присвоение граням имён: a, b, … side_list(A, X;Y) :- !, name(X, [A]), inc(A, A1),

side_list(A1, Y).

edge_list(N, (X, Y)) :- arg(3, X, N), inc(N, N1),

% Присвоение рёбрам номеров: 1, 2, … edge_list(N1,Y).

edge_list(N, X) :- arg(3, X, N).

outp(A;B, N, X:V; Y) :- var(V), !,

% Выдача результатов распознавания

V=N, outp1(A, X:N), nl, inc(N, N1), outp(B, N1, Y).

outp(A;B, N, X:V;Y) :- !, outp1(A, X:V), nl, outp(B, N, Y).

outp(A, N, X:V) :- var(V), !, V=N, outp1(A, X:N).

outp(A, N, X:V) :- !, outp1(A, X:V).

143

outp1(A, X:Y) :- % Печать результата для одной грани write(' У тела '), write(Y),

write(' грань '), write(A), write(' – '), write(X).

write_list((X, Y)) :-

write(X), write(' '), write_list(Y). % Печать списка рёбер write_list(X) :- write(X), nl.

inc(N, N1) :- N1 is N+1. dec(N, N1) :- N1 is N-1.

В этом случае «фотография» консоли после запуска программы будет иметь следующий вид:

| ?- patrec.

Введите имя файла с правилами для распознавания

(ai_patrec2): |: ai_patrec2.

Введите имя файла с данными об изображении

(ai_patrec3): |: ai_patrec3.

a ; b ; c ; d ; e ; f ; g ; h ; i ; j

pr(фон,b,1) nr(b,фон,2) vr(фон,e,3) pr(фон,g,4) nr(g,фон,5) vr(h,фон,6) pr(h,фон,7) nr(фон,e,8) vr(f,фон,9) pr(f,фон,10) nr(фон,d,11) pr(c,фон,12) nr(фон,a,13) vr(фон,a,14) nr(a,b,15) pr(b,c,16) vr(a,c,17) vr(c,d,18) nr(d,b,19) pr(b,f,20) nr(j,i,28) pr(j,h,29)

Утела 1 грань a – левая

Утела 1 грань b – горизонтальная

Утела 1 грань c – правая

Утела 1 грань d – левая

Утела 2 грань e – левая

Утела 1 грань f – правая

Утела 2 грань g – горизонтальная

Утела 2 грань h – правая

Утела 2 грань i – левая

Утела 2 грань j – горизонтальная yes

144

Авторское право на постановку данной задачи и коды 10.2 –

10.3принадлежат Д.Уоррену (D.H.D.Warren, 1975).

2.Задача о коммивояжёре

Напомним постановку этой задачи. Имеется несколько городов, между каждой парой которых существует дорога известной длины. Коммивояжёру («странствующему торговцу») необходимо побывать в каждом из этих городов по одному разу, вернуться в город, из которого он начал своё путешествие, преодолев при этом путь минимальной длины.

Приведем решение этой задачи, «скаченное» автором из Интернета (вместе с бесплатной версией Пролога LPA 4.200) без какихлибо комментариев. Единственное, что сделал автор – это убрал большую часть (90 %) кода, посвящённую графическому интерфейсу (рисованию карты Британии и отображению на ней результатов работы программы), а также сократил (с 25 до 6) список городов Британии.

Автор надеется, что английский язык примера не смутит чита-

телей (слушателей).

Код 10.5

/* The Travelling Salesman – (c) 1998-2001 LP Associates Ltd Rewritten with new algorithms by:

Brian D Steel, 17 Jun 98 / 19 Sep 01 Original version by:

Nicky Johns, Frank McCabe, Rebecca Shalfield,

Brian D Steel, Phil Vasey, Alan Westwood, Dave Westwood

This program displays a map of the mainland UK, showing a number of towns. These can be selected using the mouse, and then the shortest route found between them. Two algorithms are defined: the "exhaustive" one finds

every possible route and returns the shortest; the "heuristic" one takes each selected town in turn, and inserts it into the optimal location in the route as it grows. The former routine is combinatorial in nature, and takes far too long to compute complex routes; the latter is an n-square algorithm,

and works reasonably well even with large numbers of towns, however, it does not always return the very best route.

145