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! 

REDMI 8A

Après avoir appuyé sur  l'icône SMS j'attends 18 secondes avant de voir apparaître la liste des SMS.

Il me semble très probable quelqu'un a décidé que je devais acheter un nouveau smartphone. 

P=NP (chap2)

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.    

But we might exploit  better the full potential  of this method.

because it should also work for a 2 town permutation :

for (A,B,C,tail1)  and (A,C,B,tail2)  tail1 and tail2 yield also the same result.

in fact we can cut each time we encounter  in a tree 

(A,,,X1,X2,,,,Xm, tail) and if  we already recorded this circular permutation of (Xm...,X2,X1) at this level.

It is not sure we can build a program that can do this with reasonable amount of memory.

But some brains might theoretically calculate the amount of node exploration we can spare.

Does it make the salesman problem polynomial or even logarithmic?

Finally. 
I'd like to excuse myself in advance in case of big error made by me  in this post.

I needed to fill the pressure of writing it down.

I discovered new things doing it. 

A first attempt to compute the number of node with and without cut:

Number of nodes without cut should be N=n!+(n-1)!+(n-2)!............+3!+2!

If we are able to detect sub tree duplication (in a "polynomial" way and with reasonable amount of memory) then with detection of permutation of 2 nodes in a branch from (head0,A,B,tail0) to (head0,B,A,tail0) we could lower the total amount by 2 at each level.

  

The new number of nodes would N2= N/(2^n)

The expressions N2 or N3.2 or Nm...3.2 are just variable name  with a suffix that  try to explain that  we could also use circular permutations  of 3,4,m subsequent nodes (m <n).

With a full optimisation it is difficult (for me) to count how many nodes with spare on the entire tree.

And finally difficult to know if we can reach the polynomial or logarithmic  target this way.

I tried to see what I can spare mixing 3 and 2 town permutation  optimisation with a branch-head of  

4  towns:  I got only  6 subtrees I need to really explore instead of 24.

If we do it at (n-m) levels we ca reduce the total number of nodes to N3.2 = N/(6^n)

If we mix  m ,m-1, .....3,2 town permutations optimisation we would get something like:

Nm.(m-1)...3.2= N/(X^m) but I don't know X.

The expression for the dénominator must be much more complicated.

The hope is we can choose m so  that X can be near enough of n without inducing a to high CPU/memory cost.

But it could still be useful for pure theoretical solution.

I will try an experimentation with Pthread... a good opportunity to work again with C language and learn Pthread. 

  

This a a first "dirty" version of the salesman programm without cut but ready for its implementation.

Just to show how the permutations are generated. 

The full directory can be found on Google Drive . It is interesting is to study the list of all routes generated by the program and mark the permutations  having the same collection of towns in a  a subtree. Town are numbers in the program.

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 . 

Brother HL2135w

J'ai pourtant été fidèle à la marque en prenant soin d'acheter des toners de la marque et même de racheter une deuxième imprimante couleur de de la même marque car j'étais content.

J'essaye donc d'imprimer un PDF en recto verso pour économiser du papier. Et je n'y arrive plus avec W11. Je vérifie la mise à jour des pilotes: tout est à jour.

Je dois donc investire en temps de formation pour trouver une solution ou décider de ne plus utiliser une imprimante en parfait état de marche mécanique pour pouvoir économiser du papier.

Obsolescence programée?

P=NP Demonstration. Chap 1

It might be possible  that the langage C module named hash.c  used in the chess engine  Ec could help to resolve the question P=NP with a yes.

I don't have all the knowledge and capacity to expose the reason here. But I will try to see if this module and the way I explore the  chess-game tree in Ec could be used  in a similar manner to resolve a NP-complete problem: the Traveling purchaser problem.

What I think is: if I show  that the resolution can be obtained in polynomial time or even in logarithmic time then the demonstration of P=NP would be partially resolved.

But I am old and not well educated. So I might be wrong.

To help to understand what is done in EC with the module hash.c:

hash.c allow to save and retrieve the result of a tree below a  node named C (deep-level=n) that the engine reached after node A  (deee-level=n-2) and B (deep-level=n-1). I would name this situation (A,B,C) So the engine might have before encountered and saved situation (C,B,A).  C at deep level n-2, B at n-1 and A at n. 

From the point a view of chess and the way the result is transferred up from bottom tree,  (A,B,C) is generally equivalent to (C,B,A) (not equivalent if a chess piece is taken). That assumption might be also be challenged. I Am not completely shure. I took great risks. But It might be easier to verify it with the Traveling purchaser problem.

So now I need to build the program with  a kind of  Ec method to resolve the Traveling purchaser problem in -I hope - a logarithmic time.

Chap 2

Problemes d'affichage avec Google Map , Chrome et Windows 11 et un Lenovo Tiny M700

Cela fait une ou deux semaine que cela arrive parfois avec W11.

Lorsque j'ouvre un fenêtre  avec chrome pour  visualiser  une carte avec Map j'ai des problèmes d'affichage:  la fenêtre s'affiche alternativement à plusieurs endroits en flashant. J'utilise un Lenovo Tiny M700.

J'avais fait une recherche sur Google avec "Caroline Du Nord" puis j'ai cliqué sur la petite carte à droite qui est un lien sur Google Map.

Cela ressemble plus à un problème de driver. Mais pourquoi donc le problèmes d'affichage n'est pas reproduit avec d'autres applications?

C'est peut-être tout simplement une panne intermittente  du M700.  

En fait cela semble être une panne de l'adaptateur Display-Port vers HDMI. 

En fin de compte et après avoir acheter un nouvel adaptateur display port vers HDMI, je conclue à un arrêt de la prise en charge par W11 d'un écran DGM en HDMI:

C'est écran marchait sur la prise HDMI il y a encore quelque jours. J'ai testé la partie hardware:  câble et  sortie HDMI.  En testant l'écran ne fonctionnant plus (marque DGM) en HDMI sur un autre PC, puis en utilisant un écran qui marche en HDMI ( marque SAMSUNG) sur la machine Windows 11. Ma conclusion là plus probable  est que le problème est purement logiciel et que le driver a été supprimé. Si cela n'est pas un erreur de la part de Microsoft alors je reprouve ce choix qui encourage la surconsommation. Je dois utiliser VGA pour pouvoir encore utiliser mon écran DGM alors qu'il marchait en HDMI avant.

Prolog le langage

 J'avais dans ma jeunesse expérimenté turbo prolog. J'ai réessayé récemment d'utiliser sans succès une version récente de turbo prolog qui existe toujours.

Puis j'ai essayé Swi-prolog. 

Après quelques expérimentations plus fructueuses qu'avec turbo prolog je me pose certaines questions.

Comment se fait-il qu'un langage aussi fascinant que prolog soit aussi difficile à utiliser.

On a un terminal qui  permet d'interroger la base de donnée.

Mais!

• Si on ajoute des faits, ils ne sont pas mémorisés de manière permanente. On est obligé de modifier le fichier source du programme.
• Si on veut ajouter une règle il faut aussi modifier le fichier source du programme.
• On a pas le moyen standard de stocker dans une base de donnée comme Sqlite.

Pour moi l'idéal serait de d'avoir un fichier source de base et un autre qui s'aliment automatiquement avec les modifications que l'on fait de manière interactive. 

Mais c'est peut-être infaisable. 

Je n'y ai pas beaucoup réfléchi.

Je verrais bien un module python qui permettrait de faire des requêtes de type prolog sur une base de donnée de type SQL.

Ca existe?

De toute façon j'en ai pour un bon moment avant de comprendre comment prolog fonctionne.