[gecode-users] graph constraints and hamiltonian path

[Christian Schulte]

The idea is: add a _new_ point and then  define the cost from this point to
the first point to be zero. That's it.

Christian

--
Christian Schulte, KTH, web.it.kth.se/~cschulte/


-----Original Message-----
From: serge lemouton [mailto:serge.lemouton at ircam.fr] 
Sent: Saturday, May 21, 2011 11:24 PM
To: cschulte at kth.se
Cc: users at gecode.org
Subject: Re: [gecode-users] graph constraints and hamiltonian path

Dear Christian,

Thanks for your idea, but I am not sure to understand how to implement it. 
Moreover, i don't know if it will work, because what i want to do is to find
a path  minimizing the total distance through an ensemble of points, and it
seems to me that the "circuit" constraint will always take into account the
distance between the last and the first city in the salesman itinerary,
isn't it ?
It does not seem obvious to me that we can obtain the shortest path simply
by removing the longest distance of the shortest circuit, but I am not an
expert in hamiltonian graphs !

Serge

On 19 mai 2011, at 23:21, Christian Schulte wrote:

> Hmmm. Just thinking: how about adding an additional node that is 
> assigned to lead back to the start node and then find a Hamiltonian
circuit for this?
> That should work, shouldn't it? Or am I missing something.
> 
> Christian
> 
> --
> Christian Schulte, KTH, web.it.kth.se/~cschulte/
> 
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On 
> Behalf Of serge lemouton
> Sent: Thursday, May 19, 2011 9:32 PM
> To: users at gecode.org
> Subject: [gecode-users] graph constraints and hamiltonian path
> 
> Hello,
> 
> Question about graph constraints:
> I would like to modify the the TSP example in order to find the 
> solutions where the travelling salesman should not return to its starting
point.
> In other terms, is it possible to use the "circuit" constraint to find 
> an hamiltonian path instead of a circuit ?
> Does it require to modify the code or is it better to create another 
> subclass of the graph class ?
> 
> Thanks for any advice,
> 
> Serge Lemouton
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
> 
>