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

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.

I will appreciate your help.

Answer 1

[rifat]

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

[bkshn]

Hello rifat

Thanks alot.

it works and I can see the value of each element.

Could you help me How can I have the number of column of each element.

for example I want to have a vector of column of elements that are selected randomly.

Thanks

[rifat]

just add

columnVector(row)=col;

within the loop. columnVector will contain the column indices.

[bkshn]

Hello rifat

Could you explain more please?

what do you mean by columnVector?!!

[rifat]

it shows the column index of the elements

[bkshn]

Hello rifat

thanks for your answers.

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?

Answer 2

[Image Analyst]

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]

Well nevermind - looks like you have already Accepted an answer that works for you.

[bkshn]

As you said above code works for me, But I want to know about it more and more.

Thank you about Link.I read it but I couldn't find How can I do random search to find shortest path!!

[Image Analyst]

I don't understand rifat's code at all, that's why I suggested other methods that do create paths. I don't see how that code builds up a connected path at all. What he calls "list" changes at every row. Nothing is saved. No path is constructed. The function randSelection() doesn't even return anything. I don't think it does create a connected path like you asked, but you say it did, so whatever...... Maybe I've just totally misinterpreted what you or he said/asked.

[bkshn]

As I asked rifat, I want to have this vector(shortest path) as output of this function,when I run this code I see the value of each random column in "ans" variable of matlab.

Could you help me how can I find shortest path on a matrix from top to bottom by random search?

I read the blog that you introduced. But I can't find any thing.

[Image Analyst]

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]

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.

I'll appreciate your help.