P=NP Chap 3

  Following :   Chap 2

This provide a correction of the salesman.c program that was partially  functional  (the bugged version has been renamed to .salesman.sv1 in Drive ).

This new version select the new best route  (having lowest distance) at each node.

This is the first step in order to be able to store and reclaim the best branch of a subtree (route and distance) and cut duplicated subtrees.  

It has been painful!

A new explanation for duplicated subtrees. (new in this post of course!).

If the town p is at depth level m (root being at 0 and leaf being at n) then we can count the number of duplication:
We have (m-2)! permutation of (a1,a2,.....ak) and k = m-2.
But how much branch or how much node do we have at level m?
It seems to me that it is the number of permutation of (m-1) element taken from n elements:
n! / (m-1)!.
And the number of unique sub-trees at depth level m would be n! / [ (m-2)! (m-1)! ]
Even if it is True mathematically (I am not very good!) then I find it very difficult to evaluate the total number of nodes we really need to go though.
But if the calculus is done it could give us a proof that there is no way to try to resolve the salesman problem in polynomial time using this method.
I will try to get an idee of what I can spare experimentally.
But the amount of memory and CPU time needed to exploit the full potential of this theory might counter-balance the gain.
That is why I will try to count it with the salesman program using duplication detection for a small amount of town at each depth level.
If I am able spare some time then, it could still be useful.
Not for the P=NP problem.

What ever I am not desperate to find another method to resolve the problem quickly. It might be an incentive to learn Quantom computing. I am not very well advanced  in this topic. But I hope I will have enough time.... now that I am retired. 

If I have some time left I will also try to learn big data.I know nothing about it. But ..... I don't know .... I could make a barycentre of the town and try to guess the optimized distance.......

Last news 2023/04/09:

lets define seq2 = f ( dl , n , seq1 ) 

dl = current depth-level ; n = total number of towns. 

 seq2 >= seq   

seq is the current chronological sequence number of a node at the same depth level. 

seq2 is the sequence number  of a previous node that has an equivalent subtree.

if seq2 = seq1 it means that we  are encountering for the first time a permutation and we must store the result given from exploring the subtree below the current node 

if seq2 < seq it means we have already store the result and just have to restore from an array (A[seq2])

I think it is reasonably likely that I will find a f() that will eliminate half the nodes (due to two towns permutations in  the branch above the current depth level). It might be la little bit complex but it will allow us to avoid to memset the cache when diving and avoid to access multi-dim array that need to be at each depth level [n][n][n] for a 2 towns permutation. We will still  have to store the best route and the best distance.

I'll publish it if I can get it.

I already have a  f()  that is able to say if have to store. But I need to make further tests before publishing. 

I still need f() to be able to return the sequence node where a previous  result has been stored but I got today some clue it is possible.

2023/04/23 :

After starting to build on it I have discovered that it doesn't always work well: I don't store or save a node result at the right time! Too much risks taken! hope to find a correction. It should still be possible to save restore but with the use of large quantity of memory initialisation with memset. If I can't correct it I might have to fall back to memory initialisation.

First explanation is that, due to cuts, nodes sequences (on the same depth level ) do not correspond to the same permutations and it doesn't save or restore at the right time.  But !! It might be compensated because permutations seems to stay in the same order. They are just regular holes in the sequences. I 'll give it a try by  incrementing "artificially"  the nodes sequence number. 

I hope I will be lucky. It doesn't bother me if I am. Though. I don't mind getting some-free help! 

If the holes in sequences fit the permutations already found!

Idiots usually don't get as much luck as smart ones...... No free-some then!