CEMETECH
Leading The Way To The Future
Login [Register]
Username:
Password:
Autologin:

Don't have an account? Register now to chat, post, use our tools, and much more.
Latest Headlines
Online Users
There are 68 users online: 1 member, 55 guests and 12 bots.
Members: chickendude.
Bots: MSN/Bing (2), Magpie Crawler (2), Googlebot (8).
RSS & Social Media
SAX
You must log in to view the SAX chat widget
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 General 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.

This forum is locked: you cannot post, reply to, or edit topics. General Coding and Design => General 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
Display posts from previous:   
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
   
View previous topic :: View next topic  
Page 1 of 1 All times are GMT - 5 Hours

 

© Copyright 2000-2014 Cemetech & Kerm Martian :: Page Execution Time: 0.024171 seconds.