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.
I'd like to excuse myself in advance in case of big error made by me in this post.
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 .
