I have been experimenting with a 2.2" tft I got from ebay, and I'd like to have my uno minimize the distance between several random points on the screen (the traveling salesman problem). There are a couple of different algorithms, but the brute-force algorithm needs the Arduino to calculate all the possible connections and draw them. Is there an algorithm for generating all the possible sequences of points?
IIRC, solutions to the TSP require recursion which causes a lot of activity on the stack. A 328 Arduino has 2kB of sram for local variables and the stack. You're going to be very limited in the number of nodes a graph can have without crashing the processor due to stack overflow.
Pete
I'd like to have my uno minimize the distance between several random points on the screen
Given that the distance from any point to any other point is going to be a constant, how do you propose to minimize a constant?
PaulS:
Given that the distance from any point to any other point is going to be a constant, how do you propose to minimize a constant?
Perhaps you should Google "travelling salesman problem" so you understand what he's asking? It was perfectly clear to me, and obviously others...
Regards,
Ray L.
I tried to think of a recursion-type function that used nested for() loops, but it made my head spin 
.
How many points are there? The amount of nodes will substantially increase the memory footprint as they increase. Can't help but feel a tree like structure would be your best friend, and yet take up way too much memory.
The number of possible paths grows very large as you go up (n!), but I would only need less than 16 or so. I also have an mbed board with 256k of RAM - is this enough?
is this enough?
For what? You still haven't described what you are trying to do.
There is a lot written about the TSM problem.
algorithm 1:
generate all permutations, determine the length per route and keep the shortest
base algorithm: stringlength 10 takes 52 seconds.
//
// FILE: perm1.pde
// AUTHOR: Rob Tillaart
// DATE: 2010-11-23
//
// PUPROSE: demo permutations
//
char permstring[12] = "123456789A";
void permutate(int n)
{
if (n==0) // end reached print the string
{
//for (int i = 0; i < strlen(permstring); i++)
// Serial.print(permstring[i]);
//Serial.println();
return;
}
for (int i = 0; i <n; i++)
{
// swap
char t = permstring[i];
permstring[i] = permstring[n-1];
permstring[n-1] = t;
// permutate substrings
permutate(n-1);
// swap back
t = permstring[i];
permstring[i] = permstring[n-1];
permstring[n-1] = t;
}
}
void setup()
{
Serial.begin(115200);
Serial.println("perm1");
unsigned long time = millis();
permutate(strlen(permstring));
time = millis() - time;
Serial.print("TIME: ");
Serial.println(time);
while(1);
}
void loop()
{
}
The amount of time rises to more than exponential O(n!)
11 chars => ~10 minutes
12 chars => 2hours
13 chars => 1 day
14 chars => a fortnight
15 chars => more than a year
A far faster heuristic algorithm is to start with 1 place.
Then add that place from the list of not visited places that gives the least increment of the total route so far.
you do that until all places are added.
This algorithm does not guarantee to generate the shortest route, but it does generate a reasonable short distance in short time. Complexity is O(n^2). The generated route can be further optimized (fixes some known errors) in 2 ways:
-
given the generated route, check if reversing a sub-route shortens the route. In a picture this will remove crossing paths.
-
given the generated route, remove one place and insert it again in the route in that place that gives the least increment.
This will not guarantee an optimal route but you will have a quite close one.
The above algorithm you can find an almost optimal route with many places. For performance reasons one could create a 2D distance table which takes a lot of space. An UNO with about 1600 free bytes can hold a matrix for 30x30 places (float = 4 byte distance) as you need only store the half of it. (an exercise in itself)
A very simple, brute force algorithm should not need to be terribly RAM intensive for any reasonable number of points. The recursion depth should be no more than the number of points, so should be quite manageable in this case. You also keep only the best result yet seen after after evaluating each iteration, so little RAM use there as well. The disadvantage is it would be slow for a large number of points, but 16 is not a large number of points, so should easy to do even on a smaller Arduino.
Regards,
Ray L.
PaulS:
For what? You still haven't described what you are trying to do.
Read the original post??
They want to implement the TSP on an arduino and are here discussing it, seeing if anyone else is interested in the same kind of thing and/or has done so previously. In that regard, things seem to be working out for them.
Now to belabour your own question (or should I say, 'point'):
how do you propose to minimize a constant?
A minimised constant is itself. It could be seen as a part of a larger set, in that case, google 'find the smallest element in an array'.
But I know you know that, which leaves me wondering >> what exactly are you doing here ?
There is a certain type of member here that loves calling out captain obvious, being master of mega-terse-engineering, 'define your terms'-man - maybe you appreciate that, I sometimes do myself, all good... But anyway, my point is that I don't think that approach particularly suits you.
RayLivingston:
A very simple, brute force algorithm should not need to be terribly RAM intensive for any reasonable number of points. The recursion depth should be no more than the number of points, so should be quite manageable in this case. You also keep only the best result yet seen after after evaluating each iteration, so little RAM use there as well. The disadvantage is it would be slow for a large number of points, but 16 is not a large number of points, so should easy to do even on a smaller Arduino.
16 points (with a fixed start/stop point) will give 15! possible routes divided by 2 (to remove mirror identical)
15!/2 = 653.837.184.000 possible routes.
If the Arduino could evaluate 1 every uSec -> 653837 seconds ~7.5 days.
The recursive permutation program I posted #8 would need in the order of a year to evaluate all of them.
You can rewrite the recursive algorithm into an iterative one, that would reduce the function call overhead at the price of keeping your own stack. The algorithm has no evaluation function (calculate the length) yet so in the end you might gain a factor of 2 max I expect (but please prove me wrong 
You can optimize the code by doing the length evaluation after adding the next point. It the length sofar is longer than the shortest so far you can start backtracking. This will prune a whole branch of the solution space and will give in most cases a substantial improvement in performance.
follow up of #11 above
Another heuristic algorithm that works quite well is to start with one point and add that point to the route that has the largest minimal distance from the route so far. The you add the next etc until all points are done.
The strength of this algorithm is that the 'area of points' is covered very quickly thereby reducing the distance of every (not yet placed) point to the path quite fast.
Another heuristic way is to generate a random route and apply optimization functions (as described above). If it is shorter keep it, otherwise generate a new random one.
One can also apply a genetic algorithm and generate a lot of routes (as RAM can hold) and cross breed the best of them, search for common pattern.
For each point you calculate the distance to all other points and store results (or weighted value depending on length to reduce variable type size?). 16x15 = 240 bytes. Then go through the 16 arrays of 15 elements and add up all the permutations and note/keep the one with the lowest length?
Would work, however generating all the permutations is the real (time consuming) problem.
During my study I worked on the TSM problem and had a theory that only the 6 shortest distances per column in the distance table are relevant. The number 6 comes from the pattern of all triangles / honeycomb and would be true in a 2D world of points. In a 3D world that number would be higher (12?) Never finished it as other school tasks had more prio.
If this lemma would be true the problem would drop in complexity from O(n!) to O(6^n).
I realize that the Arduino isn't the fastest or has the most processing power, but I don't really care. I mostly had it in mind as a project that I could get credit for (I'm 15), but also because I think math and algorithms are fun . Like I mentioned before, I have an mbed board (specifically the FRDM-k64F) that has 256k of RAM and an M4 + FPU processor clocked at 120MHz. I appreciate (really!) everyone's input, but do any of you have ideas how you could translate these ideas into actual code? Again, thanks for spending time with my useless project!
I did a quick search on Wikipedia and found a two algorithms that can do what I need:
Here's what I have written based on Heap's algorithm (but it doesn't work):
unsigned int a[9] = {0, 0, 0, 0, 0, 0, 0, 0, 0};
void setup(){
Serial.begin(115200);
generate(8, a);
}
void loop(){}
void generate(unsigned int n, unsigned int *array){
if(n = 1){
for(byte i = 0; (i < sizeof(array)) && array[i] != 0; i++){
Serial.print(array[i]);
}
Serial.println();
}
else{
for(unsigned int i = 0; i < n; i++){
generate(n - 1, array);
if(n % 2 == 0)
swap(array[i], array[n-1], a);
else
swap(array[0], array[n-1], a);
}
}
}
void swap(unsigned int index1, unsigned int index2, unsigned int *array){
array[index1] = index2;
array[index2] = index1;
}
robtillaart:
If this lemma would be true the problem would drop in complexity from O(n!) to O(6^n).
And you'd be a millionaire ?!
CWashburn:
Here's what I have written based on Heap's algorithm (but it doesn't work):
I have done a Google search and found a simple TSP optimizing code on this page.
The code I refer to is in the answer rated '-2' posted by Mustapha Oldache.
With a few changes you can make the code work even with an Arduino UNO.
I have tested it with the 10 cities distance map and got a "running..." time of about one second for finding the result.
I don't know, how good the result is, as this code does not take much care on finding a "good initial solution" before starting the optimization. So maybe much better solutions may exist.
But at least, the code requires little resources. The 10 cities example tells me compiling for UNO board:
> Global variables use 504 bytes (24%) of dynamic memory,
> leaving 1,544 bytes for local variables. Maximum is 2,048 bytes.
And as there is no recursion used in the code, but all required 'stack' and 'queue' arrays are defined as static arrays initially, the algorithm does not require much additional RAM during runtime.
Perhaps give it a try.
If you have problems adapting the original code to Arduino, please let me know and I could post a code version that compiles and runs on Arduino UNO.