Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

code of trace path

Asked by huda nawaf on 22 Jan 2012

hi, say have this array: x=

       1     0     0
       0     0     0
       0     0     0  

i want anyone help me to write algorithm to trace any path begin from (1,1) and have to stop in (3,3), but when passing position such x(i,j),x(i,j) will be =1 , otherwise will be zero where sum(Xij)<=2 if j=1:3 or sum(xij)<=2 if i=1:3.

it is like sequence alignment algorithm, but I do not want use dynamic programming algo. to do this task. I wrote code but did not get the exact result who can help me? Thanks in advance

5 Comments

huda nawaf on 23 Jan 2012

walter,i wrote code , but I do not feel it is true.

I used cases to chose right or diagonal or down and each case have many many if statements, i do not feel it is true
do u need that code? if so i will send it

Walter Roberson on 23 Jan 2012

To check: acceptable moves are right, down, diagonal up left, diagonal up right, diagonal down left, diagonal down right, but not plain up, and not plain left?

Is 3x3 the sample size for this question, but the real task will use larger matrice? Or is 3x3 the actual size you will be using?

huda nawaf on 23 Jan 2012

3*3 is sample , real matrix is much larger

move is just right , down,
and just diagonal down right. there is no move to left or up

huda nawaf

Tags

Products

No products are associated with this question.

4 Answers

Answer by Walter Roberson on 23 Jan 2012
Accepted answer

Your conditions appear to translate as:

  1. first move can be in any of the three directions (random choice of 3)
  2. after that, the next move cannot be in the same direction as the one immediately previous (random choice of 2)
  3. when you reach the bottom or right edge if you do not already happen to be at the bottom right corner, you are exactly one space away and your move is forced and legal.

I have not proven that you cannot intersect the edges except for the target or one space from the target, but my mental modeling is that it is the case for square matrices under those move restrictions.

0 Comments

Walter Roberson
Answer by Elige Grant on 23 Jan 2012

Not entirely clear on an acceptable result, but if this is an example of an acceptable result:

1  1  1
0  0  1
0  0  1

Then this will find a random path for any MxN matrix:

% User Defined %
%%%%%%%%%%%%%%%%
M = 3; % number of rows
N = 3; % number or cols
overlap_allowed = 0; % Allow overlap of positions, 1-Yes, 0-No
% Define possible moves on 3x3 grid below
% U-Up, D-Down, L-Left, R-Right, S-Stay
move_grid = [0, 0, 0;...  % [UL, U, UR
             0, 0, 1;...  %   L, S,  R
             0, 1, 1];    %  DL, D, DR]   
% Automatically Defined %
%%%%%%%%%%%%%%%%%%%%%%%%%
path = zeros(M,N); path(1) = 1;   % Initialize path      
move_nums = 1:9;
move_inc = zeros(3,3,2);          % Initialize movement increment index
move_inc(:,:,1) =  [-1,-1,-1;...
                     0, 0, 0;...
                     1, 1, 1];
move_inc(:,:,2) =  [-1, 0, 1;...
                    -1, 0, 1;...
                    -1, 0, 1];                
moves_allowed = ones(M,N,9);      % Define moves allowed for each position
moves_allowed(1,:,[1 4 7])=0;
moves_allowed(end,:,[3 6 9])=0;
moves_allowed(:,1,[1 2 3])=0;
moves_allowed(:,end,[7 8 9])=0;
moves_allowed(:,:,~move_grid)=0;
curr_pos = [1,1]; count = 0;
while path(M,N) == 0
  temp = reshape(moves_allowed(curr_pos(1),curr_pos(2),:),...
                 size(move_nums));
  poss_move = move_nums(temp==1);
  if ~overlap_allowed
      temp_poss_move = ones(1,length(poss_move));
      for i = 1 : length(poss_move)
          if path(curr_pos(1)+move_inc(poss_move(i)),...
                  curr_pos(2)+move_inc(poss_move(i)+9)) == 1
              temp_poss_move(i) = 0;
          end
      end
      poss_move = poss_move(temp_poss_move == 1);
  end
  rand_move = randperm(length(poss_move));
  curr_move = poss_move(rand_move(1));
  curr_pos = curr_pos + [move_inc(curr_move),move_inc(curr_move+9)];
  path(curr_pos(1),curr_pos(2)) = path(curr_pos(1),curr_pos(2))+1;  
  count = count + 1;
end
disp(count)
disp(path)

I also included the option for being able to overlap positions, but I assume you did not want to do this for your example. If the example of the acceptable result is, in fact, not acceptable then I can make that modification. Let me know.

4 Comments

Walter Roberson on 23 Jan 2012

Hmmm, exact number of times allowed is not as clear as I thought I had pinned down. We will need clarification on this. Exactly 2 simplifies to the logic I gave.

huda nawaf on 24 Jan 2012

thanks Elig and walter,
Elig,I will try your code, yesterday walter suggested good thing, I did not consider it before.
He said that the next move has to be (random choice of 2)
So, I'm modifying my code according to what said.

I just I see you example above, in fact the sum of each column ~=M-1, also for rows ~=N-1.
as I told earlier, 3*3 matrix is just sample, my matrix is much larger,
they are long sequences
and sum(xij)<=2 mean the no. of gaps allowed within sequence, and chose 2 as a simple case . In fact I'm still not sure for the no. of allowed gaps within sequences, and is it fixed for all sequences or not, I need study more and more. But now I need to apply simple case where the no. of gaps is 2.
for ex.
'AC--ACACTA' .in this example the no. of allowed gaps is 2.
Elig, if u can modify your code , please do.
Regarding my code according to walter's suggestions , I will display it here after I finish it

Elige Grant on 24 Jan 2012

As a quick "fix" you can simply run my code and check (at the end) to see if the sums of the rows and columns conform to your specifications... if it doesn't conform, then it can simply be re-ran to generate a new random path.

The code above should work for any MxN matrix where M>=2 and N>=2.

Elige Grant
Answer by huda nawaf on 24 Jan 2012

hi walter,

this is my code,it is give me good result except one problem I faced it in edges. at first, in the first move I fixed one case 'right' just to see result, then made the move is random choice of 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% s1 = 'ACGGC'; s2 = 'ACCTT';

M=length(s1); N=length(s2);

for i=1:M

    for j=1:N
        if i==1 & j==1
         par_alig(i,j)=1;
        else
            par_alig(i,j)=0;
        end;end;end

for pop=1:1%%%%%%%% at first one individual from population

              %%%%direct=ceil(3*rand);
              dir='right';
                %switch (direct)
                  % case 1
               [z xy]=move1(par_alig,xy(1),xy(1),M,N,'right');
                       while 1
                           if xy(1)==M & xy(2)==N
                               break; end
                       dir=direction(dir);
                       [z xy]=move1(z,xy(1),xy(2),M,N,dir);
                       end; end 

%%%%%%direction fun.%%%%%%%%% function z=direction(x) switch (x) case 'right'

     R = 2 + randint(1)*(3-2);
     if R==2
         z='diagonal';
     else
         z='down';
     end
         case 'diagonal'
         R=ceil(3*rand)

if R==1

         z='right';

elseif R==2

    z='diagonal';

else

         z='down';

end

    case 'down'
    R = 1 + randint(1)*(2-1);
     if R==1
         z='right';
     else
         z='diagonal';
     end  
end

return

end

%%%%%%%%%%%%%%%% move1 fun.%%%%%%%%%% function [s1 z]=move1(s,x,y,L1,L2,direction) switch (direction)

    case 'right'
        if y<L2
    y=y+1;s(x,y)=1; end
    case 'diagonal'
        if x<L1 & y<L2
     x=x+1;y=y+1;s(x,y)=1; end
    case 'down'

if x<L1

    x=x+1;s(x,y)=1;end;end

z(1)=x;z(2)=y;s1=s; return end I found out that when the moving access to last column (may last row) not constraint with the condition sum(xij)<=2

for ex. , I got this 1 1 0 0 0

     0     0     1     0     0
     0     0     0     1     1
     0     0     0     0     1
     0     0     0     0     1
thanks

4 Comments

Elige Grant on 24 Jan 2012

Oh, ok. So the sum across all rows and all columns cannot exceed 2 for all MxN matrices?

Walter Roberson on 24 Jan 2012

Ah, my mental model of the process was incorrect. Okay, so if you intersect an edge more than 1 unit from the goal, then rerun. I would need to think about whether I could fix the algorithm.

huda nawaf on 24 Jan 2012

yes Elige.
please walter, i did not understand what u mean about intersect an edge more than 1 unit from the goal? give me example please

huda nawaf
Answer by Elige Grant on 24 Jan 2012

In this version, there is a check that will modify the possible path directions based on whether the row/col it can move to already has reached the maximum number of occupations. However, this check doesn't handle the bottom and right edges properly so there is still the check at the end to make sure that nothing is violated. It should be significantly fast than the previous version for larger matrices.

% User Defined %
%%%%%%%%%%%%%%%%
M = 5; % number of rows
N = 5; % number or cols
overlap_allowed = 0; % Allow overlap of positions, 1-Yes, 0-No
M_allowed = 2; % number of times allowed to occupy a specific column
N_allowed = 2; % number of times allowed to occupy a specific row
% Define possible moves on 3x3 grid
% U-Up, D-Down, L-Left, R-Right, S-Stay
move_grid = [0, 0, 0;...  % [UL, U, UR
             0, 0, 1;...  %   L, S,  R
             0, 1, 1];    %  DL, D, DR]   
% Automatically Defined %
%%%%%%%%%%%%%%%%%%%%%%%%%
path = zeros(M,N); path(1) = 1;   % Initialize path      
move_nums = 1:9;
move_inc = zeros(3,3,2);          % Initialize movement increment index
move_inc(:,:,1) =  [-1,-1,-1;...
                     0, 0, 0;...
                     1, 1, 1];
move_inc(:,:,2) =  [-1, 0, 1;...
                    -1, 0, 1;...
                    -1, 0, 1];                
moves_allowed = ones(M,N,9);      % Define moves allowed for each position
moves_allowed(1,:,[1 4 7])=0;
moves_allowed(end,:,[3 6 9])=0;
moves_allowed(:,1,[1 2 3])=0;
moves_allowed(:,end,[7 8 9])=0;
moves_allowed(:,:,~move_grid)=0;
curr_pos = [1,1]; steps = 0; tries = 1;
while path(M,N) == 0
  temp = reshape(moves_allowed(curr_pos(1),curr_pos(2),:),...
                 size(move_nums));
  poss_move = move_nums(temp==1);
  if ~overlap_allowed
      temp_poss_move = ones(1,length(poss_move));
      for i = 1 : length(poss_move)
          if path(curr_pos(1)+move_inc(poss_move(i)),...
                  curr_pos(2)+move_inc(poss_move(i)+9)) == 1
              temp_poss_move(i) = 0;
          end
      end
      poss_move = poss_move(temp_poss_move == 1);
  end
  temp_poss_move = ones(1,length(poss_move));
  for i = 1 : length(poss_move)
      if sum(poss_move(i)==[1,2,3,4,5,6]) == 1
          if sum(path(:,curr_pos(2)+move_inc(poss_move(i)+9))) ...
                      >= M_allowed
          	temp_poss_move(i) = 0;
          end
      end
      if sum(poss_move(i)==[1,2,4,5,7,8]) == 1
          if sum(path(curr_pos(1)+move_inc(poss_move(i)),:)) ...
                      >= N_allowed
          	temp_poss_move(i) = 0;
          end
      end
      if sum(poss_move(i)==[1,3]) == 1
          if sum(path(:,curr_pos(2))) >= M_allowed
                  temp_poss_move(i) = 0;
          end
      end
      if sum(poss_move(i)==[1,7]) == 1
          if sum(path(curr_pos(1),:)) >= N_allowed
                  temp_poss_move(i) = 0;
          end
      end   
  end
  poss_move = poss_move(temp_poss_move == 1);
  rand_move = randperm(length(poss_move));
  curr_move = poss_move(rand_move(1));
  curr_pos = curr_pos + [move_inc(curr_move),move_inc(curr_move+9)];
  path(curr_pos(1),curr_pos(2)) = path(curr_pos(1),curr_pos(2))+1;  
  steps = steps + 1;
  if sum(path(:,curr_pos(2))) > M_allowed || ...
     sum(path(curr_pos(1),:)) > N_allowed
      path = zeros(M,N); path(1) = 1;   % Initialize path
      curr_pos = [1,1]; steps = 0; tries = tries+1;
  end
end
disp(tries) % Number of redo times (because of definition violations)
disp(steps) % Number of steps in output path
disp(path)  % Matrix of path

3 Comments

Elige Grant on 24 Jan 2012

If you are going to be looking for pathways through very large MxN matrices, then I have a "quick fix" for that too. Otherwise for 5x5 matrices, it shouldn't take but a few tries to get an acceptable path.

huda nawaf on 25 Jan 2012

thanks
Elige,I got good result with your code.
I also modify my code and get acceptable result , but I think your result is best.
because I did not deal with edges well, and did not understand what was walter meaning in last comment.
Elige, why u must fix your code with larger matrix ? isn't working generally ?
if need fix please do, because my matrix is very large , they are long sequences.

Elige Grant on 25 Jan 2012

It worked in general, but it wasn't well suited for large matrices. I tried it on a 50x50 matrix and after waiting several minutes I had to kill it. With the modifications (included above) it took less than a second to reach a solution.

Elige Grant

Contact us