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

*No products are associated with this question.*

Answer by Walter Roberson
on 23 Jan 2012

Accepted answer

Your conditions appear to translate as:

- first move can be in any of the three directions (random choice of 3)
- after that, the next move cannot be in the same direction as the one immediately previous (random choice of 2)
- 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 by Dr. Seis
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.

Show 1 older comment

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

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

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

Show 1 older comment

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

Answer by Dr. Seis
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

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

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

Related Content

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

Learn moreOpportunities for recent engineering grads.

Apply Today
## 5 Comments

## Walter Roberson (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/26741#comment_58851

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 (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/26741#comment_59071

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 (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/26741#comment_59075

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 (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/26741#comment_59076

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 (view profile)

Direct link to this comment:http://www.mathworks.com/matlabcentral/answers/26741#comment_59104

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