Implementation of TSP using heuristic approach using Prolog.

 Implementation of TSP using heuristic approach using Prolog.




Description : 

Travelling Salesman Problem (TSP) : Given a set of cities and distances between every        pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.

Solution : à find the cheapest way of visiting all the cities and returning to the starting point.

Examples

Output of Given Graph: 
minimum weight Hamiltonian Cycle :
 1+4+7+9+3 = 23 path 1
2+3+8+6+1 =  20 path 2 
find all possible paths like that ?
-
-

Source Code 

e(1,2,1). e(1,3,3). e(1,5,2). e(2,1,1). e(2,4,6). e(2,5,4). e(3,1,3). e(3,4,8). e(3,5,3). e(4,2,6). e(4,3,8). e(4,5,7). e(5,1,2). e(5,2,4). e(5,3,3). e(5,4,7). v([1,2,3,4,5]). s(R,[],[F|P],C,Ph,Ch):-e(F,R,W),CW is C+W,Ph=[R,F|P],Ch=CW. s(R,Y,[F|P],C,Ph,Ch):-member(T,Y),delete(Y,T,Z),e(F,T,W),CW is C+W,s(R,Z,[T,F|P],CW,Ph,Ch). h(R,Y,H):-findall(z(Ph,Ch),s(R,Y,[R],0,Ph,Ch),H). minh([z(P1,C1)],[z(P1,C1)]). minh([z(P1,C1),z(_P2,C2)|H],M):-C1=code-box

Out put : 

Example :

(If in case any error please check the color representation is the most important.)





0/Post a Comment/Comments

Thanks, for contacting us.
We will reviewing us on your comments . Please wait an hour.
Air Reality Team....

Previous Post Next Post