[gecode-users] graph constraints and hamiltonian path

[serge lemouton]

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