P=NP chap 5

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....