vendredi 28 avril 2023

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

  





mercredi 26 avril 2023

P = NP Chap 4

In the previous Chapter 3 , I have explained that I got a bad surprise trying to avoid initialisation and use sequence nodes numbers to save and retrieve results from  duplicated subtrees: When cutting some sequence disappears and  what was the initial location for the result doesn't exist anymore and you need to dive when not expected.  I tried several solutions and it hasn't work. Hope not  completely lost.

I fell back to memory initialization with the pgm <salesman-3DIcache.c> . I got a results that sometimes doesn't fit the reference (12 towns). I need to find the bug. 

Generated datas can be verified with the help of the pgm <salesman.v1.c> that is making the computation in a simple way at leaf. In salesman-3DIcache.c I only compute the best distance. It was simpler to verify if it is working.

All new datas (make and several sources) can be found in drive salesman2 and the old in salesman.

This is the pgm salesman.v1.c: a reference used for verifying data out of salesman-3DIcache.

The next source below is  the pgm salesman-3DIcache.c: an attempt to cache datas and cut duplicated subtrees. It is bugged!!

This version use permutations of 2 towns. I think that in order to get polynomial result, we need to use permutations of much more towns. I haven't yet really worked on P/NP  evaluation of this pgm version: I am still busy trying to debug it. But I am still thinking to the future. How will I compare two permutations?  Perhaps by ordering the part of the branch nodes from root to the current node and  inserting at each level a new  town in the ordered list. Explanation:

I have 10 towns {0,1,....9}. Considering a branch described from root to leaf by (0,3,1,2,4...9) we could do:

  • level 0 we get (0)
  • level 1 we order   (0) + 3 ang get (0,3)
  • level 2 we order (0,3) + 2 and get (0,2,3)
it would allow us to share cpu time for the ordering between several nodes horizontally and vertically.
It would be nice to find a solution to also share  horizontally and vertically the CPU time needed to access a multidimensional array..........


mercredi 19 avril 2023

Fdj et nouvelle crise de paranoïa.

Je joue une fois par mois au Lotto ou à Euromillion pour environ 2,5€.

J'ai joué avec Euromillion le weekend dernier (mi avril ) pour un tirage le mardi. Enfin je le croyais car lorsque j'ai voulu consulter le résultat, l'historique ne comportait pas de trace de ce paris. J'ai donc probablement oublié de valider le jeux après avoir choisi les numéros.

Mais en y pensent à nouveau je suis pris de doute et je consulte le résultat du tirage. Je joue toujours les même numéros. J'aurais dû gagner ....6€.

Bon ça va. Je ne suis pas passé à côté de la fortune.

Mais en y repensant je trouve dommage que l'on ne puisse pas imprimer à la maison un ticket qui ait une valeur juridique ou d'avoir une confirmation du pari par email.

Car quelle preuve a-t-on si veut faire un recours devant le justice?

Il faudrait mieux valider chez le buraliste alors? .... Mais il doit y avoir aussi d'autres risques ....Je pense.

Si je joue c'est que je crois qu'il ne faut pas hésiter à laisser la chance -même infime- s'exprimer.

Si cela est pour une bonne cause bien sûr!

Pourquoi laisser cet argent à d'autres? 

Cela fait environ 30 € par an plus le temps passé une fois par mois.

Voler 2,5 + 6 euros, ça c'est la nouvelle forme qu'à pris le crime organisé. Le faire avec 100 milles voir un million de personnes ça commence à être intéressant. 

Et c'est peut être moins risqué que de voler une voiture!

Mais ça demande plus de savoir faire.

Peut être en utilisant des Pcs vendu d'occasion?  

mardi 11 avril 2023

Paranoïa informatique

 En ce moment j'ai beaucoup de soupçon concernant le fonctionnement de mes machine online et offline équipées avec linux ou window. 

Il est bien sur possible que ce soit une illusion et que je sois le seul responsable.

Mais j'ai l'impression que des données ont été supprimées à plusieurs reprise. Et je me demande si cela n'est pa dû aux disques ssd. 

Qu'est ce qui pourrait bien justifier l'emploi de tels moyens?

Ce que je crée a-t-il une réelle valeur? 

Cela vaut-il le coup de le voler?

Il y a toujours des gens pour prétendre qu'ils veulent me protéger. 

Mais à partir du moment ou ils utilisent le criminalité, j'ai le droit de me demander s'ils sont sincere et s'il ne cherchent pas à simplement calmer le jeux au moyen d'une attitude ambigüe.

Il y a peut-être des méthodes qui permettent de me protéger sans m'espionner voir me voler.  

Elle pourrait compléter l'approche criminelle.

Pourquoi ne m'avoir pas conseillé directement?


 

dimanche 9 avril 2023

Microsoft W11

 sur  un machine achetée d'occasion dégradation progressives du fonctionnement:

  •  Perte de donné sur usb.
  • Dans le gestionnaire de fichier plus d'indication taille des fichier en mode détail, verrouillage de fichiers et impossibilité d'imprimer ou supprimer. 
  • Très faible performance de WSL et pas de support INTL.
  • Perte de fonctionnalité sur driver imprimant Brother HL2135W plus de support recto/verso.

samedi 8 avril 2023

HUAWEI B525 LTE reglo mobile et reseaux SFR 4G

 Cela fait déjà environ une semaine que j'ai des problèmes avec cette box 4G. La diode d'état de la connection passe au rouge et il n'est plus possible de communique sur internet. Mais la ligne téléphonique semble encore marcher. 

Le seul remède que j'ai trouvé c'est de débrancher le câble d'alimentation. Une simple mise hors/sous tension est insuffisante. 

Je soupçonne une attaque sur mon IP et le dépôt d'un virus en RAM dans la boxe. Cela m'est arrivé aussi quelque fois avec un PC. 

Peut-être une faille de sécurité de la box 4G HUAWEI B525 qui pourrait  peut-être être corrigée si elle n'était pas n'était pas quasi obsolète. Elle marchait bien sinon 130Mb/s quand le réseau 4G n'est pas saturé. Le seul bémol c'est l'incapacité de surfer en cours de communication téléphonique. Mais c'est la même chose avec  mon smartphone.

vendredi 31 mars 2023

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!