Encoding tsp.dlv

Name tsp.dlv [Root]    Graph Problems (32)    Hamilton (17) Martin Gebser Wolfgang Faber 2009-03-30 13:03 2009-03-10 13:06 TravelingSalespersonSuite bound/1edge/2edgewt/3maxweight/1vtx/1 hc/2 No % A DLV encoding for the Hamiltonian Cycle problem. % Input graph is undirected. % By Wolfgang Faber % Work on the directed representation. A directed HC of this exists iff an % undirected HC exists in the undirected graph. It is just easier to deal with. arc(X,Y) :- edge(X,Y). arc(Y,X) :- edge(X,Y). % Take the vertex identified by bound() as arbitrary starting point. % Choose an outgoing arc and work the way along the thus constructed path. in_hm(X,Y) v out_hm(X,Y) :- bound(X), arc(X,Y). in_hm(X,Y) v out_hm(X,Y) :- reached(X), arc(X,Y). reached(Y) :- in_hm(_,Y). % Each node must have exactly one incoming and one outgoing arc of the HC. :- vtx(X), not #count{ Y: in_hm(X,Y)} = 1. :- vtx(Y), not #count{ X: in_hm(X,Y)} = 1. % The HC must be connected. :- vtx(X), not reached(X). % Finally express the HC using edge representations of the input graph. hc(X,Y) :- in_hm(X,Y), edge(X,Y). hc(X,Y) :- in_hm(Y,X), edge(X,Y). :- maxweight(M), #sum{ W,X,Y: hc(X,Y), edgewt(X,Y,W) } > M.