找到N组节点之间的所有可能路径 [英] Find all possible paths between N set of nodes

问题描述

我有 N 在开始和结尾可以配对的节点数量为 N 集数 1到1，..，n到n，..，N到N ）。然而，我在开始和结束之间有 M 阶段（可以假定为并行阶段），每个阶段都有 R 其中 R> = N 的节点数目。

如果我考虑开始 n 节点以结束 n 节点（即 n到n 对），我必须通过（M + 1）跳来到达最终节点，并有 R ^ M 可能的路径。因此，所有对的所有可能路径都是 N * R ^ M 。

我将每个链接加权为：节点 i 在阶段 m 和节点 j 在阶段 m + 1 as w_ {i， Ĵ} ^ {M，M + 1} 。

我想编写一个MATLAB代码来生成每对可能的路径，即N对对。有人可以帮我吗？

我试过它只使用穷举搜索只有2个开始和结束节点与2个阶段有3个节点。但我不知道如何以有效的方式为通用网络编写此文件。请帮助我!!!

补充：例如： N = M = 2，R = 3 我有 R ^ M = 2 ^ 3 = 9 每对可能的路径。对于这两对，我有 18 。对于 1至1 对，可能的路径设置为：

  {1 -1-1-1,1-1-2-1,1-1-3-1 
 1-2-1-1,1-2-2-1,1-2-3-1 
 1-3-1-1,1-3-2-1,1-3-3-1} 
  

和相应的权值设置为（ 0 表示开始）：

  {W_ {1,1} ^ {0,1} {-w_ 1,1} ^ {1,2} {-w_ 1,1} ^ {2,3}; W_ {1,1} ^ {0,1} -w_ {1,2} ^ {1,2} {-w_ 2,1} ^ {2,3}; w_ {1,1} ^ {0,1} -w_ {1,3} ^ {1,2} -w_ {3,1} ^ {2,3}，.........，w_ {1,3} ^ {0,1} -w_ {3,3} ^ {1,2} -w_ {3,1} ^ {2,3}} 
  

对于 2到2 对来说也是如此。

实际上，我将每跳都作为随机生成权重的矩阵生成。从开始到第一跳： A = rand（2,3），然后第一跳跳到第二跳： B = rand（3,3），第二个结束： C = rand（3,2）

解决方案

好吧，根据您的更新，您只需生成笛卡尔产品

{i} X {1,2，...， R $ ^ b
$ b

一个快速而肮脏的方法就是做这样的事情：

  paths = zeros（R ^ M，M + 2）; ＃初始化数组
 paths（：，1）= i; ＃在节点i处启动所有路径
 paths（：，M + 2）= j; ＃结束节点j处的所有路径b 
 $ b对于c = 1：M 
对于r = 1：（R ^ M）
 paths（r，c + 1）= mod idivide（r-1，R ^（c-1）），R）+1; 
 end 
 end 
  

然后你可以循环路径并计算权重。

I have N number of nodes at start and end where they can be paired as N number of sets (1 to 1, .., n to n, .., N to N). However, I have M stages (can be assumed as parallel stages) in between the start and end, and each stage has R number of nodes where R>=N.

If I consider start n node to end n node (i.e., n to n pair), I have to pass (M+1) hops to reach end node, and there are R^M possible paths. Thus, all possible paths for all pairs are N*R^M.

I weight each link as : the link between node i at stage m and node j at stage m+1 as w_{i,j}^{m,m+1}.

I want to write a MATLAB code to generate all possible paths each pair, i.e., N number of pairs. Can someone please help me?

I tried it only using exhaustive search just for 2 start and end nodes with 2 stages that have 3 nodes. But I don't know how to write this for a general network with effective way. Please help me !!!

Added: For example: N = M = 2, R = 3 I have R^M=2^3=9 possible paths for each pair. For both pairs, I have 18. For 1 to 1 pair, possible paths set is:

{1-1-1-1, 1-1-2-1,1-1-3-1
1-2-1-1, 1-2-2-1,1-2-3-1
1-3-1-1, 1-3-2-1,1-3-3-1} 

and corresponding weights set is (0 represents start) :

{w_{1,1}^{0,1}-w_{1,1}^{1,2}-w_{1,1}^{2,3}; w_{1,1}^{0,1}-w_{1,2}^{1,2}-w_{2,1}^{2,3}; w_{1,1}^{0,1}-w_{1,3}^{1,2}-w_{3,1}^{2,3}, ........., w_{1,3}^{0,1}-w_{3,3}^{1,2}-w_{3,1}^{2,3}}

Same follows for the 2 to 2 pair.

Actually, my exhaustive search I generate each hop as matrix with randomly generated weights. From start to 1st hop: A=rand(2,3), then 1st hop to 2nd hop: B=rand(3,3), and 2nd to end: C=rand(3,2)

解决方案

Okay, so per your update you just want to generate the Cartesian product

{i} X {1, 2, ..., R}^M X {j}

A quick-and-dirty approach would be to do something like this:

paths = zeros(R ^ M, M + 2); # initialize array
paths(:, 1) = i;              # start all paths at node i
paths(:, M+2) = j;            # end all paths at node j

for c = 1:M
  for r = 1:(R ^ M)
    paths(r, c+1) = mod(idivide(r-1, R ^ (c-1)), R)+1 ;
  end
end

You could then loop through paths and calculate the weights.

这篇关于找到N组节点之间的所有可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！