Prolog for theorem proving, expert systems, type inference systems, and automated planning...
2017-05-25
In the name of the father of Prolog (Alain_Colmerauer who died few days ago), I’ll show how to use Prolog for solving a common business problem: finding the paths in a graph between two nodes.. “Prolog is declarative programming language: the program logic is expressed in terms of relations, represented as facts and rules. A computation is initiated by running a query over these relations”. [Wikipiedia]. “Prolog is a general-purpose logic programming language associated with artificial intelligence and computational linguistics [..] The language has been used for theorem proving, expert systems, type inference systems, and automated planning, as well as its original intended field of use, natural language processing.[Wikipiedia]. You tell Prolog the facts and rules of your game and it will find the solution ;-) In this tutorial my graph is the network of underground/train stations of Milan. The facts are like
station('Affori centro', m3).
station('Affori FN', m3).
station('Affori', s2).
station('Affori', s4).
station('Airuno', s8).
station('Albairate - Vermezzo', s9).
station('Albate Camerlata', s11).
station('Albizzate', s5).
station('Amendola Fiera', m1).
station('Arcore', s8).
station('Assago Milanofiori Forum', m2).
station('Assago Milanofiori Nord', m2).
edge('Villapizzone', 'Lancetti', s5).
edge('Villapizzone', 'Lancetti', s6).
edge('Villa Pompea', 'Gorgonzola', m2).
edge('Villa Raverio', 'Carate-Calò', s7).
edge('Villasanta', 'Monza Sobborghi', s7).
edge('Villa S. Giovanni', 'Precotto', m1).
edge('Vimodrone', 'Cascina Burrona', m2).
edge('Vittuone', 'Pregnana Milanese', s6).
edge('Wagner', 'De Angeli', m1).
edge('Zara', 'Isola', m5).
edge('Zara', 'Sondrio', m3).
```The rules are like```
adiacent(\[X,L1\], \[Y,L1\]) :- edge(X,Y, L1) ; edge(Y, X, L1).
change(L1,L2, X) :-
station(X,L1),
station(X,L2),
not(L1 == L2).
same_line_path(Node, Node, _, [Node]). % rule 1
same_line_path(Start, Finish, Visited, [Start | Path]) :- % rule 2
adiacent(Start, X),
not(member(X, Visited)),
same_line_path(X, Finish, [X | Visited], Path).
one_change_line_path([Start,L1], [End,L2], Visited, Path):-
station(Start,L1),
station(End,L2),
change(L1,L2, X),
same_line_path([Start,L1], [X,L1], [[Start,L1]|Visited], Path1),
same_line_path([X,L2], [End,L2], [[X,L2]|Visited], Path2),
append(Path1, Path2, Path).
You can find the source code of the Prolog webservice at https://github.com/matteoredaelli/metropolitana-milano