How to create random routes?
Anyone heard of genetic algorithm TSP? I am trying to code it, but i am stuck on how to generate parents routes. It saids brute force in "http://www.lalena.com/AI/Tsp/" what does that means you can't generate a bunch of numbers by using brute force =.= it takes trillion years to generate 1 how to generate a bunch.
I just heard about the idea of the algorithm. I am curious... I don't see what is your problem, suppose you have n = 30 cities, the population size is N = 10000 (parents). What you have to do is randomly choosing N routes, which contain 30 points each. I think those are approximately N*n activities of calling random function, which doesn't look terrible, right?
If your problem is random sampling n objects (n numbers), you can check the method on wiki. I may give an idea, no guarantee though.
1. Generate an array A, containing 1 to n.
2. Generate a random number between 1 to n, say k.
3. Exchange the number of k_th with number n_th.
4. Now we have new array with n-1 numbers, sitting from 1 to n-1 site of the array. Come back to step 2 until all are done (generate a random number from 1 to n-1, and so on...)
If your problem is random sampling n objects (n numbers), you can check the method on wiki. I may give an idea, no guarantee though.
1. Generate an array A, containing 1 to n.
2. Generate a random number between 1 to n, say k.
3. Exchange the number of k_th with number n_th.
4. Now we have new array with n-1 numbers, sitting from 1 to n-1 site of the array. Come back to step 2 until all are done (generate a random number from 1 to n-1, and so on...)
Last edited on
Topic archived. No new replies allowed.