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

Question

Mohammed Aasim Shaikh 2020-9-27

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/600589-how-to-find-all-possible-paths-from-point-a-to-b-in-any-direction-in-a-matrix

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

Stijn Haenen 2020-9-27

在 MATLAB Online 中打开

With this script you got all the unique paths, but it is very slow (10 minutes for a 2x3 matrix), so you have to optimize it. Optimizing shouldnt be that hard but i dont have time for it anymore.

It tries every path until it reaches to goal by going in any of the 8 directions (left right up down and diagonal).

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)

Walter Roberson 2020-9-27

在 MATLAB Online 中打开

MATLAB permits recursive functions, using the same syntax as most other programming languages -- which is to say that you just place a call to the function you are in the middle of defining.

The limitation on recursion in MATLAB is that by default only 500 levels of recursion are permitted. However, you can change that by using

set(0,'RecursionLimit',N)

where N is your new depth limit. Be warned that if you do this, then there is a risk of crashing the computation by running out of stack space, as each call takes up memory (a copy of all local variables must be saved.)

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.

请先登录，再进行评论。

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

Answer 1

Bruno Luong 2020-9-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/600589-how-to-find-all-possible-paths-from-point-a-to-b-in-any-direction-in-a-matrix#answer_502291

编辑：Bruno Luong 2020-11-20

在 MATLAB Online 中打开

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

Bruno Luong 2020-11-19

编辑：Bruno Luong 2020-11-20

在 MATLAB Online 中打开

I update here the function Allpath to work on directgraph as well. For dirgraph, if t parameter is NaN this function returns all the path started from s and ended to leaf.

NOTE: It continues to work on undirect graph.

function p = AllPath(A, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   A is (n x n) ajadcent matrix (preferable sparse)
%       it can be symmetric (graph) or unsymmetric (digraph)
%   s, t are node number, in (1:n)
%   NOTE: for digraph, if t is NaN, all paths started from s and ended at a
%       leaf are returned
% 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.
%
% Author: <Bruno Luong> surnamename@yahoo.xx
%
if isgraph(A)
    % graph
    G = graph(A);
    [~, d] = shortestpath(G, s, t);
    if isfinite(d)
        p = AllPathHelper(A, s, t);
    else
        p = {};
    end
else
    % digraph
    if nargin < 3 || isempty(t)
        t = NaN;
    end
    tnotprovide = ~isfinite(t);
    if tnotprovide
        % connect the leaf to a single dummy node t
        n = size(A,2);
        [ss,tt] = find(A);
        leaf = setdiff(tt,ss);
        A(n+1,n+1) = 0;
        A(:,n+1) = sparse(leaf, 1, 1, n+1, 1);
        t = n+1;
    end
    G = digraph(A);
    [~, d] = shortestpath(G, s, t);
    if isfinite(d)
        p = AllPathHelper(A.', s, t);
        if tnotprovide
            % remove the dummy node
            for k=1:length(p)
                p{k} = p{k}(1:end-1);
            end
        end
    else
        p = {};
    end
end
end % AllPath
%%
function tf = isgraph(A)
A = spones(A);
tf = nnz(A-A')==0;
end % isgraph
%%
function p = AllPathHelper(AT, s, t)
% Find all paths from node #s to node #t
% INPUTS:
%   AT is (n x n) transposed of the 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 = AT(:,s);
As(s) = 0;
if nnz(As)==0
    return
end
neig = find(As);
AT(:,s) = 0;
AT(s,:) = 0;
neig = reshape(neig,1,[]);
for n=neig
    p = [p; AllPathHelper(AT,n,t)]; %#ok
end
for k=1:length(p)
    p{k} = [s, p{k}];
end
end % AllPathHelper

Walter Roberson 2021-9-18

Jagan, read about:

breadth-first search (bfs() in MATLAB)
A* algorithm (less common)
Dijkstra's algorithm (very common approach)

If what you need is the "cost" of the shortest path and not the particular edges, then there is an algorithm involving matrix multiplication.

Bruno Luong 2021-9-20

There are plenty implementations on file exchange

https://www.mathworks.com/matlabcentral/fileexchange?q=shortest+path

请先登录，再进行评论。

Answer 2

Stijn Haenen 2020-9-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/600589-how-to-find-all-possible-paths-from-point-a-to-b-in-any-direction-in-a-matrix#answer_502159

在 MATLAB Online 中打开

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)

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

14 个评论
显示 12更早的评论隐藏 12更早的评论

采纳的回答

4 个评论
显示 2更早的评论隐藏 2更早的评论

更多回答（1 个）

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

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

14 个评论 显示 12更早的评论隐藏 12更早的评论

采纳的回答

4 个评论 显示 2更早的评论隐藏 2更早的评论

更多回答（1 个）

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

14 个评论
显示 12更早的评论隐藏 12更早的评论

4 个评论
显示 2更早的评论隐藏 2更早的评论

0 个评论
显示 -2更早的评论隐藏 -2更早的评论