J'aimerais implanter l'algorithme g=E9n=E9tique (http://
khayyam.developpez.com/articles/algo/genetic/)en langage c pour
r=E9soudre le probl=E8me du voyageur de commerce (objectif : minimisation
des distances).
La premi=E8re partie consiste =E0 d=E9terminer tous les chemins possibles
entre les villes (par exemple on consid=E8re 7 villes):
{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},...
Je ne vois pas comment d=E9marrer. Pourriez vous me donner quelques
indications?
Merci par avance.
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
espie
In article , afoufa wrote:
La première partie consiste à déterminer tous les chemins possibles entre les villes (par exemple on considère 7 villes): {1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},... Je ne vois pas comment démarrer. Pourriez vous me donner quelques
Tous les chemins possibles, c'est toutes les permutations de 1..7. En cherchant un peu sur le mot-cle "permutation" tu devrais trouver ton bonheur.
Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus approprie pour demarrer.
Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il te faut, c'est une population "assez grosse", suffisamment aleatoire, et une fonction de mutation/crossover qui preserve la propriete "etre une permutation de 1..7".
In article <7ef7a278-bc53-463b-bd26-18531fb5f0d5@r24g2000yqd.googlegroups.com>,
afoufa <fftunisienne320@gmail.com> wrote:
La première partie consiste à déterminer tous les chemins possibles
entre les villes (par exemple on considère 7 villes):
{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},...
Je ne vois pas comment démarrer. Pourriez vous me donner quelques
Tous les chemins possibles, c'est toutes les permutations de 1..7.
En cherchant un peu sur le mot-cle "permutation" tu devrais trouver
ton bonheur.
Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans
Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus approprie
pour demarrer.
Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour
un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il
te faut, c'est une population "assez grosse", suffisamment aleatoire, et
une fonction de mutation/crossover qui preserve la propriete "etre une
permutation de 1..7".
La première partie consiste à déterminer tous les chemins possibles entre les villes (par exemple on considère 7 villes): {1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},... Je ne vois pas comment démarrer. Pourriez vous me donner quelques
Tous les chemins possibles, c'est toutes les permutations de 1..7. En cherchant un peu sur le mot-cle "permutation" tu devrais trouver ton bonheur.
Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus approprie pour demarrer.
Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il te faut, c'est une population "assez grosse", suffisamment aleatoire, et une fonction de mutation/crossover qui preserve la propriete "etre une permutation de 1..7".
afoufa
On 9 jan, 18:14, (Marc Espie) wrote:
In article .com>,
afoufa wrote: >La première partie consiste à déterminer tous les chemins possible s >entre les villes (par exemple on considère 7 villes): >{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},... >Je ne vois pas comment démarrer. Pourriez vous me donner quelques
Tous les chemins possibles, c'est toutes les permutations de 1..7. En cherchant un peu sur le mot-cle "permutation" tu devrais trouver ton bonheur.
Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus appropri e pour demarrer.
Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il te faut, c'est une population "assez grosse", suffisamment aleatoire, et une fonction de mutation/crossover qui preserve la propriete "etre une permutation de 1..7".
Merci beaucoup pour votre réponse et votre conseil! ca ne m'est pas venue à l'esprit! Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de quelle façon pourrais-je y arriver? Merci par avance.
On 9 jan, 18:14, es...@lain.home (Marc Espie) wrote:
In article <7ef7a278-bc53-463b-bd26-18531fb5f...@r24g2000yqd.googlegroups .com>,
afoufa <fftunisienne...@gmail.com> wrote:
>La première partie consiste à déterminer tous les chemins possible s
>entre les villes (par exemple on considère 7 villes):
>{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},...
>Je ne vois pas comment démarrer. Pourriez vous me donner quelques
Tous les chemins possibles, c'est toutes les permutations de 1..7.
En cherchant un peu sur le mot-cle "permutation" tu devrais trouver
ton bonheur.
Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans
Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus appropri e
pour demarrer.
Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour
un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il
te faut, c'est une population "assez grosse", suffisamment aleatoire, et
une fonction de mutation/crossover qui preserve la propriete "etre une
permutation de 1..7".
Merci beaucoup pour votre réponse et votre conseil!
ca ne m'est pas venue à l'esprit!
Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de
quelle façon pourrais-je y arriver?
Merci par avance.
afoufa wrote: >La première partie consiste à déterminer tous les chemins possible s >entre les villes (par exemple on considère 7 villes): >{1, 2,3,4,5,6,7},{2,1,3,4,5,6,7},{2,3,4,1,5,6,7},... >Je ne vois pas comment démarrer. Pourriez vous me donner quelques
Tous les chemins possibles, c'est toutes les permutations de 1..7. En cherchant un peu sur le mot-cle "permutation" tu devrais trouver ton bonheur.
Ca doit etre dans a peu pres tous les bouquins d'algo. Entre autres dans Knuth, bien sur, meme si c'est sans doute pas le bouquin le plus appropri e pour demarrer.
Nota bene: je ne suis pas trop convaincu que ca soit un bon depart pour un algo genetique. Ca va vite faire une trop grosse population. Ce qu'il te faut, c'est une population "assez grosse", suffisamment aleatoire, et une fonction de mutation/crossover qui preserve la propriete "etre une permutation de 1..7".
Merci beaucoup pour votre réponse et votre conseil! ca ne m'est pas venue à l'esprit! Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de quelle façon pourrais-je y arriver? Merci par avance.
espie
In article , afoufa wrote:
Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de quelle façon pourrais-je y arriver?
C'est un exemple "classique" ou il est plus naturel de proceder recursivement. Si tu stockes toutes tes permutations dans un tableau,
pour generer une permutation: - choisir le premier element - trouver toutes les permutations qui n'incluent pas ce premier element (d'ou la recursion).
Le plus rapide (mais pas forcement le plus intuitif), c'est de gener les permutations a coups de petits echanges... e.g., on part de la liste 1 2 3 4 5 6 7
on garde le 1: on genere les permutations sur 2 3 4 5 6 7
puis on echange le 1 et le 2: 2 1 3 4 5 6 7 on garde le 2: on genere les permutations sur 1 3 4 5 6 7 puis on remet les choses en place et on echange 1 et 3: 3 2 1 4 5 6 7 on garde le 3: on genere les permutations sur 2 1 4 5 6 7 puis on remet les choses en place et on echange 1 et 4: 4 2 3 1 5 6 7 on garde le 4: on genere les permutations sur 2 3 1 5 6 7 ...
In article <c8747413-b1d1-4ee8-9926-937ba6077a07@a6g2000yqm.googlegroups.com>,
afoufa <fftunisienne320@gmail.com> wrote:
Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de
quelle façon pourrais-je y arriver?
C'est un exemple "classique" ou il est plus naturel de proceder
recursivement. Si tu stockes toutes tes permutations dans un tableau,
pour generer une permutation:
- choisir le premier element
- trouver toutes les permutations qui n'incluent pas ce premier element
(d'ou la recursion).
Le plus rapide (mais pas forcement le plus intuitif), c'est de gener les
permutations a coups de petits echanges... e.g., on part de la liste
1 2 3 4 5 6 7
on garde le 1: on genere les permutations sur 2 3 4 5 6 7
puis on echange le 1 et le 2: 2 1 3 4 5 6 7
on garde le 2: on genere les permutations sur 1 3 4 5 6 7
puis on remet les choses en place et on echange 1 et 3: 3 2 1 4 5 6 7
on garde le 3: on genere les permutations sur 2 1 4 5 6 7
puis on remet les choses en place et on echange 1 et 4: 4 2 3 1 5 6 7
on garde le 4: on genere les permutations sur 2 3 1 5 6 7
...
Cependant, pourrait-on éviter de faire 7 boucles "for"?Si oui, de quelle façon pourrais-je y arriver?
C'est un exemple "classique" ou il est plus naturel de proceder recursivement. Si tu stockes toutes tes permutations dans un tableau,
pour generer une permutation: - choisir le premier element - trouver toutes les permutations qui n'incluent pas ce premier element (d'ou la recursion).
Le plus rapide (mais pas forcement le plus intuitif), c'est de gener les permutations a coups de petits echanges... e.g., on part de la liste 1 2 3 4 5 6 7
on garde le 1: on genere les permutations sur 2 3 4 5 6 7
puis on echange le 1 et le 2: 2 1 3 4 5 6 7 on garde le 2: on genere les permutations sur 1 3 4 5 6 7 puis on remet les choses en place et on echange 1 et 3: 3 2 1 4 5 6 7 on garde le 3: on genere les permutations sur 2 1 4 5 6 7 puis on remet les choses en place et on echange 1 et 4: 4 2 3 1 5 6 7 on garde le 4: on genere les permutations sur 2 3 1 5 6 7 ...
