[MatLab/Scilab] Créer un chemin dans une matrice

[MMiguel]

Bonjour,

J'ai un soucis pour créer un algorithme sous Matlab.

Au départ j'ai une matrice de 0 et 1 etle but de l'algo et de créer un chemin allant de gauche à droite mais en passant uniquement par les 1.

Il peut se déplacer que verticalement et horizontalement et j'ai réussi à faire un algo mais il fait se déplace pas comme je le souhaiterais.

Je sais qu'un algo est deja créer sur internet mais je ne sais plus ou je l'ai vu et donc je ne le trouve plus.

Merci pour toutes réponses.

Michaël

[Sentinel]

Avec une pile pour tester tous les chemins, c'est facile.

[MMiguel]

Avec une pile pour tester tous les chemins, c'est facile.

Si tu as un algorithme à me filer, je veux bien

[Sentinel]

Il te faut une classe qui contient deux champs : case courante, case précédente.

Tu places ta case d'entrée (courante=case d'entrée, précédente=null) sur la pile.

Ensuite, tant que tu n'as pas atteint la case de sortie :

Tu dépiles une case. Tu regardes si c'est la case de sortie.

- Si oui, fini

- Si non, tu cherches toutes les cases valides adjacentes, tu les mets sur la pile.

Quand tu as atteint la sortie, il suffit de dépiler l'historique des cases précédentes pour obtenir le chemin.

[MMiguel]

Merci pour cette info, je vais essayer comme ça, mais je doute pouvoir y arriver, je suis nul en programmation...

[MMiguel]

Laisse tomber, je ne comprends pas du tout comment faire ce modi programme.

Merci

[lorinc]

ben c'est à dire qu'en matlab... cela dit, je suis sur que ton truc se trouve dans les tollbox de comm

[MMiguel]

Je travail sous Scilab et dans Matlab j'ai pas trouvé.

J'ai trouvé quelques choses mais c'est pour un graphe et je travail dans une matrice

[theocrite]

Han ! Lorinc qui incite à utiliser Matlab plutôt que scilab.

Bon l'algo de Sentinel est bien (faut pas oublier de faire pour toutes les entrées possible quand même).

Si tu veux un algo, je pense que tu peux te tourner vers les chaines cachés de markov : http://en.wikipedia.org/wiki/HMM ou plutôt vers l'algo de Viterbi http://en.wikipedia.org/wiki/Viterbi_algorithm

Ce dernier permet par exemple de faire de la reconnaissance vocale :

Tu fais une matrice avec en ordonée un mot dans la base de connaissanves et en abscice la voix à analyser.

La matrice est construite avec les distances locales et on cherche le shortest path vertical.

Si ce shorest path est inférieur à un seuil, alors bigo, le mot est reconnu.

Dans ce cas, c'est beaucoup plus simpe, vu que la matrice est binaire. Pas de notions de distance, juste un test 0 / 1.

EDIT : Bon en fait je viens de relire c'est pas l'algo qui bloque c'est le codage...

Perso je ne sais pas coder en scilab, mais je peux m'y mettre pourquoi pas, c'est toujours intéressant.

Tu peux nous mettre ce que tu as fait pour le moment ? Où est ce que ça bloque et pourquoi (avec le message d'erreur qui va avec).

[MMiguel]

Merci theocrite,

Je suis vraiment pas doué en programmation et j'ai pas réellement compris l'algo de Sentinel.

Alors pour le moment j'ai encore fait aucun programme, j'essais de comprendre ou de faire un algo.

Pour commencer si tu pouvais réécrire mais avec des thermes plus simple l'algo de Sentinel ça pourrais m'aider

Mon soucis est que je ne vois pas comment faire car il y aura plusieurs chemin possible

Merci

[lorinc]

En fait, c'est pour faire quoi ?

Viterbi, je suis sûr (et même certain) que tu le trouvera dans n'importe quel module de communication de Matlab/Scilab/Octave

le but c'est quoi : avoir un chemin ? tous les chemins ? le plus court chemin (mettant un metrique sur les saut possible) ?

[MMiguel]

Voici mon sujet:

J'ai une matrice 20*20 de 0 et 1 et je dois tester tous les chemins possibles si il y en a, pour trouver le chemin le plus dans la matrice en passant uniquement par les 1.

Il y des modules shortest_path dans matlab et scilab mais c'est uniquement pour les graphes.

Aucune idée comment faire...

[Sentinel]

Solution de contournement :

Tu transformes ta matrice de 0/1 en graphe non-orienté.

Les noeuds du graphe sont tes cases 1, et tu crées une transition entre deux cases 1 adjacentes.

Ensuite, tu demandes à ton ami matlab de résoudre le chemin :)

[MMiguel]

Merci pour cette idée, maintenant je vais essayer de trouver tous les chemins possibles sans prendre en compte les 0 et les 1 dans la matrice et ensuite chaque chemin je le transforme en graphe et je prends la fonction shortest_path.

Merci beaucoup

[Sentinel]

Non non non, tu ne cherches rien à la main !

Il faut que tu crées un graphe. Tu considères toutes tes cases 1 comme des noeuds. Ensuite, si dans ta matrice deux cases 1 sont verticalement ou horizontalement adjacentes, tu crées une transition entre les noeuds les représentant dans le graphe.

Après, il ne reste plus qu'à utiliser les fonctions standard de parcours de graphe.

[MMiguel]

Avec pas mal d'aide voici ce que cela donne:

//////////////////////////////////////////////

// Définition des paramètres basics du graphe

//////////////////////////////////////////////

larg=lImage;

haut=hImage;

nb_sommets = larg*haut;

connection_1 = zeros(1,1);

X = zeros(1,larg*haut);

Y = zeros(1,larg*haut);

for ii=1:larg*haut

X(ii) = modulo( ii-1, larg ) + 1;

Y(ii) = haut - floor( (ii-1)/larg );

end // for ii

connection_1(1) = 1;

// creation du graphe avec connection de chaque noeud avec lui-même

g=make_graph('graph',0,nb_sommets,connection_1,connection_1);

g('node_x')=100*[X];

g('node_y')=100*[Y];

//////////////////////////////////////

// Création des connections

//////////////////////////////////////

for iii=2:haut-1

for jjj=2:larg-1

if(Image(iii,jjj)==1)

if Image(iii-1,jjj)==1

n1 = jjj+(iii-1)*larg;

n2 = jjj+(iii-1-1)*larg;

g=add_edge(n1,n2,g);

end

if Image(iii+1,jjj)==1

n1 = jjj+(iii-1)*larg;

n2 = jjj+(iii+1-1)*larg;

g=add_edge(n1,n2,g);

end

if Image(iii,jjj+1)==1

n1 = jjj+(iii-1)*larg;

n2 = jjj+1+(iii-1)*larg;

g=add_edge(n1,n2,g);

end

if Image(iii,jjj-1)==1

n1 = jjj+(iii-1)*larg;

n2 = jjj-1+(iii-1)*larg;

g=add_edge(n1,n2,g);

end

end // if(Image(iii,jjj)==1)

end // for x

end // for y

// suppression de la première connection noeud 1 au noeud 1

g = delete_arcs([1 1],g);

//////////////////////////////////////

// Affichage du graph

//////////////////////////////////////

show_graph(g);

//edit_graph(g);

tt=1;

for aa=1:hShape

for bb=1:lShape

[p(tt),lp(tt)]=shortest_path(aa,bb,g,'length');

tt=tt+1;

end

end

Mais malheureusement je dois utiliser les composantes connexes donc je dois repartir dans une autre redirection.

Je le donne quand même au cas ou qqun ai besoins d'aide.

Merci