/*********************************************************** tsp_planner.pi from Constraint Solving and Planning with Picat, Springer by Neng-Fa Zhou, Hakan Kjellerstrand, and Jonathan Fruhman ***********************************************************/ import planner. main => M = {{0,6,1,5,0,0}, % cost matrix {6,0,5,0,3,0}, {1,5,0,5,6,4}, {5,0,5,0,0,2}, {0,3,6,0,0,6}, {0,0,4,2,6,0}}, tsp(M). tsp(M) => N = length(M), Rel = [], foreach (I in 1..N) Neibs = [(J,M[I,J]) : J in 1..N, M[I,J] > 0].sort(2), Rel := [$neibs(I,Neibs)|Rel] end, cl_facts(Rel,[$neibs(+,-)]), best_plan_bb({1,2..N},Plan,Cost), println(Plan), println(plan_cost = Cost). final({1,[]}) => true. action({V,[]}, NState, Action, ActionCost) => NState = {1,[]}, Action = 1, % go back to vertex 1 neibs(V,Neibs), member((1,ActionCost),Neibs). action({V,Unvisited}, NState, Action, ActionCost) => NState = {NextV,NUnvisited}, Action = NextV, % visit NextV neibs(V,Neibs), member((NextV,ActionCost),Neibs), once select(NextV,Unvisited,NUnvisited).