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: olivier.scalbert on 27 May 2010 13:24 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 Hi, How can I "undo" a move ? the_route.move_city(town1, town2); evaluate() the_route.unmove_city(town1, town2); the_route.move_city(town1, town3); evaluate() the_route.unmove_city(town1, town3); .... Olivier
From: Kai-Uwe Bux on 27 May 2010 15:19 olivier.scalbert(a)algosyn.com wrote: > 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 > > Hi, > How can I "undo" a move ? > > the_route.move_city(town1, town2); > evaluate() > the_route.unmove_city(town1, town2); > the_route.move_city(town1, town3); > evaluate() > the_route.unmove_city(town1, town3); E.g.: #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 ); } city move_city ( city moving, city target ) { city result; { // remove city prev_city = the_tour[ moving ].first; city next_city = the_tour[ moving ].second; result = next_city; 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; } return ( result ); } }; 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"; route::city undo = 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( new_york, undo ); the_route.write_tour ( std::ostream_iterator< route::city >( std::cout, " " ) ); std::cout << "\n"; } BTW: instead of evaluating the length of the tour from scratch every time, you could update the length: two city connections are removed and two new ones are created; all others remain the same. Thus, subtracting two edge lengths and adding two new lengths is all that is needed. You can merge that with move_city and keep the length up-to-date. Best Kai-Uwe Bux
From: Casey Hawthorne on 29 May 2010 02:15 For the dense Euclidean TSP, you need to update all the distances to all the other nodes, O(n^2). 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 ? > >Thanks, > >Olivier -- Regards, Casey
From: Casey Hawthorne on 29 May 2010 13:35 For the dense Euclidean TSP, you need to update all the distances to all the other nodes, O(n). > >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 ? >> >>Thanks, >> >>Olivier -- Regards, Casey
From: Kai-Uwe Bux on 29 May 2010 17:12
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 |