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

To run this example, compile this program and then run the goal:

?- salesman.\

*/

Два алгоритма решения задачи о коммивояжёре:

exhaustive( [Home|Towns], Route, Dist ) :-

best_route( exhaustive_route(Towns,Home,Route), Route ), measure_route( Route, 0, Dist ).

exhaustive_route( [], Home, [Home,Home] ).

exhaustive_route( [Town|Towns], Home, NewRoute ) :- exhaustive_route( Towns, Home, IntRoute ), insert_route( Town, IntRoute, NewRoute ).

heuristic( [Home|Towns], Route, Dist ) :- heuristic_route( Towns, [Home,Home], Route ), measure_route( Route, 0, Dist ).

heuristic_route( [], Route, Route ).

heuristic_route( [Town|Towns], OldRoute, NewRoute ) :- best_route( insert_route(Town,OldRoute,IntRoute), IntRoute ), heuristic_route( Towns, IntRoute, NewRoute ).

best_route( Test, Route ) :- abolish( temp_store/2 ),

assert( temp_store([], 99999999) ), ( Test,

measure_route( Route, 0, NewDist ), temp_store( _, OldDist ),

NewDist < OldDist, abolish( temp_store/2 ),

assert( temp_store(Route,NewDist) ), fail

; % Логическое «ИЛИ» (пояснение Н.Г. Волченкова)

146

temp_store( Route, _ ), abolish( temp_store/2 ) ).

measure_route( [Town], Dist, Dist ) :- !.

measure_route( [Town1,Town2|Towns], OldDist, NewDist ) :- distance( Town1, Town2, Dist ),

IntDist is Dist + OldDist,

measure_route( [Town2|Towns], IntDist, NewDist ).

insert_route( Town, [Town1,Town2|R], [Town1,Town, Town2|R] ).

insert_route( Town, [Town1|OldRoute], [Town1|NewRoute] ) :- insert_route( Town, OldRoute, NewRoute ).

distance( Town1, Town2, Dist ) :- dist( Town1, Town2, Dist ), !.

distance( Town1, Town2, Dist ) :- dist( Town2, Town1, Dist ), !.

Рассмотрим, для примера, только 15 фактов, в которых зафиксированы расстояния между шестью городами Британии:

Аэто – проведённый запуск программы («фотография» консоли

срезультатами её работы):

| ?-

# 0.000 seconds to consult sales-new.pl [d:\prolog\lpa2002\fb998f02\examples\] | ?- heuristic( [b,e,g,l,m,n], Route, Dist ). Route = [b,l,g,e,m,n,b] ,

Dist = 687

| ?- exhaustive( [b,e,g,l,m,n], Route, Dist ). Route = [b,m,l,g,e,n,b] ,

Dist = 677

| ?-

Графическая иллюстрация полученного результата представлена на рис. 10.5.

Рис. 10.5. Решение задачи о коммивояжере для шести городов Британии

Данный пример показывает, что не всегда эвристический алгоритм (рис. 10.5,а) даёт тот же результат, что и алгоритм полного перебора (рис. 10.5,б). Очевидно, что в случае их несовпадения первый результат несколько хуже второго – здесь: 687 > 677.

3. Задача об обитателях пяти домов

Это типичная задача, решение которой требует дедуктивного дарования известного сыщика Шерлока Холмса. Автор нашел её

148

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

Приведем программу целиком (код 10.6) «в оригинале». Автор надеется, что английский язык этого примера (как и в представле-

нии задачи о коммивояжере) не смутит читателей (слушателей).

Код 10.6

%PROLOG program to solve the "5 houses" problem using

%a "verify and choose" method.

:- assert(bag(n, 0)).

:- write('There are five houses, each of a different color and '),nl, write(' inhabited by men of different nationalities, '),nl, write(' with different pets, drinks and cigarettes.'),nl,nl, write('1. The Englishman lives in the red house.'),nl,

write('2. The Spaniard owns the dog.'),nl, write('3. Coffee is drunk in the green house.'),nl, write('4. The Ukrainian drinks tea.'),nl,

write('5. The green house is immediately to the right'), write(' of the ivory house.'),nl,

write('6. The Winston smoker owns snails.'),nl, write('7. Kools are smoked in the yellow house.'),nl, write('8. Milk is drunk in the middle house.'),nl,

write('9. The Norwegian lives in the first house on the left.'),nl, write('10. The Chesterfields smoker lives next to the man'), write(' with the fox.'),nl,

write('11. Kools are smoked next to the house where'), write(' the horse is kept.'),nl,

write('12. The Lucky Strike smoker drinks orange juice.'),nl, write('13. The Japanese smokes Parliaments.'),nl,

write('14. The Norwegian lives next to the blue house.'),nl, write(''),nl,

write('THE PROBLEM: Who owns the Zebra? '),nl, write(' Who drinks water?),nl,

write('Type: ?-zebra(N).'),nl.

149

zebra(N) :- write('Wait...'), nl, solve(N).

zebra(N) :- retract(bag(n,N)),!.

solve(New) :- candidate(Colours,Drinks,Nationalities,Cigarettes,Pets),

!, % Это «отсечение» в программу включил автор

% (Н. Волченков) – догадайтесь, зачем? constraints(Colours,Drinks,Nationalities,Cigarettes,Pets), member(water:Nw, Drinks), member(zebra:Nz, Pets), write(water:Nw),nl, write(zebra:Nz),nl, write(Colours),nl,

write(Drinks),nl,

write(Nationalities),nl,

write(Cigarettes),nl,

write(Pets),nl, step_number(New).

step_number(New):-

retract(bag(n,Old)), New is Old+1, assert(bag(n,New)),!.

%A candidate solution is any of the (5!)**5 ways of

%distributing 5 colours (C), 5 drinks (D), 5 nationalities (N),

%5 cigarettes (S), and 5 pets (P) amongst 5 houses.

candidate(L1, L2, L3, L4, L5) :-

perm(L1), perm(L2), perm(L3), perm(L4), perm(L5).

perm([_:A,_:B,_:C,_:D,_:E]) :- permutation([A,B,C,D,E], [1,2,3,4,5]).

%The following constraints are placed on colours (C),

%drinks (D), nationalities (N), cigarettes (S) and pets (P).

constraints(C, D, N, S, P) :-

% The Englishman lives in the red house. member(englishman:H1, N), member(red:H1, C),

150