How to find all possible routes with a given node matrix?

조회 수: 8 (최근 30일)
Jung Sunghun
Jung Sunghun 2018년 4월 25일
댓글: Jung Sunghun 2018년 10월 20일
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
Walter Roberson 2018년 10월 15일
You effectively have an undirected graph. There are an infinite number of routes unless you add constraints.
Jung Sunghun
Jung Sunghun 2018년 10월 15일
Dear Sir,
The constraint is that the node could only be used once in the path.

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

채택된 답변

Bruno Luong
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
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.
Jung Sunghun
Jung Sunghun 2018년 10월 15일
I got it. Thank you very much for your invaluable time. Have a great day!

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

추가 답변 (1개)

Walter Roberson
Walter Roberson 2018년 10월 15일
  댓글 수: 2
Jung Sunghun
Jung Sunghun 2018년 10월 20일
Thank you very much for the kind supporting.

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

카테고리

Help CenterFile Exchange에서 Variables에 대해 자세히 알아보기

Community Treasure Hunt

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

Start Hunting!

Translated by