code of trace path

2012 1 22
4 个回答
回答已采纳
3 次查看（30 天）

0 个投票

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 个评论
显示 3更早的评论 隐藏 3更早的评论

Walter Roberson
Walter Roberson 2012-1-22
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
huda nawaf 2012-1-23
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
huda nawaf 2012-1-23
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
Walter Roberson 2012-1-23
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
huda nawaf 2012-1-23
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

请先登录，再进行评论。

请先登录，再回答此问题。

 采纳的回答

Walter Roberson
Walter Roberson 2012-1-23

0 个投票

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.

更多回答（3 个）

Dr. Seis
Dr. Seis 2012-1-23

0 个投票

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 个评论
显示 2更早的评论 隐藏 2更早的评论

Dr. Seis
Dr. Seis 2012-1-23
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
Walter Roberson 2012-1-23
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
huda nawaf 2012-1-24
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
Dr. Seis 2012-1-24
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.

请先登录，再进行评论。

huda nawaf
huda nawaf 2012-1-24

0 个投票

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 个评论
显示 2更早的评论 隐藏 2更早的评论

huda nawaf
huda nawaf 2012-1-24
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
Dr. Seis 2012-1-24
Oh, ok. So the sum across all rows and all columns cannot exceed 2 for all MxN matrices?
Walter Roberson
Walter Roberson 2012-1-24
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
huda nawaf 2012-1-24
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

请先登录，再进行评论。

Dr. Seis
Dr. Seis 2012-1-24

0 个投票

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 个评论
显示 1更早的评论 隐藏 1更早的评论

Dr. Seis
Dr. Seis 2012-1-24
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
huda nawaf 2012-1-25
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
Dr. Seis 2012-1-25
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.

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Creating and Concatenating Matrices 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by