FR 3041799 A1 20170331 FR 1502012 A 20150928 1 Introduction. En mathématiques (et donc en informatique), il existe une catégorie de problèmes que l'on nome NP-Complets (NP-difficiles), car, leur résolution est complexe et nécessite en général un calcul d'une complexité de type kPAN. Avec par exemple P comme dimension de l'espace du problème, N autre dimension dans le problème (nombre d'échantillons...). La documentation et les recherches sur ces problèmes est abondante, en effet, ce type de problème est le cauchemar des mathématiciens et des ordinateurs dès que N va croissant. L'un des exemple typique des problème NP-Complets est celui du « voyageur de commerce ». C'est pour ce problème que nous proposons une solution linéaire pour trouver du premier coup la solution idéale, sachant qu'il est établi que si un problème NP-complet ( ou NP-difficile) dispose d'une solution (polynomiale ou linéaire), alors tous les problèmes NP-Difficile peuvent également être résolus en temps polynomial ou linéaire. L'algorithme proposé que l'on nome « spirale Leafar », consiste tout simplement à superposer au « nuage » de points représentant les villes, une spirale de Fibonacci ( spirale croissante de ration y) de placer le centre de cette spirale sur le centre de gravité du nuage de points, puis de la faire tourner selon une méthode particulière. Dès lors, le chemin idéal peut-être facilement construit en parcourant la spirale et en « collectant » les points de part et d'autre, dans l'ordre d'intersection avec la perpendiculaire à la tangente à la spirale au temps t, à la condition qu'il ne soient pas plus près d'un autre bras spirale. Cet algorithme est récursif, car, à partir de 4 points (ou plus) remplissant certaines conditions de densité locale, on assiste éventuellement à la formation d'un « amas » local, qui nécessite d'être traité lui même comme un sous problème, avec sa propre sous-spirale, ensuite reliée à la macrospirale mère. Ainsi, n'importe quel ensemble de points en apparence chaotique peut être organisé en une « fractalisation » parfaite selon le motif de la spirale de Fibonacci. L'algorithme est décrit pour un exemple type : problème du « voyageur de commerce » en 2 dimensions, mais il est applicable à tout problème NP-Complets, à condition de pouvoir définir un une norme pour un vecteur, et un angle entre deux vecteurs dans l'espace R.N- 3/23 3041799 2 Définition du problème du « voyageur de commerce ». Le problème du voyageur de commerce est le suivant : étant donnée N villes réparties aléatoirement dans un plan, et toutes reliées entre-elles par des routes, quel trajet doit emprunter le voyageur de commerce pour visiter toutes les villes, en effectuant le minimum de kilomètres. Illustration 1: Problème du voyageur de commerce, villes et routes. Note : il existe des variantes du problème où toutes les villes ne sont pas nécessairement reliées à toutes les autres par un segment de route (c'est d'ailleurs le cas dans le monde réel en général), mais ceci n'est qu'un sous-problème du problème plus général. En effet, on comprend bien que la suppression de route ne fait que simplifier la complexité du problème et le nombre de solutions à explorer. Encore une fois, rappelons que que si 1 problème NP-complet a une solution, ils en on tous une, car ils s'y rapportent. Dans cet exemple, l'espace du problème est à 2 dimensions, chaque ville Pi (xi, yi) étant défmie par un point dans RxR. N=5. Bien sur, le meilleur chemin se trouve intuitivement à l'oeil nu pour un si petit nombre de ville, mais pour un grand nombre... 4/23 3041799 3 Algorithme de résolution par méthode « spirale Leafar » L'algorithme va être présenté de façon visuelle et géométrique, car il n'est pas nécessaire d'utiliser un ordinateur (un feuille de papier calque suffit ;-) ) mais bien entendu, il peut être transposé en n'importe quel langage informatique pour des données plus nombreuses. 3.1 Initialisation 3.1.1 Données du problème Voici un échantillon aléatoire de 10 villes. Villes X Y V1 85 79 V2 8 48 V3 -53 51 V4 -20 18 V5 23 -6 V6 -84 -9 W 59 -11 V8 -46 -48 V9 -50 -51 V10 55 -78 Pour commencer, on représente l'ensemble des « villes » du problème dans le plan Euclidien. 5/23 3041799 V1(85.79) V3(8,48 V3( -53.51 V4(-20,18) \T5(23. V6(-84,-9 V7( 9 -11) V8(-46,-48) V9( 50. 51 V10(55.-78) Illustration 2: exemple aléatoire avec 10 villes Ce simple exemple comporte déjà 9^9 solutions possibles... 3.11 Calcul du centre de gravité du nuage On va ensuite calculer le centre de gravité de ce « nuage ». Dans notre problème, toutes les villes ont le même « poids », mais un problème où les villes auraient une pondération variable n'est qu'une variante. G(Xg,Yg) = ( /xi/10, Eyi/10) = (-2,3,-0,7). Il est assez prêt de l'origine O choisie, mais si l'on avait placé l'origine en bas à gauche, le centre de gravité G aurait été à la même position donc plus distant. 6/23 3041799 3.1.3 Positionnement primaire de la « spirale » de Fibonacci On va maintenant dessiner dans le plan une spirale de Fibonacci. La littérature abonde de documentation sur les propriétés et méthode de construction de cette spirale. On rappellera simplement qu'il s'agit d'une spirale croissante dans les proportions de 111 = (1+-V5)/2. Pour l'implémentation informatique, le plus simple est d'utiliser la fonction polaire qui permet de tracer facilement la spirale: r(a) = exp(1/elnelira). La spirale doit être centrée sur le centre de gravité G, et on la fait pivoter autour de G, jusqu'à ce que la ville la plus éloignée de G soit traversée par la spirale. Notons Vmax, cette ville telle que -V(xiA2+yiA2) est max. Dans notre exemple, c'est Vmax = V1 . On obtient un premier positionnement. Illustration 3: Premier positionnement de la spirale 7/23 304 1 i99 Dès lors, pour chaque ville Vi on détermine le bras spirale le plus proche, est-ce l'intérieur, où l'extérieur ? On associe la ville à son bras le plus proche. Sur la figure, on a représenté en vert les segments qui relient chaque ville à son bras le plus proche. Ces segments sont perpendiculaire à la tangente à la spirale, logique puisqu'on veut la distance mini au bras. On obtient ainsi un ordre en les Vi. Illustration 4: Rattachement des villes au bras le plus proche On note di, la distance de la ville Vi à son bras. Di est noté positif si la ville est à l'extérieur du bras de référence, et négatif si à l'intérieur. Pour la simplicité des étapes suivantes, nous appellerons dès lors Xl, X2,... ,XN les villes réordonnées depuis l'extérieur de la spirale vers l'intérieur. D'un point de vue algorithmique, cela revient à construire un nouveau tableau X=(X1,..,XN). 8/23 3041799 3.1.4 Affinage du positionnement par calcul de rugosité Pour une spirale donnée formant un angle avec une spirale de référence quelconque, qu'on note S(a), on défmi la notion de rugosité Ru du chemin X(i) par : Ru(X) = r E 1,N (4)1 di On va maintenant faire tourner la spirale autour de G afin de trouver la spirale Saopt, telle que Ru(X) soit minimum. D'un point de vue informatique, il suffira ici de faire tourner la spirale pas à pas depuis un angle de référence, et de calculer la rugosité uniquement chaque fois que le chemin change, car il ne changera que de façon discontinue, à certains angles limite. A partir d'un certain angle on a une sorte de « saut quantique », d'un point d'un bras vers un autre bras, adjacent. Illustration 5: Chemin tracé après positionnement de la spirale pour rugosité minimum. On obtient ici un nouveau tableau X11-(X1,...,Xi,...XN). 9/23 3041799 Dans notre exemple : X[] = (V1,V10,V9,...,V5,V7). On obtient un chemin qui n'est pas incohérent, cependant, on note immédiatement que V7 pourrait être reliée plus rapidement, entre V1 et V10. On est ici face à une situation de « captage » d'un point de chemin par un bras adjacent. Ces situations de captage sont généralisées et traitées plus loin. On passe donc à l'étape suivante 3.2 Calcul itératif du chemin idéal de X[X1,...,XNJ On trace un premier chemin entre les Xi, dans l'ordre où il sont projetés sur la spirale, en partant de l'intérieur ou de l'extérieur, c'est indiffèrent, mais avec une condition de récursivité: Boucle sur le tableau ordonné des X(i). Pour i=1 à N-1 : Illustration 6: Premier chemin déterminé par méthode "leafar" 10/23 3041799 3.2.1.1 Détection et traitement des « amas » Certaines configurations particulières, où un certain nombre de points sont regroupé sur une certaine zone, peuvent donner naissance à des « amas ». Cette phase de l'algorithme décrit le critère de détection d'un tel amas, la manière de la constituer, de le traiter. Calculer : LCi = Norme(Xi,Xi+1)+Norme(Xi+1,Xi+2)+Norme(Xi+2,Xi+3) : norme du chemin trouvé en première instance. DCi = Norme(Xi,Xi+2)+Norme(Xi+2,Xi+1)+Norme(Xi+1,Xi+3) : norme du raccourci éventuel obtenu par zig-zap, dans les cas de densité et configuration particulière des 4 villes X. (Les conditions topologiques d'émergence d'une telle situation sont discutée dans la partie Error: Reference source not foundError: Reference source not found). Si LCi > DCi => Début de rencontre avec un « amas » (*) : r Illustration 7: Situation limite : point de basculement, création d'un amas 11/23 3041799 Voir figure Illustration 7: Situation limite : point de basculement, création d'un amas Création de l'amas A(4) = (Xi,Xi+1,Xi+2,Xi+3) On fait ensuite une « agrégation éventuelle des villes Xi+j qui suivent (l'amas peut Contenir plus de 4 villes/étoiles...) Pour j=1 à n-i-1 ( Tant que LCi+j > DCi+j => Ajout de Xi+j dans l'amas existant (Xi,Xi+1,...,Xi+j-1). Si LCi+j Sortie de boucle j avec Fin de boucle j ( j++). Illustration 8: Rencontre d'un amas Sur la figure précédente, on a modifié les donnée pour faire apparaître un tel amas. On présuppose que le centre de gravité n'a pas changé par cet ajout, sinon il faudrait recommencer l'algorithme. Pour ce faire, on peut imaginer qu'il a aussi été ajouté une ville Vx située à l'opposé du centre de gravité GA de l'amas A(2,9), à une distance égale à 9xNorme(G,GA), de telle sorte que équilibre est 12/23 3041799 respecté. On pourrait aussi considérer l'ajout d'un autre amas B de poids égal, dont le centre de gravité est symétrique à GA par rapport à G. Bref, le centre de gravité n'a pas bougée Dans notre exemple: A(i,J) = (Xi, ...,Xi+J-1) = A(2,9) = (X2,...,X10). Un amas de 9 villes défini depuis X2. On observe que la portion d'espace E(A) (en mauve sur la figure) forme la zone contenant l'amas A. E(A) est défini entre: - les droites reliant au plus court à la spirale V71 et V79 ( droites perpendiculaires à la tangente à la spirale au point le plus proche de V71 et V79), d'une part et - la spirale délimitant la « ligne de partage » entre deux bras concentriques (en violet sur la figure, la limite extérieure est hors champs mais on l'imagine) Récursion de l'algorithme (reprise en 3.1.1 Données du problème avec comme données du nouveau sous-problème les na=i+J-1 villes (Xi,...,Xi+J-1)). Un amas est donc parfaitement défini par les 2 entiers i et J, qui sont respectivement l'origine (ville de l'amas la plus en amont) et son nombre de ville. Faire un 3.2.1.2 Rattachement d'un amas A(i,J) à sa spirale parente Si LCi Tracer segment Xi->Xi+1 Dans notre exemple, il n'y a pas de tels amas, donc pas de récursions. Fin de boucle i 13/23 3041799 3.2.1.2 Rattachement d'un amas A(i,J) à sa spirale parente Par la récursion, on a obtenu un chemin spirale parfait, mais local à A(i,J). Illustration 9: Chemin optimal mais local de l'amas A(2,9) On note sur la figure qu'on a formé un trajet local beaucoup plus logique que le zig-zag donné en première instance avant récursion sur l'amas. On notera dès lors A(A1,... AJ), les points réordonnancés par la spirale locale. On doit maintenant faire le rattachement de l'amas A(i,J). En première approche, on pourrait brutalement être tenté de rattacher l'amas A au super amas parent X par les 2 segments : (Xi-1->Xi) et (Xi+J-1>Xi+J). Ce n'est pas une mauvaise solution, on conserve la forme spirale de A, mais ce rattachement provoque au moins une intersection de segment. Il n'est donc pas optimum. 14/23 3041799 11/4. Illustration 10: Rattachement "brutal" de l'amas A au super amas X Sur la figure ci-dessus on a encore ajouté des points pour donner plus de tour à la spirale et rendre l'exemple plus probant. Le rattachement Xl->XA1 semble logique, il est en extrémité et au plus court. Rattachement X11->A15 (il ne passe pas par A7, contrairement à ce que peut laisser croire la figure). Mais ce rattachement n'est pas très « esthétique »... On présent qu'il existe un meilleur rattachement. En voici la méthode : DEBUT RATTACHEMENT AU PLUS PROCHE (Xi+J, AG,J) Trouver Amin dans A(j,J) tel que Norme (Xi+J,Amin) soit minimale (Amin = A7 dans l'exemple). Si Amin = AJ => Optimum atteint=> Sortie. Si Amin <> AJ : 15/23 3041799 Rattacher Xi+J ( X11 dans l'exemple), à Amin Supprimer le segment (Amin,Amin-1) (soit (A7,A6) dans l'exemple en première récursion, (Al2,A13) en seconde récursion). RATTACHEMENT AU PLUS PROCHE (Amin-1, A(min,J)) Fin Si Amin AJ FIN RATTACHEMENT AU PLUS PROCHE. Illustration 11: première itération d'un rattachement au plus proche Après une première itération, sans récursion, c'est déjà plus agréable à regarder, mais il reste encore une intersection dans le chemin produit. 3041799 Illustration 12: Rattachement optimal de l'amas : apparition de 2 bras spirale... Après avoir effectué toutes les récursions de la fonction de rattachement, on ressort de cette fonction avec un chemin non croisé où semblent se dessiner deux bras spirales enroulés l'un sur l'autre... 3.2.1.3 « Accrétion » d'un portion de chemin par le chemin d'un bras spirale adjacent. Dans la figure Illustration 5: Chemin tracé après positionnement de la spirale pour rugosité minimum , on avait déjà noté que V7 était destiné à être capté par le segment (V1,V10), pour aboutir au chemin tel que sur Illustration 6: Premier chemin déterminé par méthode "leafar". Le cas du captage d'une ville unique est facile à traiter, avec un rapide calcul de différence de nonne, cependant, il est insuffisant pour traiter les cas toute une sous-partie du chemin est destiné à être capté. 17/23 3041799 Sur la figure ci-dessus, on a représenté une situation d'accrétion type. On présent bien qu'il existe une optimisation possible de ce chemin, en incluant les point (Xj,...,Xj+K) entre Xi et Xi+1. On trace les deux bissectrices de (Xi-1,Xi,Xi+1) et (Xi,Xi+1,Xi+2). Les K candidats au captage (Xj,...,Xj+K) sont recherché dans la portion de bras inférieur délimité par ces deux bissectrices, car, en dehors de cette zone d'accrétion , les point seraient capté par les segments (Xi-1,Xi) ou (Xi+1,Xi+2). Soit P le nombre de points compris dans cette portion. On a donc un tableau X(j,..., Xj+P) de candidats au captage. Pour i=1 à N-1 Identification des P candidats X(j,..., Xj+P) au captage par, dans la zone d'accrétion de (Xi,Xi+1). Pour p=P à p=1 r Illustration 13: Exemple d'une situation de captage extérieur 18/23 3041799 On calcule les différence de longueur entre le chemin initial (LC1) et celle du chemin obtenu par captage LCc. LC1 = IXiXi+11+ zk E 0,p+1 Xj+k-1,Xj+k+1 I LCc = I XiXj1 + Ek e °'P 1 Xj+k,Xj+k+1 I Si Lcc Vi' en Vi->Vp->Vi'. 3.4 Généralisation en N dimensions Il est déjà établi que si un problème NP-complet a une solution, alors tous les problèmes en ont une, par réduction polynomiale. Cette solution est donc applicables en N-dimensions, à conditions de savoir défmir un angle et une norme dans l'espace à N dimensions. Dès lors on peut replace les vecteurs à N dimension dans OUR, en utilisant la norme et l'angle de chaque vecteur GXi. L'espace RN doit respecter certaines caractéristiques, à savoir être normé bien sur, et être doté d'un produit scalaire A entre deux vecteurs. De telle sorte que l'angle peut être calculé comme : 0(GXi,GXj) = arccos(GXi A GXj / I GXi I + I GXj I ). 20/23 3041799 En N dimensions, on pourrait définir l'hyper-spirale de telle sorte que toute projection de l'hyperspirale dans RN sur R2 soit également une spirale, avec un décalage de phase optionnel. 3.5 Exemple en 3 dimensions. Cette fois, notre voyageur de commerce est un voyageur du futur... A bord de sa navette spatiale, il doit relier n planètes P réparties aléatoirement dans R3. Dans ce cas, on calculera également le centre de gravité des planètes à visiter. Puis, la distance de chacune à ce centre. Sur un graphe en 2D, on placera les planètes. La planète la plus proche Po peut-être placée n'importe où sur le cercle respectant sa distance au centre. Ensuite, chaque planète Pi peut être placée sur son cercle de distance, en formant un angle respectant l'angle entre les vecteurs Pi-1 et Pi. Sur ce graphe projeté en 2D, on calcule le chemin idéal par la méthode Leafar. Une fois calculé, on peut dessiner le chemin en 3D en suivant le même ordre des Pi. L'hyper-chemin tracé sera une sorte de dragon qui jamais ne se mort la queue. Il serait intéressant de construire l'hyper-spirale 3D, S3 dans R3 de telle sorte que Proj(S3 sur plan (y,z) = S2, S2 étant une spirale de Fibonacci. Bien entendu Proj(S3 sur plan (x,y) = S1, qui est une spirale de Fibonacci. Dès lors, on peut s'amuser à faire tourner la spirale S2, pour effectuer des décalages de phase, et observer comment évolue l'hyper-spirale S3 en fonction du décalage de phase de Si et S2. Pour un décalage de phase nul, l'hyper-spirale est en fait une spirale 2D inclinée, mais contenue dans un plan, tandis que pour un décalage non nul, on obtiendra des motifs 3D. Le décalage de phase à 90° doit présenter un intérêt particulier, ainsi que tous ceux avec un angle nrn, n étant entier. 4 Exemples de champs d'applications Il va sans dire que les domaines d'application de cette méthode de résolution des problèmes NPcomplets sont nombreux: - L'ensemble de ce que nous appelons « matière » puisse être ordonné de façon fractale, autour de l'élément Spirale de Fibonacci. Il faudrait juste connaître plus précisément la topologie de l'univers connu pour le fractaliser par cette méthode. - On peut imaginer définir un système de coordonnées très puisant, donnant chaque position par sa longueur spirale, sa distance au bras, et récursivement dans le cas de sous groupe. - Tous les domaines où un optimum doit être trouvé dans un graphe combinatoire: jeux de stratégie, optimisation... - En gravitation, comprendre la spirale comme un état d'équilibre ou du moins d'attraction. Le mécanisme « d'accrétion » décrit dans l'algorithme expliquerait l'organisation en spirale des étoiles dans une galaxie. Le mécanisme de détection et rattachement des amas expliquerait les galaxies double spirales qui seraient ainsi le résultat d'une influence gravitationnelle externe. - En pondérant les astres avec leur masse gravitationnelle, on peut calculer le chemin idéal pour s'enfuir d'une planète en profitant au mieux des « rebonds gravitationnels » des astres, 21/23 3041799 de proche en proche... On ignorera les astres peu massif ou mal placés qui ne procureraient pas plus d'énergie que n'en demande le détour à faire... On peg même tenir compte du temps de trajet, en attendant d'être éternels... - Pour un système solaire donné, gravitant autour de son centre de gravité, pondérer avec la masse de chaque astre, calculer le chemin spirale idéal qui les unis, voir comment évolue ce chemin dans le temps, avec la rotation des astres. On peut faire l'hypothèse qu'il n'est pas rompu brutalement, qu'il se déploie et évolue en respectant son chaînage? - En mécanique fondamentale, on peut se demander si cette spirale n'est pas au coeur de la matière et ne pourrait pas expliquer les « sauts quantiques ». En effet, dans l'exemple du voyageur de commerce, quand on fait tourner la spirale, il arrive un moment où un point est soudainement rattaché en un autre point du chemin, provoquant un nouveau chemin non optimum. Parallèle possible avec état « excité » d'un électron? - On serait presque tenté de demander: quel rapport cela peut-il avoir avec les « brisures de symétrie »... Etant donné que la spirale n'a qu'un centre virtuel, dont on se rapproche sans cesse sans jamais l'atteindre, il peut y avoir une relation entre ces écarts infinitésimaux au centre de gravité, et la brisure de symétrie... 22/23 3041799 Illustration Index Illustration 1: Problème du voyageur de commerce, villes et routes. 4 Illustration 2: exemple aléatoire avec 10 villes. 6 Illustration 3: Premier positionnement de la spirale 7 Illustration 4: Rattachement des villes au bras le plus proche 8 Illustration 5: Chemin tracé après positionnement de la spirale pour rugosité minimum 9 Illustration 6: Premier chemin déterminé par méthode "leafar" 10 Illustration 7: Situation limite : point de basculement, création d'un amas 11 Illustration 8: Rencontre d'un amas 12 Illustration 9: Chemin optimal mais local de l'amas A(2,9) 14 Illustration 10: Rattachement "brutal" de l'amas A au super amas X 15 Illustration 11: première itération d'un rattachement au plus proche 16 Illustration 12: Rattachement optimal de l'amas : apparition de 2 bras spirale... 17 Illustration 13: Exemple d'une situation de captage extérieur 18 Illustration 14: Chemin corrigé par captage 19 23/23 REVENDICATIONS1. RESOLUTION LINEAIRE DES PROBLEMES NP-COMPLETS « METHODE LEAFAR ». La présente demande de brevet a pour but de fournir à son inventeur (Raphaël Wizenberg), l'exclusivité des droits de propriété intellectuelle pour tout logiciel informatique qui utiliserait l'algorithme décrit en détail dans le document joint. On entend par logiciel informatique tout programme (software) développé en n'importe quel langage informatique destiné à être exécuté sur un quelconque système informatique, y compris les composants électroniques « embarquant » cet algorithme. La protection des droits s'entendra à tout logiciel gratuit ou payant, utilisant de façon complète ou partielle la méthode algorithmique décrite. Ainsi, un logiciel qui n'implémenterait que certaines des étapes clés décrites en détail dans le document ci-joint serait soumis au brevet présentement demandé: - application d'une spirale de Fibonacci centrée sur centre de gravité du nuage des points représentant le problème rotation minimisant la « rugosité » du chemin - détection et rattachement des « amas » - détection et traitement des situation « d'accrétion » En outre, dans éventualité où un tiers inventerait un algorithme amélioré ou optimisé, mais basé sur la « méthode Leafar » serait soumis au brevet présentement demandé. Dans le document détaillé, l'algorithme est décrit pour un problème du voyageur de commerce en 2 dimensions, mais cette méthode est applicable à des problèmes en N dimensions, par projection du problème N dimensions en 2 dimensions, par calcul d'une norme et d'un angle dans l'espace en N dimension. La protection devra donc s'étendre à tout logiciel ou algorithme quelle que soit la dimension du problème traité. La protection demandée couvrira tous les domaines d'applications qui sont très nombreux: résolution de tous les problèmes de graphes et combinatoire, cosmologie, météorologie, calcul opérationnel... De fait, tous les domaines nécessitants des calculs complexes peuvent bénéficier de cette invention, et seront donc soumis à la protection de droit d'auteur faisant l'objet de la présente demande. En cas de litige, et si un accord amiable ne peut-être trouvé avec le « contrevenant », le tribunal compétent sera chargé de statuer sur le différent.