Traveling Salesman Problem
in [General Programming]
|
Prev: Ctalk 0.0.96a 20100523 Release Candidate Available
Next: where to find a job scheduler (implemented by c++) to distribute jobs to nodes and then collect results
From: Casey Hawthorne on 29 May 2010 23:56 There are many versions of the TSP and they all have applications. - on undirected graphs -- symmetric TSP on a complete (dense) graph -- symmetric TSP on a sparse graph - on directed graphs -- antisymmetric TSP on a complete (dense) graph -- antisymmetric TSP on a sparse graph I didn't realize you were changing positions of cities in a data structure, I thought you changing changing cities' positions in Euclidean space. In any case, it is a lot easier to swap two edges in the tour, than change cities and all their associated links. Simulated annealing swaps two edges for fast transistions from one configuration to another. On Sat, 29 May 2010 23:12:10 +0200, Kai-Uwe Bux <jkherciueh(a)gmx.net> wrote: >Casey Hawthorne wrote: > >> For the dense Euclidean TSP, you need to update all the distances to >> all the other nodes, O(n). > >a) What is the "dense" Euclidean TSP as opposed to a "non-dense" TSP? > >b) Why do distances to other nodes change? I thought, the distances between >the cities are given and just the order in which the cities are visited >changes. Then, to update the total length, you need to subtract the lengths >of those edges that you break by changing the order and add in the lengths >of the edges that you create. > > >>>On Wed, 26 May 2010 10:41:54 -0700 (PDT), >>>"olivier.scalbert(a)algosyn.com" <olivier.scalbert(a)algosyn.com> wrote: >>> >>>>Hello, >>>> >>>>In the context of the TSP (Traveling Salesman Problem), I would like >>>>to have a good an efficient way of representing and manipulating the >>>>route (joining all the towns). >>>>What I would like, is to be able to remove one town from the "list" of >>>>towns at a given position and reinsert it at an other given position, >>>>in O(1). So I need something as a list for fast remove/insert and >>>>something as an array for fast index access.Do you know if such an ADT >>>>exists ? >[...] > >Best > >Kai-Uwe Bux -- Regards, Casey
From: Casey Hawthorne on 31 May 2010 23:07
There are many versions of the TSP and they all have applications. - on undirected graphs -- symmetric TSP on a complete (dense) graph -- symmetric TSP on a sparse graph - on directed graphs -- antisymmetric TSP on a complete (dense) graph -- antisymmetric TSP on a sparse graph Added another variation: Also minimum cost tours (not minimum length) where you are allowed to visit a city more than once. The triangle inequality rarely applies in these cases. I didn't realize you were changing positions of cities in a data structure, I thought you changing changing cities' positions in Euclidean space. In any case, it is a lot easier to swap two edges in the tour, than change cities and all their associated links. Simulated annealing swaps two edges for fast transistions from one configuration to another. -- Regards, Casey |