Défi pour le PureBasic :)

comtois · Message par **comtois** » dim. 04/déc./2005 12:02

L'algo de Graham est utilisé pour construire un polygone convexe ,idem pour ton nuage de point non ? enfin pour le nuage , c'est un polygone non convexe , mais enfin ça ne résoud pas le problème du voyageur de commerce ?

Il s'agit de passer par toutes les villes , et pas de les encercler comme tu le proposes , ou alors je n'ai rien compris , et dans ce cas tu pourrais développer un peu plus , je suis intéressé par le sujet .
J'avais commencé quelques recherches il y a quelques temps , elles aboutissaient toutes à l'utilisation des graphes pour gérer ce problème, mais je n'ai pas été plus loin , j'ai d'autres sujets en cours d'études en ce moment.

Faire également des recherches sur le cycle hamiltonien.

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.

Frenchy Pilou · Message par **Frenchy Pilou** » dim. 04/déc./2005 12:17

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

Connu oui !
Réglé non !
On ne trouve que des solutions qu'on pense être la meilleure, mais s'en en être sûr, du fait qu'il est impossible au jour d'aujourd'hui de vérifier par l'examen exhaustif de tous les cas possibles !
Et puis un truc qui fait appel aux élastiques, aux bulles de savons, aux fourmis ... pour tenter de le résoudre ne peut être qu'un algo fun

Sami · Message par **Sami** » dim. 04/déc./2005 12:35

Il existe plein de choses que l'on ne peut prouver et d'autres que l'on affirme et qui sont fausses.
Ex: Par exemple Pi. On ne peut avoir sa vraie valeur mais seulement une approximation. Les calculs que l'on réalise avec sont donc que des approximations.
Les cours de physiques en terminal S ou autre. L'atome est le plus petit élément de l'univers. C'est écrit noir sur blanc. Par contre aucune explication sur la physique quantique alors que l'on nous parle de la corpulence du photon et bien des lasers en optique.

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.
Ca c'est trés interressant. Il faut trouver le moyen de réduire le périmétre ou l'aire du polygone. L'aire du polygone peut être décomposer en triangle d'ou les algos de triangulisation. Le périmétre est moins exploitable géométriquement à mon avis.

comtois · Message par **comtois** » dim. 04/déc./2005 12:40

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.

Ok , je vais regarder ça plus attentivement alors , merci pour l'info.

Backup · Message par **Backup** » dim. 04/déc./2005 13:02

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

je croyais que c'etait le Quark !! ?

Sami · Message par **Sami** » dim. 04/déc./2005 13:07

Oups j'ai tapé trop vite et mal relut. oui c'est bien le quark et pas l'atome comme dans les bouquins de physiques de terminal en autre. dsl

comtois · Message par **comtois** » dim. 04/déc./2005 13:09

Tiens un résumé sur le sujet , intéressant , ça va plaire à Pilou , ça parle de savon , de fourmis ,de gaz ,de son !!

http://lslwww.epfl.ch/~thoma/research/t ... _chap4.pdf

http://lslwww.epfl.ch/~thoma/research/these/

Backup · Message par **Backup** » dim. 04/déc./2005 13:20

il devait etre chiant le Frenchy pilou a 8 ans ...

exemple de dialogue journalier chez Frenchy pilou a ces 8 ans :

- mais Pourquoi ci ? , mais pourquoi ça ? ect ...

-VAS TE COUCHER !

-Mais heu !!

-YA PAS DE MAIS !!!
-AU LIT !

Frenchy Pilou · Message par **Frenchy Pilou** » dim. 04/déc./2005 14:33

@comtois
Fichtrou la thèse

Merci, c'est très poètique en effet cet essai Poetic

Multicellular electronic (IC) tissue (T) with autonomous evolutionary , self-repair (P), self-replication (O) and learning (E) capabilities
http://www.poetictissue.org/ le site!

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

Mécanismes 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

Et bien sûr j'adore le chapitre 4

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.

Le système D émerdard, y a que cela de vrai !

Il a fait cela aussi le bougre : Le mur bio

http://lslwww.epfl.ch/biowall/VersionE/ ... ionsE.html

@Dobro
Nan j'irai pas me coucher, je veux savoir le plus court chemin pour faire la tournée des bistrots !

Backup · Message par **Backup** » dim. 04/déc./2005 16:01

voici le terrain de jeux des 250 villes :

utilisez le fichier "defi250.csv" dont le lien est donné plus haut !
le point rouge est la ville numero 1 (depart)

BOUTON DROIT POUR QUITTER !!!!

; 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

Frenchy Pilou · Message par **Frenchy Pilou** » dim. 04/déc./2005 16:06

Bravo!
Cela marche!
Comment qu't' as fait ? Mon truc de de ne prendre que quelques chiffres ?

T'as bien vérifié qu'il n'y en a pas 2 ayant les mêmes coordonnées?

Backup · Message par **Backup** » dim. 04/déc./2005 16:09

oui !
dans cette partie du code !

Code : Tout sélectionner

 ; transformation dans la liste du format 0.123456789;0.987654321 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

Frenchy Pilou · Message par **Frenchy Pilou** » dim. 04/déc./2005 16:12

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 sur l'écran!

Backup · Message par **Backup** » dim. 04/déc./2005 16:17

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!

non car aucune coordonées n'est pareil !!

des les 2eme decimale apres la virgule !!!!
donc c'est bon !

fait se dessiner mes points au ralenti en mettant un Flipbuffer et un delay(5)
dans la boucle de dessin tu verra par toi meme !

Frenchy Pilou · Message par **Frenchy Pilou** » dim. 04/déc./2005 16:21

Ok parce que j'avais pas envie de les compter à l'écran!