Алгоритм нахождения различных путей от A до B в взвешенном, направленном циклическом графе - PullRequest
Новая
       61

Алгоритм нахождения различных путей от A до B в взвешенном, направленном циклическом графе

9 голосов
/ 17 января 2012

Предположим, что у нас есть DIRECTED , WEIGHTED и CYCLIC .

Предположим, что нас интересуют только пути с общий вес меньше чем MAX_WEIGHT

Какой наиболее подходящий (или любой) алгоритм для нахождения числа различных путей между двумя узлами A и B, которые имеют общий весменьше, чем MAX_WEIGHT?

PS: Это не моя домашняя работа.Просто личный, некоммерческий проект.

Ответы [ 3 ]

2 голосов
/ 17 января 2012

Если количество узлов и MAX_WEIGHT не слишком велико (а все веса целые), вы можете использовать динамическое программирование 

unsigned long long int num_of_paths[MAX_WEIGHT+1][num_nodes];

инициализировать до 0, кроме num_of_paths[0][start] = 1;. 

for(w = 0; w < MAX_WEIGHT; ++w){
    for(n = 0; n < num_nodes; ++n){
        if (num_of_paths[w][n] > 0){
            /* for each child c of node n
             * if w + weight(n->c) <= MAX_WEIGHT
             * num_of_paths[w+weight(n->c)][c] += num_of_paths[w][n];
             */
        }
    }
}

решение - сумма num_of_paths[w][target], 0 <= w <= MAX_WEIGHT.

1 голос
/ 17 января 2012

Простая рекурсия. У вас есть это в экспоненциальном времени. Очевидно, что циклы с нулевым весом не допускаются.

функция noe (узел N, предельный вес W)

  1. нет. пути равен нулю, если все исходящие ребра имеют вес> W

  2. в противном случае нет. пути - это сумма чисел пути, полученная суммой (noe (C1, W-W1), noe (C2, W-W2), ... noe (Cn, W-Wn)), где C1 ... Cn - это узлы, соединенные с N, для которых W-Wi не является отрицательным, где Wi - вес соединительной кромки, написанный на вашем любимом языке.

Должно существовать более эффективное решение, аналогичное алгоритму Дейкстры, но я думаю, что этого достаточно для домашней работы.

0 голосов
/ 17 января 2012

Ваша проблема является более общим случаем K-непересекающегося пути В ориентированных плоских графах , с нефиксированным K.

K Проблема непересекающихся путей для ориентированных плоских графов такова:

дано : ориентированный планарный граф G = (V; E) и k пар (r 1 ; s 1 ); ....; (r k ; s k ) вершин группы G;

find : k попарно непересекающихся направленных путей P 1 ; ...; P k в G, где P i работает от r i до s i (i = 1; ....; k ).

В k-непересекающемся пути вы можете нарисовать дугу от всех s i до B, а также дугу от A до всех r i , тем самым вы создадите граф G 'из G .

Теперь, если вы можете решить свою проблему в G 'в P , вы можете решить k-непересекающийся путь в G, поэтому P = NP.

Но если вы прочитаете связанную статью, это даст некоторое представление об общем графе (решение k-непересекающегося пути с фиксированным k), и вы сможете использовать его для получения хорошего приближения.

Также существует более сложный алгоритм, который решает эту проблему в P (для фиксированных k) в общих графах. но в целом это не просто (это Сеймур).

Таким образом, ваш лучший выбор в настоящее время - использовать алгоритмы перебора.

Редактировать: Поскольку MAXWEIGHT не зависит от вашего входного размера (размера вашего графика), это не влияет на эту проблему. Кроме того, это NP-Hard для неориентированного невзвешенного графика, тем не менее вы можете просто сделать вывод, что NP-Hard.

...