У меня есть взвешенный граф 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->и]
Я вычисляю вероятность любого отдельного пути (путем умножения ребер), но не знаю, как объединить вероятность разных путей с общими узлами. Я думаю, что могу сделать это путем объединения и пересечения путей, но я ищу простой программируемый алгоритм.
Чтобы рассчитать вероятность всех событий на пути, умножьте вероятности отдельных событий.
например Два перехода с равными шансами произойдут 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
Я добавил арифметику для вашего примера.
спасибо, это здорово! теперь у вас есть идеи, как это закодировать, и в чем сложность? я пытался к этому, но я не уверен, как. кстати, реальный граф я намного больше на комплексе.
Код должен быть простым — BFS с вычислением вероятностей в каждом узле по мере продвижения, как я показал при расчете вашего примера.
bfs кажется правильным, но что, если я добавлю ребро между c и d? p(c) и p(d) будут меняться от первой итерации ко второй.
Если вы что-то меняете, вам приходится пересчитывать все «ниже по течению» от изменения.
Добавлен псевдокод и реализация C++.
Конечно, я могу это сделать, но в моем примере у меня есть несколько одинаковых узлов на разных путях. Расчеты этого мне не ясны. (просто попробуйте простой пример в моем вопросе)