Although I haven't fixed all the problem in what has already been programmed in salesman-3DIcache.c
(see Chap 4 ) , I will try to explore what could be the next step:
Saving results of duplicated subtrees due to permutations of more than 2 subsequent towns.
To remind us what it is about, let's try with 6 towns and permutation of two towns:
These to branches below yield the same result because they have the same sub-tree after town 4:
(1,2,3,4,....) and (1,3,2,4,...)
But it happen also with permutation of 3,4,.....towns.
Let see how many subtrees yield the same result with 10 towns and permutations of 3 towns:
(1,2,3,4,5,...) ;(1,2,4,3,5,...); (case A)
(1,3,2,4,5,...); (1,3,4,2,5,...);
(1,4,2,3,5,...) (1,4,3,2,5,...)
That is interesting because they are more duplications! And the number of town in the permutation can be increased by 1 at each level.
Is it worth it?
Not sure because a lot of cuts have normally been done in the previous levels! But do we need to do it at each level? I am no able to compute it and will prefer doing some experimentation. What I have seen is that the number of new duplication detected by passing from a 2 towns to a 3 towns permutation is not big. It can be estimated by listing branches at depth level 4 with simul.v1.c (root being level 0).
Another problem is the cost of saving/restoring the result of duplicated sub tree. For now I have used an array of the type [N][N][N] (N= Number of towns) and partially initialize it with town I am suppose to encounter at this level. I don't need a memory this size and further more it might become very heavy when using permutation of more than 2 towns.
So I could compute Z the real size I need and use database indexing techniques:
A first approach could be (if K is the index) K=(town1*town2*town3 )%(Z/m) and see what can be done to adjust the number of collisions (like choosing m).
Further more the CPU charge of computing K can been shared vertically because :
K= town1 % (Z/m) * town2 % (Z/m) * town3 % (Z/m)
And we finally have to do a one dim array access and sequentially access collisions.
It is interesting to see that each permutation will produce the same index because * is commutative.
Is it worth it?
So I will continue with the faith that P=NP.......
More idees:
We can have 2 differents collections of numbers having the same product (like 5*3*4=5*2*6). In order to avoid this kind of collision we could use the summe 5+3+4=12 and 5+2+6=13 to detect the collision. And 2 permutations still have the same sum because of the commutativity. (excuse me if am to basic, I just want more clarity).
so we could find a previous result due to subtre duplication with the help of a 2 dim array using both sum and product of the number-id of each town.
Tye are many questions:
Is too risky ? Can we avoid this risk?
Can we verify if it is possible up to a certain number of towns: is it possible to have 2 different collections of k numbers n, n chosen in (1,2,...number of towns), that have the same product and the same summe?
It must be possible to verify if k isn't too big because we don't have much case to generate: they are combinations. If we choose to store the result of a 10 towns permutation and if the number of towns is N then max(k)= N * N-1 *........* N-10.
Then is it again possible if we use P%m instead of P? How can we choose m? m primer?
I can't ask my wife!!!!!!!
I repeat my question: if the number ni is in the collection C1 and mi in C2, C1 and C2 having both k elements then is true that:
- [(sum of ni = sum of mi) and (product of ni =product of mi) ]<==> C1 = C2
- [m exist and (sum of ni = sum of mi) and (product of ni%m =product of mi%m)] <==> C1 = C2
? ( m is limited by the size of memory at hand on the computer)
Perhaps I should try to find a third signature of the collection C1. The other signatures are the sum and the product.
Avoiding initialisation:
how can I know I access an array for the firs time: we the use of 2 array and a pointer between the 2 arrays and a global variable:
a 2 dim array A1[][] and A2[] and a variable PA2 pointing on A2[0] after initialisation:
I want to store the result R of a subtree defined by P and S :
When I want to store, I get a new pointer on A2 : p=PA2 , PA2=PA2+1
A1[P][S]=p, A2[p]=R
If I want to know if something has already been stored in A2 after initialization.
I get p = A1[P][S] and test p>PA2.
11/05/2023
Still not found why I get sometimes a wrong result with salesman-3DIcache.c pgm!
I might have taken a wrong decision. I mean: the functional analysis might be incorrect. What I want to do might be either impossible to do or I have chosen the wrong way to do it.
Still trying to find out what is wrong by tracing what the pgm do. But it is difficult.
Whatever .... now, I need to find the error .
The result is sometime correct, depending on the problem I want to solve.
It is encouraging.
Though....
