How to find all possible paths from point A to B in any direction in a matrix?

조회 수: 59(최근 30일)
Mohammed Aasim Shaikh 2020년 9월 27일
댓글: Bruno Luong 2021년 9월 20일
I have a MXN matrix and I select two given points A and B. How do I find and store all the possible unique paths form A to B? There are no constraint on which direction I can go from the current point, it can be up, down, left, right, or diagonal (in all four directions).
댓글 수: 14표시숨기기 이전 댓글 수: 13
John D'Errico 2020년 9월 29일
The important point to reconize is just the sheer enormity of the number of all possilbe paths, even for a small matrix.
Almost always there are better ways to solve a problem than a complete sampling of the space you wish to investigate. This is why optimization methods exist, to help you to avoid brute force sampling schemes.

댓글을 달려면 로그인하십시오.

채택된 답변

Bruno Luong 2020년 9월 29일
편집: Bruno Luong 2020년 11월 20일
Tiny matrix of size 4 x 3.
All paths of two opposite corners:
• 38 paths for 4-connectivity,
• 2922 paths for 8-connectivity
clear
close all
m=4; n=3;
% Adjacent matrix of a graph of 4-connected grid of size m x n
[X,Y] = meshgrid(1:n,1:m);
mxn = numel(X);
I = sub2ind(size(X),Y(1:end-1,:),X(1:end-1,:));
J = I+1;
A = sparse(I,J,1,mxn,mxn);
I = sub2ind(size(X),Y(:,1:end-1),X(:,1:end-1));
J = I+size(X,1);
A = A + sparse(I,J,1,mxn,mxn);
A4 = A + A';
% Adjacent matrix of a graph of 8-connected grid of size m x n
I = sub2ind(size(X),Y(1:end-1,1:end-1),X(1:end-1,1:end-1));
J = I+size(X,1)+1;
A = A + sparse(I,J,1,mxn,mxn);
I = sub2ind(size(X),Y(2:end,1:end-1),X(2:end,1:end-1));
J = I+size(X,1)-1;
A = A + sparse(I,J,1,mxn,mxn);
A8 = A + A';
% source and destination
is = 1; js = 1;
id = m; jd = n;
s = sub2ind([m,n],is,js);
d = sub2ind([m,n],id,jd);
allp4 = AllPath(A4, s, d);
PlotandAnimation(4, A4, allp4, [m,n]);
allp8 = AllPath(A8, s, d);
PlotandAnimation(8, A8, allp8, [m,n]);
%%
function PlotandAnimation(nc, A, allp, sz)
fprintf('%d-connected %d x %d\n', nc, sz);
% Plot and animation
figure
[i,j] = ind2sub(sz,1:prod(sz));
nodenames = arrayfun(@(i,j) sprintf('(%d,%d)', i, j), i, j, 'unif', 0);
G = graph(A);
h = plot(G);
labelnode(h, 1:prod(sz), nodenames)
th = title('');
colormap([0.6; 0]*[1 1 1]);
E = table2array(G.Edges);
E = sort(E(:,1:2),2);
np = length(allp);
for k=1:np
pk = allp{k};
pkstr = nodenames(pk);
s = sprintf('%s -> ',pkstr{:});
s(end-3:end) = [];
fprintf('%s\n', s);
Ek = sort([pk(1:end-1); pk(2:end)],1)';
b = ismember(E, Ek, 'rows');
set(h, 'EdgeCData', b, 'LineWidth', 0.5+1.5*b);
set(th, 'String', sprintf('%d-connected, path %d/%d', nc, k, np));
pause(0.1);
end
end
%%
% EDIT: better code available in the comment
function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
% A is (n x n) symmetric ajadcent matrix
% s, t are node number, in (1:n)
% OUTPUT
% p is M x 1 cell array, each contains array of
% nodes of the path, (it starts with s ends with t)
% nodes are visited at most once.
if s == t
p = {s};
return
end
p = {};
As = A(:,s)';
As(s) = 0;
neig = find(As);
if isempty(neig)
return
end
A(:,s) = [];
A(s,:) = [];
neig = neig-(neig>=s);
t = t-(t>=s);
for n=neig
p = [p; AllPath(A,n,t)]; %#ok
end
p = cellfun(@(a) [s, a+(a>=s)], p, 'unif', 0);
end %AllPath
댓글 수: 4표시숨기기 이전 댓글 수: 3
Bruno Luong 2021년 9월 20일
There are plenty implementations on file exchange

댓글을 달려면 로그인하십시오.

추가 답변(1개)

Stijn Haenen 2020년 9월 29일
With this script you got all possible paths, but it is very slow so you have to optimize it (shouldnt be that hard but dont have time for it anymore).
The script tries every path by going in any of the 8 directions at every step until it reaches its goal position.
clear
a=[1 2 3; 4 5 6];
start1=1;
start2=1;
goal1=2;
goal2=2;
abackup=a;
data=[];
for i=10^(numel(a)-1):10^numel(a)-1
pos1=start1;
pos2=start2;
route_i=num2str(a(pos1,pos2));
j=num2str(i);
abackup=a;
abackup(pos1,pos2)=NaN;
for n=1:numel(j)
if j(n)=='1'
try
if ~isnan(abackup(pos1-1,pos2))
pos1=pos1-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='2'
try
if ~isnan(abackup(pos1-1,pos2+1))
pos1=pos1-1;
pos2=pos2+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='3'
try
if ~isnan(abackup(pos1,pos2+1))
pos2=pos2+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='4'
try
if ~isnan(abackup(pos1+1,pos2+1))
pos1=pos1+1;
pos2=pos2+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='5'
try
if ~isnan(abackup(pos1+1,pos2))
pos1=pos1+1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='6'
try
if ~isnan(abackup(pos1+1,pos2-1))
pos1=pos1+1;
pos2=pos2-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='7'
try
if ~isnan(abackup(pos1,pos2-1))
pos2=pos2-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
if j(n)=='8'
try
if ~isnan(abackup(pos1-1,pos2-1))
pos1=pos1-1;
pos2=pos2-1;
route_i=sprintf('%s%g',route_i,a(pos1,pos2));
abackup(pos1,pos2)=NaN;
if pos1==goal1 && pos2==goal2
data(end+1)=str2num(route_i);break
end
end
catch
end
end
end
end
unique(data)

댓글을 달려면 로그인하십시오.

R2020a

Community Treasure Hunt

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

Start Hunting!