FORUM MP | Algorithmes : Kruskal: Cycle ou non dans mon chemin?

COMMUNAUTE MP

Identifiez vous ...

DOMAINE MP

Bavardages

Langages Généraux

Langages Web

Langages DotNet

Autres langages

Dev. Jeux Video

Sécurité

Sys. Exploitation

Graphismes

Logiciels

Réseaux

Bases de données

Méthodologies

Emplois High-tech

Aide juridique

Articles juridiques

FORUM

CHAT MP IRC

Votre pseudo ...

Srv: irc.moteurprog.com

Chan: #MoteurProg

PARTICIPER

Plus de 3500 emplois.

Visiteur MP

Kruskal: Cycle ou non dans mon chemin?
	Forum : ALGORITHMES Sous Catégorie : Aucune Type du sujet : Sujet Normale FAQ : FAQ ALGORITHMES
		SUIVI PAR MAIL INACTIF
		SUJET NON RESOLU
		SUJET ACTIF
		N'APPARTIENT PAS A LA FAQ

PAGE : [1]

FORUM ALGORITHMES
	Page précedente	Page suivante

ink4
Nouveau membre

Inscrit : 25/05/2006
Messages : 2

#132629 Posté le 05/05/07 à 14:08

Bonjour,

J'ai un sujet du voyageur de commerce a faire. Eh oui je suis encore etudiant...
Pour trouver un des meilleurs chemins, j'ai décidé d'utiliser l'algo de Kruskal pour commencer.
L'etape du tri des aretes dans l'ordre croissant est réussie.
Maintenant il faut que je prenne ces aretes une par une, dans leur ordre croissant, et vérifier que à chaque fois que j'ajoute une arete à mon chemin, elle ne fait pas faire un cycle à mon chemin. Et ca je vois pas comment je peux faire... Smiley

Alors, je sais que pour chaque arete je peut vérifier si ses deux sommets ont déja été utilisé:

1/ Dans le cas ou il y a au moins un sommet non utilisé dans mon chemin, c'est que l'arete ne fait pas de cycle. Donc j'ajoute mon arete.

2/ Dans le cas où les deux sommets de mon arete sont déja utilisés par mon chemin, deux cas se presentent:
a/ soit l'arete relie deux morceaux de chemin, donc la c'est bon;
b/ soit l'arete forme un cycle, la c'est pas bon, donc je prend une autre arete.

C'est ce deuxieme cas (a/ et b/ inclus) que je sais pas comment faire. En tout cas , je connai pas de methode appropriée.

Si vous avez une methode concrete a me donner, je vous remercie d'avance.

PS: n'hésitez pas à me poser des questions si ce n'est pas très clair.

HAUT DE PAGE

Publicité

Inscrit : X
Messages : X

#Aucun

HAUT DE PAGE

ink4
Nouveau membre

Inscrit : 25/05/2006
Messages : 2

#132677 Posté le 06/05/07 à 13:39

Je pense avoir trouvé une reponse. Je vais tester. Je vous tiens au courant si ca marche. (La nuit porte conseil ^^)
Je suis toujours ouvert à d'autres solutions, donc n'hésitez pas.

HAUT DE PAGE

pac
Co-Administrateur
Superviseur :
- Méthodologie.
Modérateur :
- Delphi
Chef de projet(s) :
- Jeu Awalé
- EcoSystem
- MySudoku

Inscrit : 08/04/2004
Messages : 6570

#132681 Posté le 06/05/07 à 15:11

Salut, je ne connais pas l'algo de Kruskal. Pour résoudre le problème du voyageur de commerce, je ne connaissais que 2 solutions, la méthode des algos génétiques et la méthodes des fourmis.

Si tu souhaites réaliser un programme utilisant l'algo de Kruskal, si tu le fais en POO, il n'y a pas de problème pour savoir si une arête est déjà utilisée ou pas. Il suffit d'avoir une classe Ville, une classe Arete avec 2 pointeurs vers les 2 Villes, puis X instances de cette classe qui représenteront chaque des arêtes.

Il faut aussi avoir une liste ou un tableau qui contient dans l'ordre l'ensemble des arêtes. Pour savoir si l'arête est déjà utilisée, il suffit de rechercher dans la liste ou le tableau si l'arête est déjà présente ou pas.

Quel langage utilises-tu pour faire ton algo ? Est-il obligatoire ?
__________________________
Lisez la charte, pensez à regarder la FAQ, les tutoriaux, l'annuaire et faites une recherche dans les forums.
N'oubliez pas le Tag [Résolu]

.

Initiez-vous à Delphi avec Turbo Delphi Explorer, au C ou au C++ avec Code::Blocks et C# avec Visual C# 2005 Express.

HAUT DE PAGE


	Page précédente	Page suivante
FORUM ALGORITHMES

PAGE : [1]

.: Site Web développé par Julien Pichot et l'équipe MPWG avec www.evolvia-web.com :.