Discussion :

[tagsOf]

Salut à tous,

Je dois implémenter une heuristique en C du célèbre problème du voyageur de commerce, qui consiste à limiter la recherche de parcours au k villes voisines les plus proches attendant encore d'être visitées. On fixe k arbitrairement en fonction du nombre de ville.

On suppose déjà implémenté une matrice qui contient toutes les distances entre toutes les villes.

Je ne sais pas encore trop par ou commencer, je souhaiterai seulement que vous me proposiez non pas la solution, mais des idées, pour savoir vers ou me dirigez.

Merci d'avance

[ToTo13]

Bonjour,

étant donné que tu sais exactement ce que tu veux faire, il ne te reste plus qu'à faire :
- soit une recherche exhaustive en limitant le nombre de ville suivantes possible à K. Ce qui te diminuera considérablement ton arbre de recherche.
- modifier la matrice de voisinage en mettant une distance infinie pour les villes qui ne sont pas les K plus proches de la ville étudiée. Ensuite, il ne reste plus qu'à lancer une méta-heuristique : recuit simulé (la plus utilisée pour le voyageur de commerce), tabou, ...

[tagsOf]

Tu pense que l'arbre est la meilleure structure pour implémenter cette heuristique ?

Merci pour ta contribution !

[benDelphic]

la méthode de SEP sera je pense très efficace car les branches sont bien définies.
il te reste le mode d'évaluation par exemple les quasi-arbres .

[ToTo13]

Bonsoir,

j'ai pas dis la meilleure et encore moins la plus efficace !!!
Je dis que c'est la plus compréhensible et sans doute la plus facile.

[tagsOf]

J'ai essayé de trouver une implémentation à ce problème, mais il s'avère que cela est plus difficile que ca ne le paraissait.

Notre prof nous a fait allusions a l'utilisation pour nous aider du problèmes des n-reines, mais j'avoue ne pas voir le rapport entre ces 2 problèmes. On nous a aussi parler de "trier la matrice de distance" ... la pareille je ne vois pas l'interet.

D'une manière générale, je ne vois pas comment gérer les villes déja visité de celle qui ne le sont pas encore...

Si vous avez des idées pour m'aiguiller davantage ou m'expliquer vos idées ce serai sympa !

Merci d'avance !

[pseudocode]

Notre prof nous a fait allusions a l'utilisation pour nous aider du problèmes des n-reines, mais j'avoue ne pas voir le rapport entre ces 2 problèmes. On nous a aussi parler de "trier la matrice de distance" ... la pareille je ne vois pas l'interet.

hum... il a l'air super pédagogue ton prof d'algo.

Je ne sais pas trop s'il cherche à vous orienter sur "Dijkstra" ou sur l' "Ordered Greed".

[tagsOf]

Bonjour à tous,

Je dois programmer en C une heuristique du voyageur de commerce, et d'après notre prof, la clé résulte dans la compréhension du lien entre ce problème et celui des n reines (connu sous "problème des 8 reines") ...

Il semblerai que les booléen soit la pour indiquer si une ville a déja été visité ou pas...

Ca vous parle peut être plus qu'a moi...

N'hesitez pas si vous avez des idées ou des éléments de réponse ...

PS: J'ai déja codé l'algorithme naïf (passé en vue toutes les permutations) sans passer par les n reines.

L'heuristique que je dois implémenté limite a chaque fois la recherches a k villes parmi celle pas encore visité au lieu de toutes les villes pas encore visités (on réduit l'arbre).

[Emmanuel Delahaye]

Bonjour à tous,

Je dois programmer en C une heuristique du voyageur de commerce, et d'après notre prof, la clé résulte dans la compréhension du lien entre ce problème et celui des n reines (connu sous "problème des 8 reines") ...
<...>

Aucun rapport avec le langage C. C'est un problème d'algorithme

http://fr.wikipedia.org/wiki/Probl%C...des_huit_dames

http://fr.wikipedia.org/wiki/Probl%C...ur_de_commerce

[ToTo13]

Bonjour,

Il semblerai que les booléen soit la pour indiquer si une ville a déja été visité ou pas...

tu auras juste un champ ou un tableau qui te permettra de savoir si une ville a déjà été visitée.

PS: L'heuristique que je dois implémenté limite a chaque fois la recherches a k villes parmi celle pas encore visité au lieu de toutes les villes pas encore visités (on réduit l'arbre).

C'est ce que je t'ai expliqué plus haut.
En fonction du critère que tu choisis (distance entre les villes, temps de déplacement entre les villes, ...) tu fais un tri afin de les classer de la plus proche à la plus éloignée. Attention de ne pas prendre en compte celles déjà visitées.