Depends on the connectivity, but probably not.
Look into ant colony optimization and or ant systems, but ant colony will be better, since it was designed to solve problems like this, especially if optimality is not required. Since that can't be guaranteed anyways.
Quote:Original post by fractoid
well, for a 40x40 maze, I'd guess you wouldn't have more than 30 or 40 intersections. Is that a small enough number to brute-force TSP?
<referential tsp linky>
Its not the number of intersections.
Its the number of pills that i need. (you only need to get a path from pill to pill, ect.)
I've got a really sneaky idea.
From,
Nice coder
Quote:Original post by fractoid
well, for a 40x40 maze, I'd guess you wouldn't have more than 30 or 40 intersections. Is that a small enough number to brute-force TSP?
<referential tsp linky>
Hell no.
40! is HUGE.
We need a sneaky algo.
From,
Nice coder
Quote:Original post by Nice CoderSorry, poor choice of words. I meant use a heuristic-but-relatively-time-consuming-compared-to-greedy algorithm, of the sort on that page. Not just a naieve recursive implementation, which, as you point out, would be fine if you have a quantum computer to run it on. :P
Hell no.
40! is HUGE.
We need a sneaky algo.
From,
Nice coder
Quote:Original post by fractoidQuote:Original post by Nice CoderSorry, poor choice of words. I meant use a heuristic-but-relatively-time-consuming-compared-to-greedy algorithm, of the sort on that page. Not just a naieve recursive implementation, which, as you point out, would be fine if you have a quantum computer to run it on. :P
Nice coder
Ok.
I was just getting a WTF moment.
[lol]
From,
Nice coder
Author
Quote:Original post by Nice Coder
How many is a 'few'?
(i've got an idea. But it all depends on how many things there are to search.)
From,
Nice coder
what do you mean with "how many is a 'few'"?
Ok. 11 items. (10 pils, one powerpill).
You could get a path in a few miliseconds.
ok 11! = 39,916,800
Which is doable in 30 seconds. (you have 40M nodes to search).
Just as long as it doesn't increase (one more item, and you in the 400Mitem mark. WHich is a little heigh. Two more and your in the billion item mark).
Ok, assuming 1Billion instructions per second.
You have 30 seconds.
So 30billion / 39,916,800 = 751 instructions per node max.
From,
Nice coder
You could get a path in a few miliseconds.
ok 11! = 39,916,800
Which is doable in 30 seconds. (you have 40M nodes to search).
Just as long as it doesn't increase (one more item, and you in the 400Mitem mark. WHich is a little heigh. Two more and your in the billion item mark).
Ok, assuming 1Billion instructions per second.
You have 30 seconds.
So 30billion / 39,916,800 = 751 instructions per node max.
From,
Nice coder
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
