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 provingexpert systemstype 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


Enter your instance's address


More posts like this

Smart investment Problem with Prolog

2024-07-14 | #programming #prolog

Below my #prolog solution for Smart investment problem. It is a sample of Linear Programming using Prolog. A client of an investment firm has $10000 available for investment. He has instructed that his money be invested in particular stocks, so that no more than $5000 is invested in any one stock but at least $1000 be invested in each stock.

Continue reading 