# How can I find a connected path on a matrix by Random Search?

2 views (last 30 days)
bkshn on 26 Apr 2014
Commented: bkshn on 29 May 2014
Hello
I have a matrix . I want to find a connected path of elements from up to button. I want to do it by random search. As I said I want connected path ,then if it selects element [i,j] in row i , in the next row (i+1) it should select from column j-1 or j or j+1. I want to do it by random search.

rifat on 27 Apr 2014
Edited: rifat on 27 Apr 2014
Hope the following function helps.
function[]= randSelection(mat)
[r c]=size(mat);
list=1:c;
for row=1:r
col=list(1 + floor(rand() * length(list)));
l1=col-1;
l2=col+1;
if l1<1
l1=1;
end
if l2>c
l2=c;
end
list=l1:l2;
mat(row,col)
end
rifat on 25 May 2014
it shows the column index of the elements
bkshn on 27 May 2014
Edited: bkshn on 27 May 2014
Hello rifat
when I use columnVector(row)=col; within the loop and run the function in debug mode I can see the index of column, But i don't know how can I have it as output of my function in a vector format like [1;2;3;4;4]?
Could you help me?

Image Analyst on 27 May 2014
Why random? Why not use a function built for it that does it in a systematic way? If you have the Image Processing Toolbox, see http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/ Or you could simply use bwlabel() to get a list of all elements on the path.
Image Analyst on 27 May 2014
Here I make a matrix that has a roughly "S" shaped path. Then I run rifat's code on it:
function test
clc;
mat = [...
0 0 0 1 1 1 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 0 1 1 1 0 0
1 0 0 0 1 0 0
0 1 1 0 0 1 0
0 0 0 1 1 1 0
0 0 0 0 0 0 0]
randSelection(mat)
function[]= randSelection(mat)
[r c]=size(mat);
list=1:c;
for row=1:r
col=list(1 + floor(rand() * length(list)));
l1=col-1;
l2=col+1;
if l1<1
l1=1;
end
if l2>c
l2=c;
end
list=l1:l2;
mat(row,col)
end
Save all of the above code (both functions) in test.m and run it and you'll get this:
mat =
0 0 0 1 1 1 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 0 1 1 1 0 0
1 0 0 0 1 0 0
0 1 1 0 0 1 0
0 0 0 1 1 1 0
0 0 0 0 0 0 0
ans =
0
ans =
0
ans =
0
ans =
1
ans =
1
ans =
0
ans =
1
ans =
0
Now if that's what you want, fine, but I'm just not getting it. I don't see anything that describes the location of the pixels (elements) on the "S" shaped path. I would think the path would be a list of 16 (row, column) coordinates, not a list of 8 zeros or ones (not even really a list since they're not in the same array). But I'm glad it's working for you. I don't need to understand it - you do and that's all that counts.
bkshn on 29 May 2014
Yes You are right. as you see in rifat's code , it selects one random element in each row. but I want to have them as a vector with number of columns. for example I want [3;4;2;1;....] to show me index of columns each random element, I want rifat to explain me more and help me how can I have a vector as output.
Could you help me?
I want to do random search on a matrix to find shortest path.