Défi pour le PureBasic :)

Frenchy Pilou · Message par **Frenchy Pilou** » sam. 03/déc./2005 22:42

http://labo.algo.free.fr/defi250/defi_d ... illes.html
page ou se trouve le fichier des 250 villes et les modalités( c'est super ouvert)

Pour ces 250 points le record est pour l'instant
Le trajet le plus court trouvé jusqu'à présent (par Xavier Clarist 21/12/2002).
Longueur = 11.8093
en 1200 soit 360 de temps corrigé ( 360 secondes ? )

Le concours est ouvert à tous, sans limitation de temps (tant que cette page se trouve sur le Web...). Tout système d'exploitation, language, compilateur est accepté. Si possible, il serait bien de fournir l'exécutable ou même le code source (si votre logiciel est libre), mais ce n'est pas obligatoire.

La page des résultats actuels
http://labo.algo.free.fr/defi250/classement.php?id=1

Alors, pour ceux ceux qui sont en manque d'inspiration, voilà une occasion de se frotter aux autres langages Non ?

Y a rien à gagner à part le respect des autres bidouilleux

D'après ce post
http://pingouin.migrateur.free.fr/forum ... hp?forum=2
C'est encore en cours !
L'auteur n'est pas moi ! (je viens juste de trouver la page )
C'est un extrait de la page du règlement

Le défi des 250 villes : faites participer votre algorithme !

Le défi des 250 villes est un concours ouvert à tous et . Il s'agit de créer un logiciel permettant de trouver, le plus vite possible, le chemin le plus court entre 250 villes (voir un exemple à droite).

Voici comment le défi a commencé :

Après avoir découvert le problème du voyageur de commerce (PVC) et les algorithmes génetiques, j'écris en 1996 une première version de mon algorithme permettant de résoudre des petits problèmes (de l'ordre de 25 villes). Cet algorithme est présenté dans ma page sur les algorithmes génétiques en C (1997). En 1998-99, j'en fait une version Delphi sous Windows (GraphGen), en ajoutant la possibilité de changer le nombre de villes et d'afficher graphiquement la solution.

Le 30 Septembre 2000, je reçois un e-mail d'un étudiant en informatique. Il me dit qu'il travaille depuis un an sur un algorithme permettant de résoudre le problème du voyageur du commerce, qu'il pense être très performant.
Intrigué, je lui demande plus de détails et je lui envoie une version de mon algorithme écrit en Delphi. Il me répond que mon programme est intéressant, mais que le sien est bien mieux que le mien ... et il me le prouve en me l'envoyant !
Effectivement, mon algorithme fonctionne bien pour un nombre de villes assez réduit, mais commence à peiner à partir de 75 villes. Le sien est plus efficace et surtout beaucoup plus rapide !
Sachant que mon programme date un peu, et que j'ai des idées d'amélioration et d'optimisations, je lui propose de nous mesurer grâce à un défi : trouver le meilleur parcours pour un problème de 250 villes. (le défi n'a pas de date de fin car il est impossible à ma connaissance de prouver que l'on a trouvé le meilleur chemin)
Quelques temps plus tard, d'autres personnes me contactent pour participer au concours...
Vous voulez participer ? C'est facile
C'est simple, il suffit de créer un programme qui respècte les règles ci-dessous, et de m'envoyer le résultat (votre meilleur parcours).

Le concours est ouvert à tous, sans limitation de temps (tant que cette page se trouve sur le Web...). Tout système d'exploitation, language, compilateur est accepté. Si possible, il serait bien de fournir l'exécutable ou même le code source (si votre logiciel est libre), mais ce n'est pas obligatoire.

Si vous avez une idéee d'algorithme et si vous savez programmer, n'hésitez pas à nous rejoindre !.
Actuellement plus de 20 participants sont dans la course ! (voir la page des résultats et classement actuel)

Les termes exacts du défi

Le but est simple : trouver le chemin le plus court entre les 250 villes dont les coordonnées (x, y) sont définies dans le fichier suivant : defi250.csv

Les 250 villes se trouvent dans un carré de 1 x 1, c'est à dire entre les points de coordonnées (0, 0) et (1, 1).

Le format du fichier est le suivant :

nombre de villes total
position X de la première ville;position Y de la première ville
position X de la deuxième ville;position Y de la deuxième ville
position X de la troisième ville;position Y de la troisième ville
...

Extrait du fichier defi250.csv :

250
0.223118073306978;0.216796220745891
0.447559242602438;0.492616587784141
0.569365015253425;0.473787421826273
0.474918519612402;0.033659254200757
...

Les villes sont numérotées de 0 à 249. Les trajets doivent commencer par la ville 0.

Le logiciel devra fournir le résultat (meilleur trajet trouvé) sous la forme :

n° de la 1ère ville visitée (toujours 0)-n° de la 2ème ville visitée-n° de la 3ème ville visitée...

(si possible dans un fichier, c'est plus pratique...)

Par exemple, voici le début du meilleur parcours :

0-85-24-202-51-05-61-92-37-06-153-32-242-58-155-227-113-126-110-...

Pas besoin d'afficheur dans votre programme, il suffit d'utiliser la petite applet que j'ai créé, à intégrer dans une page html très simple (on en voit un exemple en haut de cette page) :

<html>
<applet code="DisplayTsp.class" width=400 height=400>
<param name="Problem" value="default">
<param name="Parcours" value="0-85-24-202-51-05-61-92-37-06-153-32-242-suite du parcours...">
</applet>
</html>

Dans le même répertoire, placez le fichier DisplayTsp.class (l'applet Java).

Cette applet de visualisation - dont vous voyez une démo un peu plus haut - est un logiciel libre (GPL) dont code source est disponible ici : DisplayTsp

Elle permet calculer la longueur du trajet et de zoomer. Elle peut aussi fonctionner avec d'autres problèmes (nombre de villes différents...)

Bien sûr, vous pouvez utiliser votre propre afficheur pendant le calcul (quelqu'un l'a même implémenté en OpenGL !) mais je vous préviens que cela rique de ralentir fortement le calcul...

Backup · Message par **Backup** » sam. 03/déc./2005 23:56

le problem serai le format des coordonées !

0.223118073306978

15 chiffres apres la virgule, je crois pas que le pure gere des flottants de cette taille !

d'ailleurs je confirme ,le pure accepte que des chiffres avec 8 decimales !

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

Tu convertis

A la fin il ne te demande que l'ordre des villes pas les coordonnées!
C'est lui qui calcule la longueur du chemin!

0.223118073306978 peut devenir par exemple
2231180.73306978

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

en fait "0.223118073306978" correspond a quoi ?

sur un ecran on a pas de chiffre a virgule !

(je suis une bille en math )

on a des coordonées du genre 20,50

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

Je pense qu'il a donné des coordonnées d'enfer, pour que les calculs soient le plus fin possible! Pour des zooms sûrement aussi...
Cela va se jouer à des millièmes de ploils de papier à cigarette

Comme dit dans l'autre post il va falloir convertir !

Et les seuls math à savoir en géométrie pure ne seront : comment calculer la longueur d'une diagonale d'un rectangle ABCD dessiné sur un repère X Y
Le carré de l'hypoténuse = la somme des carrés des côtés adjacents
soit par exemple
AC * AC = (AB *AB) + ( BC * BC)
Donc la longueur entre 2 points A et C est la Racine carrée de (AB *AB) + ( BC * BC)
http://fr.wikipedia.org/wiki/Th%C3%A9or ... _Pythagore

De toute façon tu ne vas faire les calculs qu'en Interne
C'est pour cela que tu vas les convertir pour qu'ils soient assimilables par PureBasic

Encore que je viens de lire dans la doc, que la plage des Flottants est illimitée !

cederavic · Message par **cederavic** » dim. 04/déc./2005 0:43

On aurait moin de précision en Pure, a moin d'utiliser l'asm (ou un userlib) pour les Doubles floats

Sami · Message par **Sami** » dim. 04/déc./2005 10:59

La question que je me pose c'est pourquoi il n'utilise pas l'algo A*.
Il n'est pas parfait et son implémentation serait différente dans le cas de ce probléme; mais il est rapide!
Il y a une autre solution aussi. C'est de créer un polygone qui passe par tout ces points avec un périmétre le plus faible possible.
Ce lien peut être prometteur.
Le polygone serait convexe ou convexe pour avoir le chemin le plus rapide.
D'autres liens sur les polygones.
http://serge.mehl.free.fr/anx/polygones.html
http://membres.lycos.fr/emauvais/idm/GeoPPol.htm

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

La question que je me pose c'est pourquoi il n'utilise pas l'algo A*.

C'est un test pour essayer de trouver l'algo le plus rapide, si celui-ci en l'implantant va plus vite, nul doute que tout le monde va l'adopter

Y a plus k'a

djes · Message par **djes** » dim. 04/déc./2005 11:23

J'ai fait un petit code à l'arrache pour tester toutes les possibilités. Reste à réduire leur nombre!

Code : Tout sélectionner

Dim ville_visitee.l(250)
NewList chemin.l()
NewList chemins_complet.l()

Procedure prochaine_ville(ville_actuelle)

	ville_visitee(ville_actuelle)=#True

	For i=1 To 249
		If ville_visitee(i)<>#True
			AddElement(chemin())
			chemin()=i
			prochaine_ville(i)
		EndIf
	Next
	
	AddElement(chemins_complet())
	chemins_complet()=AllocateMemory(250*4)
	ResetList(chemin())
	u.l=0
	While NextElement(chemin())
		PokeL(chemins_complet()+u,chemin())
		;là on peut calculer les distances
		;Debug chemin()
		u+4
	Wend

	For i=1 To 249
		ville_visitee(i)=#False
	Next i	
	ClearList(chemin())
	
EndProcedure

For i=0 To 249
	ville_visitee(i)=#False
Next i

prochaine_ville(0)


CallDebugger
End

Sami · Message par **Sami** » dim. 04/déc./2005 11:25

Ca y est j'ai trouvé un autre truc sympa!
Nuage de points
Ca me rappelle mes cours de modélisation spatiale en atelier.
Une solution qui est utilisé en automobile. Notament pour retrouver les surfaces de carroserie faites par les designers.

P.S Finalement on retombe dans un algo déjà utiliser! Celui de calculer la distance entre les points.

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

@dobro
tu peux seulement prendre les 2 premiers chiffres
0.223118073306978;0.216796220745891
0.447559242602438;0.492616587784141
0.569365015253425;0.473787421826273

cela devient des coordonnées X Y facilement utilisables

22; 21
44; 49
56; 75
etc
Tu as juste à verifier s'il n'y a pas 2 points identiques, auquel cas tu prends 3 chiffres

223; 216
447; 492
569; 753
etc

Cela ne change absolument rien, puisque ce qui est demandé c'est l'ordre des points des villes

Une fois ton meilleur chemin trouvé, pour voir ou tu te situes pas rapport aux autres concurrents, tu te débrouilles pour faire le calcul avec les données primitives en double précisions, que sais-je...
j'ai pas regardé ce que Purebasic admet, et il doit y avoir des biblios qui permettent le calcul flottant avec un max de chiffres

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

Il semble que dans ce cas les deux algo qui servent sont les Diagramme de Voronoi et la Triangulation de Delaunay.

Chris · Message par **Chris** » dim. 04/déc./2005 11:38

Ce qui serait bien, ce serait de trouver l'algo le plus rapide en PureBasic. Ca mettrai un drole de claque au C/C++ et autres langages Pro.

Je vois déjà leurs tête, à ceux qui disent que PureBasic est un langage de bricolo.

djes · Message par **djes** » dim. 04/déc./2005 11:39

Faut pas rêver! Le langage ne change rien au problème... C'est de l'algo pure.

Sami · Message par **Sami** » dim. 04/déc./2005 11:52

L'algo joue un grand role c'est certain. Mais si on utilise un langage interprété le résultat peut être décevant.

Je viens de trouver un autre algo pour ce probléme. Algo de Graham
Il semble finalement que le probléme soit bien connu et déjà régler. Il faut juste supprimer la derniére étape de l'algo.
Dans le cas de l'algo de Graham, l'étape la plus couteuse est le tri des points. On peut peut être l'accélérer avec un arbre binaire. Comme lors de la construction d'un BSP.
Par contre l'implentation de tout cela doit être un sacré boulot!