Finding the shortest path in a cell array based on given input

Question

Shawn Castelino 2019-11-22

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/492647-finding-the-shortest-path-in-a-cell-array-based-on-given-input

编辑： Stephen23 2019-11-23

If I have a call array of n - 1x2 vectors, how do I find the shortest path using a combination of these n vectors based on a given input

example using 6 vectors:

existing cell array - { [0 1], [1 2], [2 3], [3 4], [0 3], [1 4] }

input - [0 4]

expected output - {[0 1], [1 4]} or {[0 3],[3 4]}

edit: fixed input

2 个评论
显示无隐藏无

Adam Danz 2019-11-22

What do you mean "shortest path"?

Are the pairs of valure (x,y) coordinates such that you have 6 dots and you're trying to find which dot is closest to the input coordinate?

I don't understand how the outputs map onto the input.

Shawn Castelino 2019-11-22

Sorry, I should have done a better job explaining and I corrected a mistake in the question

The existing cell array is a sort of index, they are not coordinates. They are the indeces for transformation matrices (in robotics). The lower number is the start of the frame and the upper number is the end of the frame.

In the example, the existing cell array is all available frames I have. If I input a frame that doesn't exist, I can calculate it using the combination (product) of the other frames. the upper number of the previous frame should be the lower number of the next frame.

so i the case of the example, if the input is [0 4], i can achieve it by multiplying frames [0 1] x [1 4] or [0 3] x [3 4]

请先登录，再进行评论。

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

Answer 1

Stephen23 2019-11-22

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/492647-finding-the-shortest-path-in-a-cell-array-based-on-given-input#answer_402876

编辑：Stephen23 2019-11-23

在 MATLAB Online 中打开

Each row of the output cell array is one path:

>> C = {[0,1],[1,2],[2,3],[3,4],[0,3],[1,4]};
>> V = [0,4];
>> Z = mainfun(C,V)
>> Z{1,:} % 1st path
ans =
     0     1
ans =
     1     4
>> Z{2,:} % 2nd path
ans =
     0     3
ans =
     3     4

Where mainfun is defined as:

function Z = mainfun(C,V)
%C = {[0,1],[1,2],[2,3],[3,4],[0,3],[1,4]};
%V = [0,4];
N = 1+numel(C);
Z = {};
M = vertcat(C{:});
X = V(1)==M(:,1);
for ii = reshape(find(X),1,[])
    nestfun(M(~X,:),C(ii))
end
%
    function nestfun(W,A)
        if numel(A)>N
            return
        elseif V(2)==A{end}(2)
            if numel(A)<N
                N = numel(A);
                Z = A;
            else
                Z(end+1,:) = A;
            end
        else
            Y = W(:,1)==A{end}(2);
            for jj = reshape(find(Y),1,[])
                nestfun(W(~Y,:),[A,{W(jj,:)}])
            end
        end
    end
end