J'ai un tableau a deux dimensions qui represente ma zone a parcourir, avec certaines cases a 0 ( franchissables ) et d'autres a 1 ( infranchissables ). On représente ainsi un rectangle de terrain comportant des obstacles.
Mon but est de passer au moins une fois sur chaque case franchissable, en un trajet minimum.
 
J'arrive a parcourir entierement mon tableau tout en évitant les obstacles, mais le trajet obtenu est loin d'etre optimal... Quelqu'un a-t-il une idée ou connait-il un algorithme d'optimisation pour un tel parcours?

Regarde du coté de la recherche operationnelle (algo du parcours le plus court). Désolé, j'ai plus l'algo en tete, t'as pas fait ca en cours des fois ? (avec les files d'attentes etc...)

Ben si on a fait des parcours de graphes en info; Mais il ne s'agissait de parcours ou on avait le droit de sauter d'un sommet a n'importe quel autre ( depth-first, breadth-first, etc... ). Dans mon cas tu ne peux aller d'un sommet a l'autre que s'ils sont reliés par une arete.
Pour comprendre le probleme il faut s'imaginer un robot mobile qui parcourt le terrain. La il devient évident que ces algorithmes la ne me sont d'aucun secours.

A vue de nez c'est NP Complet ton pb.

 
Ouais non, je parlais pas de ca... désolé, j'ai al flemme de rechercher mes cours

 
Ouais mais je cherche pas un algo de calcul direct de la meilleure solution, je cherche des idées pour optimiser une solution naive.

Quelles hypothèses a-t-on sur les obstacles ?
 
Tu peux avoir des terrains comme ça ?
 

?

Les obstacles peuvent avoir n'importe quelle forme, tant que la zone a parcourir reste connexe.

Sur de petites dimensions, tu dois pouvoir décomposer ton problème comme un arbre (assez explosif, je l'accorde), où tu ne considères le retour arrière que si tu as marqué tous les noeuds connexes de ton noeud courant. Si tu as plus d'une possibilité tu débutes un nouveau sous graphe. Si tu es coincé, tu repars en arrière. Bon, c'est une heuristique pourrie... Surtout qu'elle risque de foirer.

OK, donc il existe toujours un chemin (et donc un chemin optimal).

 
Si je commence en X, ton heuristique arrive à un résultat impossible.

Adapter l'algo de Floyd Djikstra?? En considerant chaque point de ta matrice comme le sommet d'un graphe de taille n*n...
 
 
A+,

Parce qu'il manque la condition d'arrêt.
 
Mais je suis d'accord que c'est pas génial.

 
Ah voila, c'est celui la que je cherchait. Y'en a un autre aussi je crois  

Bon je viens de lire dans un bouquin qu'il n'existe pas d'algorithme efficace qui résolve le probleme du parcours hamiltonien...

 
Oui mais il s'agit de passer au moins une fois sur chaque case ( d'ou le coté Hamiltonien ) et pas seulement d'aller d'un point a un autre...