Jump to content

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


Recommended Posts

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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).

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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) ?

Link to comment
Share on other sites

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...

Link to comment
Share on other sites

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 :)

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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.

Link to comment
Share on other sites

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

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...