Traveling Salesman Problem

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: olivier.scalbert on 26 May 2010 13:41

---

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 ?

Thanks,

Olivier

From: Lie Ryan on 26 May 2010 15:01

---

On 05/27/10 03:41, 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 ?

HashMap (aka dictionary) is amortized O(1) (that is, it's O(1) unless
you've got collisions) for insertion, deletion, and indexing. However
using HashMap you will have to figure out a way to do fast O(1) hashing
and equality comparison.

From: Patricia Shanahan on 26 May 2010 17:10

---

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 ?

Think carefully about whether you really need the array-like indexing.
If you could work entirely with pointers to towns, you could use a
doubly linked list. That gives O(1) time for e.g. moving town A to be
immediately before or after town B.

Patricia

From: Kai-Uwe Bux on 26 May 2010 17:15

---

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 ?


What about:

#include <utility>
#include <vector>
#include <cassert>

#include <iostream>
#include <ostream>
#include <iterator>

class route {
public:

typedef unsigned int city;

private:

typedef std::pair< city, city > prev_next;

std::vector< prev_next > the_tour;

public:

route ( unsigned int num_cities )
: the_tour ( num_cities, prev_next() )
{
for ( city c = 0; c < num_cities; ++c ) {
the_tour[ c ].second = ( c + 1 ) % num_cities;
the_tour[ c ].first = ( c + num_cities - 1 ) % num_cities;
}
}

template < typename OutIter >
OutIter write_tour ( OutIter where ) const {
city c = 0;
do {
*where++ = c;
c = the_tour[ c ].second;
} while ( c != 0 );
return ( where );
}

route & move_city ( city moving, city target ) {
{ // remove
city prev_city = the_tour[ moving ].first;
city next_city = the_tour[ moving ].second;
the_tour[ prev_city ].second = next_city;
the_tour[ next_city ].first = prev_city;
}
{ // re-insert
city prev_city = the_tour[ target ].first;
city next_city = target;
the_tour[ moving ].first = prev_city;
the_tour[ moving ].second = next_city;
the_tour[ prev_city ].second = moving;
the_tour[ next_city ].first = moving;
}
}

};


int main ( void ) {
route::city const new_york = 0;
route::city const chicago = 1;
route::city const syracuse = 2;
route::city const salt_lake = 3;
route::city const num_cities = 4;

route the_route ( num_cities );
the_route.write_tour
( std::ostream_iterator< route::city >( std::cout, " " ) );
std::cout << "\n";

the_route.move_city( new_york, salt_lake );
the_route.write_tour
( std::ostream_iterator< route::city >( std::cout, " " ) );
std::cout << "\n";

the_route.move_city( chicago, new_york );
the_route.write_tour
( std::ostream_iterator< route::city >( std::cout, " " ) );
std::cout << "\n";
}


Best

Kai-Uwe Bux

From: olivier.scalbert on 27 May 2010 12:33

---

On May 26, 11:15 pm, Kai-Uwe Bux <jkherci...(a)gmx.net> wrote:

> What about:
>
> #include <utility>
> #include <vector>
> #include <cassert>
>
> #include <iostream>
> #include <ostream>
> #include <iterator>
>
> class route {
> public:
>
>   typedef unsigned int city;
>
> private:
>
>   typedef std::pair< city, city > prev_next;
>
>   std::vector< prev_next > the_tour;
>
> public:
>
>   route ( unsigned int num_cities )
>     : the_tour ( num_cities, prev_next() )
>   {
>     for ( city c = 0; c < num_cities; ++c ) {
>       the_tour[ c ].second = ( c + 1 ) % num_cities;
>       the_tour[ c ].first  = ( c + num_cities - 1 ) % num_cities;
>     }
>   }
>
>   template < typename OutIter >
>   OutIter write_tour ( OutIter where ) const {
>     city c = 0;
>     do {
>       *where++ = c;
>       c = the_tour[ c ].second;
>     } while ( c != 0 );
>     return ( where );
>   }
>
>   route & move_city ( city moving, city target ) {
>     { // remove
>       city prev_city = the_tour[ moving ].first;
>       city next_city = the_tour[ moving ].second;
>       the_tour[ prev_city ].second = next_city;
>       the_tour[ next_city ].first = prev_city;
>     }
>     { // re-insert
>       city prev_city = the_tour[ target ].first;
>       city next_city = target;
>       the_tour[ moving ].first  = prev_city;
>       the_tour[ moving ].second = next_city;
>       the_tour[ prev_city ].second = moving;
>       the_tour[ next_city ].first = moving;
>     }
>   }
>
> };
>
> int main ( void ) {
>   route::city const new_york = 0;
>   route::city const chicago = 1;
>   route::city const syracuse = 2;
>   route::city const salt_lake = 3;
>   route::city const num_cities = 4;
>
>   route the_route ( num_cities );
>   the_route.write_tour
>     ( std::ostream_iterator< route::city >( std::cout, " " ) );
>   std::cout << "\n";
>
>   the_route.move_city( new_york, salt_lake );
>   the_route.write_tour
>     ( std::ostream_iterator< route::city >( std::cout, " " ) );
>   std::cout << "\n";
>
>   the_route.move_city( chicago, new_york );
>   the_route.write_tour
>     ( std::ostream_iterator< route::city >( std::cout, " " ) );
>   std::cout << "\n";
>
> }
>
> Best
>
> Kai-Uwe Bux

Thanks very much. It looks very promising !
I will do some tests this weekend ...

Olivier

 |  Next  |  Last
Pages: 1 2 3
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