Общая вероятность всех путей между двумя узлами во взвешенном ограниченном графе

У меня есть взвешенный граф G=(V,E)

В этом графе вес ребра (v[i],v[j]) — это вероятность (p) прямого перехода между v[i] и v[j] (0<p<1).

Например: пример графика

Я пытаюсь рассчитать вероятность перехода между двумя узлами v, u.

Что я сделал до сих пор:

Я нашел все пути от v до u (используя all_simple_paths )

[в-0,1->а-0,2->в-0,3->и]

[v-0,1->а-0,2->в-0,2->б-0,4->г-0,5->и]

[в -0,1-> б -0,2-> в -0,3-> и]

[в-0,1->б-0,4->г-0,5->и]

Я вычисляю вероятность любого отдельного пути (путем умножения ребер), но не знаю, как объединить вероятность разных путей с общими узлами. Я думаю, что могу сделать это путем объединения и пересечения путей, но я ищу простой программируемый алгоритм.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
0
98
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Чтобы рассчитать вероятность всех событий на пути, умножьте вероятности отдельных событий.

например Два перехода с равными шансами произойдут 1 раз из 4

Чтобы вычислить вероятность возникновения одного или нескольких из нескольких независимых событий, p(A или B) = p(A) + p(B) – p(A и B).

Ваш пример:

p(D) = 0.5
p(C) = 0.3
p(B) = 0.2 + 0.06 - 0.012 = 0.248
p(A) = 0.3 * 0.2 = 0.06
p(V) = 0.0248 + 0.006 - 0.0001488 = 0.0306512

Алгоритм псевдокода выглядит так

- Mark all nodes 'uncalculated'
- LOOP over nodes
    - IF node has outlinks but no inlinks
        - LOOP over all paths from node to end node
            - LOOP PN over nodes in path
                 - LOOP I over inlinks to PN
                     - IF source node on I  'uncalculated'
                         - BREAK out of PN loop
                     - SET IP(I) = I probability * source node probability
                 - ENDLOOP I 
                 - IF 0 inlinks
                     - SET PN probability = 1
                 - IF 1 inlinks
                     - SET PN probability = IP[0]
                 - IF 2 inlinks
                     - SET PN probability = IP[0] + IP[1] - IP[0] * IP[1]
                 - IF inlinks > 2
                     - ask user to refactor input
                     - STOP
                 - IF PN = end node
                     - OUTPUT end node probability
                     - STOP

Вот код C++ для этого (он слишком сложен для написания кода на Python):

void cPathFinder::probs()
        {
            // The probabilities are stored in the link and node attribute myCost
            // Mark all node probabilities as 'not yet calculated'
            for (auto &n : myG)
                n.second.myCost = -1;

            // loop over nodes
            for (auto &n : myG)
            {
                // check for possible starting node
                // i.e one with out edges and no in edges
                if (!(outDegree(n.second) && (!inDegree(n.second))))
                    continue;

                // iterate over all paths from starting node to target node
                visitAllPaths(
                    node(n.second),
                    myEnd,
                    [&, this](int length) -> int
                    {
                        // loop over nodes in path
                        for (int n : myPath)
                        {
                            if (n < 0)
                                continue;

                            // loop over inlinks
                            std::vector<double> vprob;
                            bool fOK = true;
                            for (const auto l : inlinks(n))
                            {
                                double prevNodeProb = node(l.first.first).myCost;
                                if (prevNodeProb == -1)
                                {
                                    // the previous node probability has not been calculated yet
                                    // no need to look at any more inlinks
                                    fOK = false;
                                    break;
                                }
                                // store the probability contribution from this inlink
                                // it is the product of the source node proabability and the link probability
                                vprob.push_back(
                                    prevNodeProb * l.second->myCost);
                            }
                            // check if there is enough information
                            // to calculate the probability for this node
                            if (!fOK)
                                break;

                            // all the previous nodes are calculated
                            // calculate this node's probability
                            switch (vprob.size())
                            {
                            case 0:
                                //starting node, assume probability of 100%
                                node(n).myCost = 1;
                                break;

                            case 1:
                                // one inlink, prob is previous node prob times link probability
                                node(n).myCost = vprob[0];
                                break;

                            case 2:
                                // two inlinks
                                node(n).myCost =
                                    vprob[0] + vprob[1] - vprob[0] * vprob[1];
                                break;
                                
                            default:
                                /*  More then two inlinks
                                The code does not handle this
                                but note that multiple inlinks can alwayd be reduced to a series of
                                nodes with 2 inlinks
                                */
                                throw std::runtime_error(
                                    userName(n) + " has more than 2 inlinks, please refactor input");
                            }
                        }

                        return 0;
                    });
            }

            std::stringstream ss;
            ss << "\nfinal node " << userName(myEnd) << " probability "
               << node(myEnd).myCost << "\n";
            myResults = ss.str();
        }

Вывод из пробного прогона для вашего примера

input
l u c 0.3
l u d 0.5
l c a 0.2
l c b 0.2
l d b 0.4
l a v 0.1
l b v 0.1
e v

path: u c a v 
path: u c b v
path: u d b v

node probs
c 0.3
u 1
d 0.5
a 0.06
b 0.248
v 0.0306

final node v probability 0.0306

Более полная документация на https://github.com/JamesBremner/PathFinder3/wiki/Probabilities

Полный код этого приложения находится на https://github.com/JamesBremner/PathFinder3

Конечно, я могу это сделать, но в моем примере у меня есть несколько одинаковых узлов на разных путях. Расчеты этого мне не ясны. (просто попробуйте простой пример в моем вопросе)

malachi levy 29.10.2022 19:46

Я добавил арифметику для вашего примера.

ravenspoint 29.10.2022 19:56

спасибо, это здорово! теперь у вас есть идеи, как это закодировать, и в чем сложность? я пытался к этому, но я не уверен, как. кстати, реальный граф я намного больше на комплексе.

malachi levy 29.10.2022 20:32

Код должен быть простым — BFS с вычислением вероятностей в каждом узле по мере продвижения, как я показал при расчете вашего примера.

ravenspoint 29.10.2022 20:41

bfs кажется правильным, но что, если я добавлю ребро между c и d? p(c) и p(d) будут меняться от первой итерации ко второй.

malachi levy 29.10.2022 20:55

Если вы что-то меняете, вам приходится пересчитывать все «ниже по течению» от изменения.

ravenspoint 29.10.2022 20:58

Добавлен псевдокод и реализация C++.

ravenspoint 30.10.2022 19:58

Другие вопросы по теме