Jump to content
  • Advertisement
Sign in to follow this  
stu2000

TSP brute force state change algorithm

This topic is 2700 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello all!

Ive been working on this for about two days whenever I have spare time, and its making me feel so dumb because i get the feeling the answer should be obvious. (probably just a few well placed modulus ' % ' signs. )

I'm trying to figure out a way to get between states (list of nodes) in the TSP (travelling salesperson problem). I know many of you will say you need to use AI and thats the best/quickest way to get a solution, but i've already done/know that at university.

Example

state 1 -> A B C D
state 2 -> B A C D
state 3-> A C B D
etc


the state number continuously increases and from the number a unique state can be formulated. It might be easier to imagine the nodes as A B C D A, instead of A B C D, you already know that you have to end up back at the head of the list at the end.

The key is that the state should be represented by an integer so that it can be incrementally increased. Each state should preferably be unique, but I would be happy to settle for an algorithm that somehow ends up with the occasional same actual state from two different state numbers.

Its easy to get all the combinations of doing one switch, but getting it so that it will get all the states by performing two switches is hard,
eg like going from A B C D to C A B D

It can be quite hard to get my point across sometimes so if you don't understand that's normal and please just respond asking about the relevant bit.

Thanks in advance,
Stu

Share this post


Link to post
Share on other sites
Advertisement
So far I have come up only with the following algorithm.

Treat it like your trying to brute force a bicycle spin lock ( 3 to 4 wheels of numbers 0-9 remember them)
Instead of numbers you have letters representing the nodes
Since no letter can be used twice, treat the wheel as a 'priority'
You keep spinning the left most wheel one notch (letter/number) each time to change the priority, and once you have turned that wheel a full turn, turn the second wheel by one notch. You keep repeating this until the second wheel has turned fully and then you turn the third wheel one notch. Once the final wheel (rightmost wheel) has done a full circle, all the possible outcomes should have been made.

Diagram shown.
4617251627.jpg

Whenever a 'wheel' wants to output a letter which is already placed, it tries to output the next priority letter. If that letter is already placed it repeats until it places a letter.

Unfortunately, since the last wheel has last say, the last wheel changing priority is pointless and that series is pointless.

Is this method complete (get every state)? i know its not perfect as there will be duplicates =(

Share this post


Link to post
Share on other sites

clicky


cheers for that. looking through it. http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm looked most interesting, then realised will be hard to reach each state without going through each previous state. I need to be able to pick an algorithm that doesnt rely on working through the previous states because this will be programmed in parallel and not on a single thread in serial.

Share this post


Link to post
Share on other sites
Read more of that page. It describes how an index can be used to generate the corresponding permutation in lexicographic order.

Share this post


Link to post
Share on other sites

Read more of that page. It describes how an index can be used to generate the corresponding permutation in lexicographic order.


Are you referring to the page you linked or the page I linked?

Are you referring to this section of the page you linked:

[font=sans-serif][size=2]"An obvious way to generate permutations of n is to generate values for the Lehmer code (possibly using the factorial number system representation of integers up to n!), and convert those into the corresponding permutations. However the latter step, while straightforward, is hard to implement efficiently, because it requires n operations each of selection from a sequence and deletion from it, at an arbitrary position; of the obvious representations of the sequence as an array or a linked list, both require (for different reasons) about n[sup]2[/sup]/4 operations to perform the conversion. With n likely to be rather small (especially if generation of all permutations is needed) that is not too much of a problem, but it turns out that both for random and for systematic generation there are simple alternatives that do considerably better. For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in O(n log n) time."[/font]
[font="sans-serif"]
[/font]
[font="sans-serif"]Stu[/font]

Share this post


Link to post
Share on other sites
I will try tonight with set A B C D
first letter chosen is = index %4, second = index %3, thrid index %2

each time letter chosen it is removed from the base list, A B C D, and base list is always kept in alphabeitcial order.

ie
if index 6 produces 2 ,0, 0 so result is C A B D
if index 3 produces 3, 0, 1 so result C A D B

Has anyone tried this, know any fatal flaws with it?

Share this post


Link to post
Share on other sites
Well, in exactly that form it doesn't work... you can see that the period of the sequence is 12, but there's 24 possible permutations, so the algorithm only visits half of them.

A similar algorithm works fine: first letter chosen is index/4, then set index := index%4. Second letter chosen is index/3, then set index := index%3. And so on. This is equivalent in function to the factorial numbering explained in the wikipedia page.

Don't do it for every permutation, though. Do it once for each thread to identify the first permutation for it to work on (for 24 permutations and 4 threads, the first thread starts at permutation 0, the second starts at permutation 6, the third at permutation 12...), and from there just do the standard iteration algorithm. That's where the lexicographic ordering comes in handy.

Share this post


Link to post
Share on other sites

Well, in exactly that form it doesn't work... you can see that the period of the sequence is 12, but there's 24 possible permutations, so the algorithm only visits half of them.

A similar algorithm works fine: first letter chosen is index/4, then set index := index%4. Second letter chosen is index/3, then set index := index%3. And so on. This is equivalent in function to the factorial numbering explained in the wikipedia page.

Don't do it for every permutation, though. Do it once for each thread to identify the first permutation for it to work on (for 24 permutations and 4 threads, the first thread starts at permutation 0, the second starts at permutation 6, the third at permutation 12...), and from there just do the standard iteration algorithm. That's where the lexicographic ordering comes in handy.


Thanks for that. I did notice that i missed quite a few and it was flawed, unfortunately your suggestion wont work for me either for two reasons.
1) I didnt understand what you meant when it came to set index := index%4 is that different from index = index%4? i dont understand the :.


2) im actualy usingthis for CUDA and will have a single thread for calculating each and every permutaiton. The index will be generated from the threadIdx.x + blockIdx.x etc. This way i am trying to use the huge power of the gpu's parallel computation and even though calculating each permutation should be slower on its own, having hundreds/thousands running in parallel at a time should make this faster.

Is your algorithm summed up like: (pseudo code)


function CalculatePermutation( int index )
{
int firstLetter = index / 4;
char firstLetterChar = GetCharFromNumber ( firstLetter );
index = index % 4;

int secondLetter = index / 3;
char secondLetterChar = GetCharFromNumber ( secondLetter );
index = index % 3;

int thirdLetter = index / 2
char thirdLetterChar = GetCharFromNumber ( thirdLetter );
index = index % 2;

...etc..

}

I wouldnt need to pass the final index from that into the next call to CalculatePermutation would i?

ie can i run something like:
for ( int i = 0; i<25; i++)
{
CalculatePermutation( i );
}

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!