Is there anyone who can help this question?
How to find all possible routes with a given node matrix?
조회 수: 8 (최근 30일)
이전 댓글 표시
Hello,
I am trying to write a function to find all possible routes from the Start node, 6, to the Goal node, 21, with the given node matrix, A, as shown in the below.
A =
1 6
1 23
2 3
2 4
2 5
3 2
4 2
4 7
5 2
5 11
6 1
6 26
7 4
7 8
8 7
8 9
8 24
9 8
9 23
10 11
10 13
10 15
10 16
11 5
11 10
12 13
12 14
13 10
13 12
13 24
14 12
14 19
15 10
15 17
16 10
16 17
16 18
17 15
17 16
17 25
18 16
18 19
18 22
19 14
19 18
19 20
20 19
21 22
21 27
22 18
22 21
22 25
23 1
23 9
24 8
24 13
25 17
25 22
26 6
27 21
I would like to build a function which results the following outputs.
[6,1,23,9,8,7,4,2,5,11,10,15,17,25,22,21]
[6,1,23,9,8,7,4,2,5,11,10,15,17,16,18,22,21]
[6,1,23,9,8,7,4,2,5,11,10,16,17,25,22,21]
[6,1,23,9,8,7,4,2,5,11,10,16,18,22,21]
[6,1,23,9,8,24,13,10,15,17,25,22,21]
[6,1,23,9,8,24,13,10,16,17,25,22,21]
[6,1,23,9,8,24,13,10,16,18,22,21]
[6,1,23,9,8,24,13,12,14,19,18,16,10,15,17,25,22,21]
[6,1,23,9,8,24,13,12,14,19,18,16,17,25,22,21]
[6,1,23,9,8,24,13,12,14,19,18,22,21]
Thank you very much for your invaluable time to help on this problem.
Best regards,
Sunghun Jung
댓글 수: 3
Walter Roberson
2018년 10월 15일
You effectively have an undirected graph. There are an infinite number of routes unless you add constraints.
채택된 답변
Bruno Luong
2018년 10월 15일
편집: Bruno Luong
2018년 10월 15일
I found actually 13 paths, more than the 10 you have listed:
[6 1 23 9 8 7 4 2 5 11 10 13 12 14 19 18 16 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 13 12 14 19 18 22 21]
[6 1 23 9 8 7 4 2 5 11 10 15 17 16 18 22 21]
[6 1 23 9 8 7 4 2 5 11 10 15 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 16 17 25 22 21]
[6 1 23 9 8 7 4 2 5 11 10 16 18 22 21]
[6 1 23 9 8 24 13 10 15 17 16 18 22 21]
[6 1 23 9 8 24 13 10 15 17 25 22 21]
[6 1 23 9 8 24 13 10 16 17 25 22 21]
[6 1 23 9 8 24 13 10 16 18 22 21]
[6 1 23 9 8 24 13 12 14 19 18 16 10 15 17 25 22 21]
[6 1 23 9 8 24 13 12 14 19 18 16 17 25 22 21]
[6 1 23 9 8 24 13 12 14 19 18 22 21]
Test code:
A =[ 1 6
1 23
2 3
2 4
2 5
3 2
4 2
4 7
5 2
5 11
6 1
6 26
7 4
7 8
8 7
8 9
8 24
9 8
9 23
10 11
10 13
10 15
10 16
11 5
11 10
12 13
12 14
13 10
13 12
13 24
14 12
14 19
15 10
15 17
16 10
16 17
16 18
17 15
17 16
17 25
18 16
18 19
18 22
19 14
19 18
19 20
20 19
21 22
21 27
22 18
22 21
22 25
23 1
23 9
24 8
24 13
25 17
25 22
26 6
27 21];
p = gallpaths(A,6,21);
for k=1:length(p)
fprintf('%s\n', mat2str(p{k}));
end
Using this function GALLPATHS I made
function p = gallpaths(A,start,last)
% find all direct paths from start to last
% A is (n x 2) each row is an edges
A = sortrows(A);
b = true(size(A,1),1);
p = gapengine(A,b,start,last);
end
function p = gapengine(A,b,start,last)
% recursive engine
if start==last
p = {last};
else
bs = A(:,1) == start;
next = A(bs & b,2);
p = {};
b(bs) = false;
for k=1:length(next)
i = next(k);
pk = gapengine(A,b,i,last);
pk = cellfun(@(p) [start, p], pk, 'unif', 0);
p = [p, pk];
end
end
end
댓글 수: 3
Bruno Luong
2018년 10월 15일
Nope find all paths has exponential complexity. AFAIK this is intrinsic to the problem you want to solve rather than the algorithm.
추가 답변 (1개)
Walter Roberson
2018년 10월 15일
댓글 수: 2
Walter Roberson
2018년 10월 19일
See also https://www.geeksforgeeks.org/find-paths-given-source-destination/ which gives code in C, Java, and Python.
참고 항목
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!