code of trace path

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

[Walter Roberson]

Are you trying to say that you want to create paths from (1,1) to (3,3) in which any one row or column is visited at most twice?

Is the path to be 4-connected or 8-connected (diagonal moves allowed) ?

Are you trying to generate all such paths, or the shortest such path, or any one such path?

[huda nawaf]

thanks walter,

yes, at most twice for example

i did not fully understand what r u mean regarding 4-connected or 8-connected

but , i can say to u the moving be either right or down or diagonal.

Also, i did not want shortest path and also not optimal, i need any path begin (1,1) and access the goal (3,3) with consider the conditions above.

my idea is get the path then improve it using PSO

[huda nawaf]

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]

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]

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

Answer 1

[Walter Roberson]

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.

Answer 2

[Dr. Seis]

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.

[Dr. Seis]

I think I might understand - if you have an MxN matrix to trace the path through, then the sum of each column must be <= M-1 and the sum of each row must be <= N-1. Let me know if this is what you mean.

[Walter Roberson]

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]

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

[Dr. Seis]

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.

Answer 3

[huda nawaf]

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

[huda nawaf]

regarding last thing I wrote it, I will modify it

I got :

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

[Dr. Seis]

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

[Walter Roberson]

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]

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

Answer 4

[Dr. Seis]

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

[Dr. Seis]

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]

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.

[Dr. Seis]

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.