Найти все возможные пути между N множеством узлов

Question

У меня есть N количество узлов в начале и в конце, где они могут быть спарены как N количество наборов (1 to 1, .., n to n, .., N to N). Тем не менее, у меня есть M этапов (можно считать параллельными этапами) между началом и концом, и каждый этап имеет R количество узлов, где R>=N.

Если я считаю начать n узел в конце n узла (т.е. n to n пара), я должен пройти (M+1) хмель, чтобы достигнуть конечного узла, и есть R^M возможные пути. Таким образом, все возможные пути для всех пар: N*R^M.

я вес каждой ссылки как: связи между узлом i на этапе m и узел j на этапе m+1 как w_{i,j}^{m,m+1}.

Я хочу написать код MATLAB для генерации всех возможных путей каждой пары, то есть N числа пар. Может кто-нибудь, пожалуйста, помогите мне?

Я попробовал его только с использованием исчерпывающего поиска только для 2 начальных и конечных узлов с 2 этапами, которые имеют 3 узла. Но я не знаю, как эффективно это сделать для общей сети. Пожалуйста, помогите мне !!!

Добавлено: Например: N = M = 2, R = 3 У меня есть R^M=2^3=9 возможных путей для каждой пары. Для обеих пар у меня есть 18. Для 1 to 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 to 2 пары.

На самом деле, мой исчерпывающий поиск. Я генерирую каждый прыжок в качестве матрицы со случайно сгенерированными весами. От начала и до 1-го прыжка: A=rand(2,3), затем первый хмель на 2-й хопе: B=rand(3,3) и 2-го до конца: C=rand(3,2)

Answer 1

Итак, в вашем обновлении вы просто хотите создать декартово произведение

{г} X { 1, 2, ..., R}^МХ {J}

быстрый и грязный подход был бы сделать что-то вроде этого:

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 

Вы могли бы затем цикл через paths и вычислить веса.