PASCAL: Je vous en supplie, aidez moi, ou lisez au moins!!

Recherche :

Dernière réponse
Sujet : PASCAL: Je vous en supplie, aidez moi, ou lisez au moins!!
BENB	tfj57 > je dis pas que c'est rapide... mais ils semblent completement perdus, alors je leur donne un os a ronger, mais pas plus, donc ils le programment comme ils veulent ! De toute facon ces problemes (voyageur de commerce et prog dynamique) sont toujours gourmant en calculs Sinon il y a aussi des algo de style tri on pose une solution puis on essaye d'intervertir deux villes et on regarde le resultat, c'est plutot plus long, mais graphiquement c'est plus joli, car on peut presenter l'evolution de la solution, et on vois un embrouillamini se demeller. Par contre si les villes sont donnes dans un ordre judicieux ce peut etre une solution.

Dernière réponse

Sujet : PASCAL: Je vous en supplie, aidez moi, ou lisez au moins!!

BENB

tfj57 > je dis pas que c'est rapide...
mais ils semblent completement perdus, alors je leur donne un os a ronger, mais pas plus, donc ils le programment comme ils veulent !
De toute facon ces problemes (voyageur de commerce et prog dynamique) sont toujours gourmant en calculs

Sinon il y a aussi des algo de style tri
on pose une solution puis on essaye d'intervertir deux villes et on regarde le resultat, c'est plutot plus long, mais graphiquement c'est plus joli, car on peut presenter l'evolution de la solution, et on vois un embrouillamini se demeller.

Par contre si les villes sont donnes dans un ordre judicieux ce peut etre une solution.

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

BENB

BOL a écrit a écrit :

Il doit y a voir une méthode dite des moindres carrés ou quelque chose :??: comme ça mais je ne la connais pas exactement. :(
Elle doit être plus efficace que le calcul des (n-1)! distances possibles... On doit pouvoir la trouver dans des cours d'analyse numériques ou de statistique. ou sur un moteur de recherche quelconque.

bol

Il n'y a pas de choix il faut calculer toutes les distances, la methode de l'arbre permet d'eviter un certain nombre d'additions, le tableau des distances de ville a ville permet de ne faire qu'un minimum de racines carres.

il me semble que cet algo est optimum...

Pour les moindres carres il faut optimiser des variables continues, pour des variables dicretes il faut en general tout essayer...

bol	oui effectivement, après un rapide tour de voila (ou je suis tombé sur un forum d'ana num) et sur yahoo( où je suis tmbé sur un forum de l'ENS Cachan), on tombe plutôt sur une utilisation pour faire des approximations et lisser des nuages de points. désolé de cette fausse route

tfj57

BENB>...

Bonjour à toutes et à tous,

C'est la méthode idéale qui se programme très facilement en récursif, mais il y a tout de même un gros problème, dès que le nombre de villes atteint à peine une quinzaine, la recherche devient très très longue et augmente d'un façon exponentielle pour plus de villes.

Il est aussi difficile de trouver des méthodes efficaces pour réduire les banches des arbres car pour cela il fait aller assez en profondeur dans la branche pour s'apercevoir que la solution est moins bonne qu'une solution déjà touvée par exemple.

Ce problème n'est pas si évident que ça, et je crois qu'à ma connaissance il n'y a pas d'algorithme pour rechercher la solution optimale dans des délais raisonnables.

Salutations

[edit]--Message édité par tfj57--[/edit]

JPA	La méthode des moindres carrés est plutôt destinée à chercher une courbe de lissage d'un nuage de points. Ca ne me semble pas adapté au problème posé ici.

bol

Il doit y a voir une méthode dite des moindres carrés ou quelque chose :??: comme ça mais je ne la connais pas exactement. :(
Elle doit être plus efficace que le calcul des (n-1)! distances possibles... On doit pouvoir la trouver dans des cours d'analyse numériques ou de statistique. ou sur un moteur de recherche quelconque.

bol

BENB

Bon aller je m'y colle, il te faut en fait trouver un algo qui te permet de calculer tous les trajets en evitant d'en calculer certains deux fois, et en evitant d'en oublier.

Un technique consiste a partir d'une ville.
puis dans un arbre tu mets les distances de cette ville avec les n-1 autres villes, puis pour chaque element de l'arbre tu ajoute les distances...
A
| \ \
B C D
d1 d2 d3
|\ |\ |\
C D B D B C
d1+d4 etc...
|
D
d1+d4+d5
Et avant de faire cet arbre je ferais un tableauc calculant les distances entre tous les couples de villes, et pour faire l'arbre tu cherches dans ce tableau.

A la fin une fois l'arbre accompli, tu n'as plus qu'a chercher dans la branche de l'arbre qui te donne le chemin le plus court.

darkoli

je crois qu'il est aussi possible d'utiliser les algorithmes genetiques pour resoudre ce probleme.

ben2655

jls a écrit a écrit :

cherche des algo sur les parcourt de graph, cela pourrait t'aider.

:na: merci a tous ceux qui ont repondu, bifacemcleod, tu as parfaitement raison, je suis moi meme d'accord avec toi mais d'une je n'ai pas demandé que l'on fasse le pb a la place de la personne pour qui je le demande, j'ai demandé qq un qui avait deja fait le meme exo et d'autre part, il peut arriver que l'on ai pas de temps, ou que la note soit tellement importante qu'un corrigé serais le bienvenu...enfin a vrai dire je ne sais pas s'il s'agit de negligence, de manque de temps, de feneantise ou d'un coups de bourre, moi je n'ai fais que essayé de "l'aider" encore une fois je suis d'accord de recopier n'est pas une solution pour progresser c'est pourquoi je l'ecris entre guillements

jls	cherche des algo sur les parcourt de graph, cela pourrait t'aider.

BifaceMcLeOD

ben2655 a écrit a écrit :

je suis desolé mais c pire qu'un esprit scolaire ici, on se croirais entre camarades de lycée, qui veulent pas s'entraider par jalousie. bravo les gars, ne me faites pas que si on se fait aider c pas comme ca qu'on y arrive je connais la chanson, ca ne marche pas ici parceque aucun de vous de se souscis de toute facon de qq un qu'il ne connait pas.

Non, je ne dirais pas cela. Si tu parcours le forum, tu trouveras des tas de cas où les forumeurs ont donné des idées d'algos, des bouts de code, etc. Mais la programmation est un exercice difficile et une science fondamentalement expérimentale. Ce qui veut dire que pour apprendre, il faut essayer, essayer et essayer encore, jusqu'à ce qu'on trouve une méthode qui marche. Si on te donne le code complet répondant au projet demandé, tu (ou ton ami/amie) ne feras/fera aucun progrès. Et ça, tout le monde te le dira ici, c'est vraiment dommage.

Alors si tu postes une question du genre "j'ai une liste de villes qui ont des coordonnées (x, y), comment je peux faire pour trouver la distance minimale du chemin passant par toutes les villes", tu auras sans doute des réponses te donnant une idée d'algo -- suffisamment pour pouvoir redémarrer et ne pas rester bloqué. Mais faire un projet complet, c'est bosser à ta place. Et clairement, personne ici n'acceptera de le faire. Pour les raisons que j'ai évoquées ci-dessus. Parce que le forum est là pour permettre aux gens d'apprendre, toujours et encore. Et à rien d'autre.

ben2655

c justement pour ca que j'esperais trouver des gens qui l'ont deja fait, j'ai jamais demandé qu'on bosse a ma place!

gilou

Si tu nous proposes des algos, on te les critiquera, et te permettra de les ameliorer, mais on n'a pas l'intention de se taper ton boulot. Faudrait voir a bosser un peu.
A+,

ben2655

je suis desolé mais c pire qu'un esprit scolaire ici, on se croirais entre camarades de lycée, qui veulent pas s'entraider par jalousie. bravo les gars, ne me faites pas que si on se fait aider c pas comme ca qu'on y arrive je connais la chanson, ca ne marche pas ici parceque aucun de vous de se souscis de toute facon de qq un qu'il ne connait pas.

wouatouwouatou

au fait, ta du tapercevoir de lesprit Hardware maintenant :D

Et puis, se bouger les fesses ne le feront pas avancer dans son projet (jai deja essayé et ca na rien donné :D...)
Moi jaurai plutot dit se bouger les neuronnes (ca marchera tout de suite mieux :D:D:D )

ben2655

sympa, merci pour les conseils, d'autres candidats??

LogonSystem

Arf, c'est rigolo ton problème... :p
C'est un simple problème de combinatoire...
Un conseil, tu peux gagner du temps en arrêtant de calculer à chaque fois que le trajet courant est plus long que le plus petit trouvé.
Mais comme te l'ont dit les autres ici, va falloir que la personne qui t'a filé son problème se bouge un peu les fesses...

ben2655

....suis d'acccord avec toi, juste que ce n'est pas pour moi alors comme je peux pas aider la personnne je me suis dis que peut etre qq un pourrais le faire, j'ai mm pas chercher a lire le sujet, je connais rien du pascal et suis pas specialement une bete en programmation, j'ai juste fais un peux de C.
Voilà l'histoire.
merci
:hello:

gilou

100% d'accord avec toi Biface.
A+,

BifaceMcLeOD

C'est effectivement un problème classique. Ceci dit, ne le prends surtout pas mal, mais je pense que personne ici n'acceptera de te donner la solution toute faite.

Les forumeurs seront tout à fait disponible pour répondre à un problème précis (par exemple, j'ai tel code, tel résultat, pourquoi ça ne marche pas ?), mais pas pour faire le boulot à ta place (et s'il te plait, ne tire pas sur le messager ! :( -- le messager, en l'occurrence, c'est moi).

Maintenant, je veux bien te donner quelques conseils méthodologiques si tu es un peu perdu par la grosseur de la tâche à réaliser. Il y a 2 grosses parties dans ce projet. La manipulation des villes (donc en particulier les algorithmes de plus court chemin) d'une part, et la partie graphique d'autre part.

Je te conseille vivement de travailler d'abord et exclusivement sur les algorithmes et les structures de données, et de faire un programme qui se contente du mode texte pour dialoguer avec l'utilisateur (avec des WriteLn et des ReadLn). Une fois cette partie terminée, toutes tes structures de données et tes algorithmes seront en place.

Une fois que tout cela marchera, tu pourras attaquer la partie graphique. Normalement, tu n'auras quasiment pas à modifier ce que tu as fait pour le mode texte, si c'est correctement écrit (voire pas du tout du tout si c'est vraiment très bien écrit).

ben2655

Voilà, je suis en galere pour resoudre ce sujet.
Etant donné que c un sujet archi "classique", je voudrais savoir si qq un ne l'avais pas deja fais, auquel cas, ce serais tres sympa de m'envoyer le corrigé.
Sinon, si qq un pouvais m'aider ce serais plus que sympa.
Je compte sur l'entraide et l'esprit hardware.
Voici le sujet, merci de me repondre sur ben2655@caramail.com

Merci a tous.

http://j.hayot.free.fr/pascal.jpg