Follwing Chap 1
To give a better idea of what could perhaps be done with a methode derived from Ec software.
We want to resolve the traveler purchaser problem with a collection of towns T={A,B,C,D......}.
(Starting from A and going through each town in T/ {A})
For each permutations P of (B,C,D...) we need to find the one with the lowest distance the salesman has to run through. We could find several one but we need only one.
One solution is run through a tree that build the permutation and at each leaf of calculate the distance for this permutation and record if it is lower that the previous one we found.
Another solution is to upload the best distance found in a sub tree and to select the best one at each level.
In this case we can see that they are duplicated subtrees. Let's compare to branches:
(A,B,C,D, Tail1......) and (A,D,C,B,Tail2)
Tail1 and Tail2 subtrees have the same collection of towns and should yield the same result.
We don't need to explore the duplication we can simply cut it and use for ADCB the result previously found for ABCD.
For a 3 towns circular permutation we can spare half the nodes at each level for n level is approximately dividing the full process by 2^n. Approximately because it is not possible for all level (deepness).
They are perhaps several ways to find the duplication at each level (deepness in the tree):
- we can use an array (created at each dive in the next level toward the leaf) and look up (B,C,D) when the previous nodes are (D,C,B). Each town being designated by a number.
- We could perhaps avoid to create a multi dim array because duplicated subtree come at a regular positions at the same depth level when using a specific permutation systeme (I show it in langage C program and its output at the end of this post ). We could build in advance an array providing for each node at a same level which node previously got the result. Or better (to spare memory) have a function for each level which provide for each node (its chronologic number) which previous node has the result. It could perhaps even be done with some quantum computer solution. I mean using a quantum computer as a coprocessor. The biggest problem is to find a way to build automatically this function for each level. It might be possible. Or we can use a build-in advance array. I will try this in a langage C program with thread. It will give an idea on the number of nodes we can spare.
But we might exploit better the full potential of this method.
because it should also work for a 2 town permutation :
for (A,B,C,tail1) and (A,C,B,tail2) tail1 and tail2 yield also the same result.
in fact we can cut each time we encounter in a tree
(A,,,X1,X2,,,,Xm, tail) and if we already recorded this circular permutation of (Xm...,X2,X1) at this level.
It is not sure we can build a program that can do this with reasonable amount of memory.
But some brains might theoretically calculate the amount of node exploration we can spare.
Does it make the salesman problem polynomial or even logarithmic?
Finally.
I'd like to excuse myself in advance in case of big error made by me in this post.
I needed to fill the pressure of writing it down.
I discovered new things doing it.
A first attempt to compute the number of node with and without cut:
Number of nodes without cut should be N=n!+(n-1)!+(n-2)!............+3!+2!
If we are able to detect sub tree duplication (in a "polynomial" way and with reasonable amount of memory) then with detection of permutation of 2 nodes in a branch from (head0,A,B,tail0) to (head0,B,A,tail0) we could lower the total amount by 2 at each level.
The new number of nodes would N2= N/(2^n)
The expressions N2 or N3.2 or Nm...3.2 are just variable name with a suffix that try to explain that we could also use circular permutations of 3,4,m subsequent nodes (m <n).
With a full optimisation it is difficult (for me) to count how many nodes with spare on the entire tree.
And finally difficult to know if we can reach the polynomial or logarithmic target this way.
I tried to see what I can spare mixing 3 and 2 town permutation optimisation with a branch-head of
4 towns: I got only 6 subtrees I need to really explore instead of 24.
If we do it at (n-m) levels we ca reduce the total number of nodes to N3.2 = N/(6^n)
If we mix m ,m-1, .....3,2 town permutations optimisation we would get something like:
Nm.(m-1)...3.2= N/(X^m) but I don't know X.
The expression for the dénominator must be much more complicated.
The hope is we can choose m so that X can be near enough of n without inducing a to high CPU/memory cost.
But it could still be useful for pure theoretical solution.
I will try an experimentation with Pthread... a good opportunity to work again with C language and learn Pthread.
This a a first "dirty" version of the salesman programm without cut but ready for its implementation.
Just to show how the permutations are generated.
The full directory can be found on
Google Drive . It is interesting is to study the list of all routes generated by the program and mark the permutations having the same collection of towns in a a subtree. Town are numbers in the program.
We can see on this output of the programm that, if a list of more than 5 towns was used, duplication of permutation of two towns (green) and three town (red) would allow us to explore only 6 subtrees.
But it is also very interesting to see the regularity at which green and red hyphens appear. It means that we could perhaps avoid to use a three dim lookup but only one dim. This one dim being the
sequence at which nodes apper at the same depth level.
A new version of salesman.c has been made that seems to work much better in Chap 3 .
