This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's
Calculator Programming subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.
General Coding and Design =>
Calculator Programming
| Author |
Message |
|
Harrierfalcon
The Raptor of Calcs
Super Elite (Last Title)
Joined: 25 Oct 2006
Posts: 2535
|
 Posted: 20 Jan 2009 07:26:58 pm Post subject: |
|
|
This subforum needs HAYULP.
But that's besides the point. Through a WoW addon, I came across Ant Colony Optimization, which is what Wikipedia calls a "metaheuristic algorithm" created to help solve the Traveling Salesman Problem.
Since then, I've been implementing this into a Python program, but...I think what I'm doing is somewhat problematic.
What you have to do...well, what I think you have to do is to have a list with one element for every path, to keep track of the pheromone level on that path. But, what this means is you have to have one element for every possible path...and the number of possible paths is the factorial of the number of nodes.
Unfortunately, this quickly becomes impractical. For eleven nodes--only eleven--you would need a list with 39,916,800 elements.
So...am I wrong in thinking that the number of possible paths is the factorial of the node count? Or is there definitely a more efficient way to do this?
EDIT: OK, it's not the factorial, which is the product of all numbers leading up to it...it's the sum of all the numbers leading up to it. Anyone know the name used to reference this?
EDIT2: All right, I've got to work on stuff more before I ask about it. This helped me come up with .5((L-1)2+L-1.
Last edited by Guest on 11 Jul 2010 06:45:38 pm; edited 1 time in total |
|
| Back to top |
|
|
luby
I want to go back to Philmont!!
Calc Guru
Joined: 23 Apr 2006
Posts: 1477
|
| Posted: 21 Jan 2009 09:08:33 pm Post subject: |
|
|
| RE: Edit #1 I know that in Calculus we call it Riemann sum when you add all the numbers from 1 to N Hope this helps |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 22 Jan 2009 12:34:19 pm Post subject: |
|
|
"it's the sum of all the numbers leading up to it. Anyone know the name used to reference this?"
I always referred to them as triangular numbers. :)
As to doing TSP... just to inform you of alternatives, "differential evolution" and "simulated annealing" are pretty stiff contenders as well, you might wish to look into them too.
thornahawk |
|
| Back to top |
|
|
Harrierfalcon
The Raptor of Calcs
Super Elite (Last Title)
Joined: 25 Oct 2006
Posts: 2535
|
| Posted: 26 Jan 2009 08:49:38 pm Post subject: |
|
|
Just finished the program, and it works for the most part. Instead of actually randomizing the path though, it just takes the path that has the highest probability of being chosen. Probably not the best thing, so I'm probably going to try and adapt it to do that.
I'll take a look into differential evolution and simulated annealing though...maybe they'll be more consistent than ACO, thanks guys. |
|
| Back to top |
|
|
|
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
