Re: Traveling Salesman Problem
- From: Lie Ryan <lie.1296@xxxxxxxxx>
- Date: Thu, 27 May 2010 05:01:58 +1000
On 05/27/10 03:41, olivier.scalbert@xxxxxxxxxxx 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.
.
- References:
- Traveling Salesman Problem
- From: olivier.scalbert@xxxxxxxxxxx
- Traveling Salesman Problem
- Prev by Date: Traveling Salesman Problem
- Next by Date: Re: Traveling Salesman Problem
- Previous by thread: Traveling Salesman Problem
- Next by thread: Re: Traveling Salesman Problem
- Index(es):
Relevant Pages
|
