Shortest Path Algorithm

[Darrier]

Hey guys. I have a project to do in a couple days about shortest path algorithms. Now the thing is , i'll be using logic to do the math in the algorithm , which is actually quite easy to understand however i have to do it in matlab. The problem is , i must be showing all the possible routes like X1*X2+X3 which means 1 route is X1->X2 the other is just X3. In matlab the program wants me to define every variable as you possibly know but if i define those variables with 1's and 0's it is very unlikely for me to see all the possible routes . So i was thinking if there was a way to show the routes in letters , rather than numbers.

 

[mingzai]

Try google "Ant colony optimization" this might help you. I quoted some of the wikipedia search result and some of my thoughts here:

The algorithm mimic the way an ant find the shortest path. Lets start with an ant, first, the ant will traverse through all the required points randomly.

1. It must visit each point exactly once;
2. A distant point has less chance of being chosen (the visibility);
3. The more intense the pheromone trail laid out on an edge between two cities, the greater the probability that that edge will be chosen;
4. Having completed its journey, the ant deposits more pheromones on all edges it traversed, if the journey is short;
5. After each iteration, trails of pheromones evaporate.

"pheromone trail" can be modeled as just a number. e.g. consider point 1,2,3: possible "trails" are:
1->2, 1->3, 2->1, 2->3, 3->1, 3->2.
Use more than 1 ants per iteration, the shortest path tends to be passed-by by more ants. and paths used by more ants will deposits more "pheromone" and more ants will tends to use the path will more "pheromone". after some iteration, the solution will converge to a "shortest path" and this will be the result of the optimization algorithm.