PureBasic

Sur un graphe planaire, on nomme “Cycle hamiltonien” une boucle fermée qui passe une fois et une seule par chaque sommet du graphe : en effet, c’est le mathématicien Hamilton qui étudia au 19e le problème de l’existence, dans un graphe donné, d’un cycle hamiltonien.

Il semble finalement que le problème soit bien connu et déjà réglé

Sami a écrit : Oui l'algo de Graham propose de les encercler. Mais à la fin de l'algo! Au milieu de celui-ci on passe par tous les points. On fabrique un polygone étoile ou polygone quelconque irrégulier non inscrit dans un cercle de n sommet.

L'atome est le plus petit élément de l'univers. C'est écrit noir sur blanc.

Les circuits électroniques ne font pas exception, et les trois axes de la vie que sont l'évolution des espèces (Phylogenèse), le développement de l'organisme à partir d'une seule cellule (Ontogenèse), ainsi que l'apprentissage dont notre cerveau est capable (Epigenèse), ont vu nombre de réalisations s'en inspirer.

Ces trois axes forment l'acronyme POE

La théorie, c’est quand on sait tout et
que rien ne fonctionne. La pratique, c’est
quand tout fonctionne et que personne
ne sait pourquoi. Ici, nous avons réuni
théorie et pratique : Rien ne fonctionne...
et personne ne sait pourquoi !
Albert EINSTEIN

4.2.4 De la ficelle
Avant de passer aux bases théoriques, citons une méthode originale pour résoudre
le problème du plus court chemin entre deux villes. Minty, en 1957, propose, dans une
note de 12 lignes dans le journal Operations Research [161], une solution à base de
ficelle et de clous. Il suffit de prendre un clou par ville, et de les relier par des bouts
de ficelle dont la longueur correspond à la distance séparant chaque paire de villes
reliées par une route. En tirant ensuite sur les clous qui représentent les villes à relier,
le chemin le plus court se trouve tout naturellement en suivant les bouts de ficelle
tendus.
Par cette approche, il est également possible de trouver en une fois tous les chemins
entre un point (la source) et tous les autres, en suspendant des poids à tous les clous.
En tenant le clou de la source, tous les autres clous pendront par une suite de bouts de
ficelle représentant le plus court chemin à la source.

; codé par Dobro
; le terrain de jeu des 250 villes


offsetx=100
offsety=50
zoom=6

Enumeration
   #dobro
   #Police
   #Sprite
   #Fichier
EndEnumeration

NewList list.s()


Resultat = OpenFile ( #Fichier , "defi250.csv" )
While Eof ( #Fichier )=0
  Texte$ = ReadString ()
   AddElement (list.s())
  list()=Texte$
Wend
CloseFile ( #Fichier )

; ** suprime le premier element de la liste (250) ***
FirstElement (list())
DeleteElement (list())
; ********************************************

; transformation dans la liste du format 0.123456789;0987654321 en format : 12;98
ForEach list()
  x$= StringField (list(), 1, ";" )
  y$= StringField (list(), 2, ";" )
  x$= Mid (x$,3,2)
  y$= Mid (y$,3,2)
  total$ =x$+ ";" +y$
   DeleteElement (list())
   AddElement (list())
  list()=total$
Next

; ************************************************************

; ***********************************
Resultat = InitSprite ()
FontID = LoadFont ( #Police , "arial" , 18, #PB_Font_Bold )
EcranX = GetSystemMetrics_ ( #SM_CXSCREEN ): ;=largeur de l'ecran
EcranY = GetSystemMetrics_ ( #SM_CYSCREEN ): ;=hauteur de l'ecran
   WindowID = OpenWindow (1, 0, 0,EcranX, EcranY, #PB_Window_SystemMenu|#PB_Window_BorderLess |#PB_Window_ScreenCentered , "hello" )
  Result = OpenWindowedScreen ( WindowID (1) ,0,0, EcranX, EcranY, 1, 0,0)
  Resultat = InitMouse ()
  
   ; *********** boucle principale *******************
   Repeat
     While WindowEvent () : Wend
     ExamineMouse ()
     WindowEvent ()
     Delay (2)
    
     If MouseButton (2)
       End
     EndIf
    
     ; *************** dessin de la carte******************
     If ok=0 ; sert a ne dessiner qu'une fois !
     ResetList (list() )
     ForEach list()
      compteur=compteur+1
      x= Val ( StringField (list(), 1, ";" ))*zoom+offsetx
      y= Val ( StringField (list(), 2, ";" )) *zoom+offsety
       StartDrawing ( ScreenOutput ())
       If compteur<>1
         Box (x,y,2,2, RGB ($FF,$FF,$0)) ; dessin des villes
       Else
         Box (x,y,5,5, RGB ($FF,$6F,$6F)) ; dessin de la 1er ville
         EndIf
         StopDrawing ()
          
     Next
      ; ****************************************
    ok=1 ; le dessin est fini pas la peine de le redessiner a l'infini !
   EndIf
    
       FlipBuffers (): ; affiche l'ecran

     ;ClearScreen(0, 0, 0) :;efface l'ecran
    
   Until Event= #PB_Event_CloseWindow

Oui, oui, mais si y en a 2 pareilles différentes seulement à la 8ème décimales (très proches par exemple)?
Il en manquera une à la fin!