как решить граф с циклами

Question

Я пытаюсь найти решение следующей проблемы с помощью Java.У меня есть график, это хороший пример того, как он может выглядеть:

Есть его обозначение:

[{ A = {C = 0,7}, {D = 0,3}}, { C = {out = 0,2}, {F = 0,8}}, { D = {C = 0,1}, {F = 0,2}, {G = 0,3}, {E = 0,4}}, { S = {A = 0,4}, {B = 0,6}},
{E = {G = 0,3}, {out = 0,7}}, { G = {B = 0,2} {out = 0,8}}, ...

S - это начальный узел (S = 1), out - это выход из графика.

Я хочу отследить график и узнать, какой процент каждыйузел имеет.Например, A = 0,4 * S (S = 1), C = 0,7A + 0,1D, D = 0,3A + 0,7B

Я думал, что это можно сделать с помощью рекурсии (DFS для ориентированных графов, в частности, алгоритма Тарьяна), но хотя есть циклы, я не думаю, что это помогает.Другим решением является решение системы линейных уравнений.Я не знаю, что лучше, чтобы это работало, и, возможно, существуют решения для такого рода задач.Этот пример является просто примером, но я должен учитывать, что у меня есть, как ок.2000 узлов (а кто знает сколько циклов).

Как бы вы это сделали?

Answer 1

Решение линейных уравнений представляется очень хорошим подходом.

Вы можете попробовать использовать Устранение по Гауссу .Я уверен, что вы можете просто найти уже написанный Java-код, чтобы сделать это для вас, в Интернете.

Answer 2

Примечание: для циклических графов решение одной системы линейных уравнений не дает вероятности . Это дает вам ожидаемую кратность.

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

1. Вычислить сильно связанные компоненты (SCC) графика.
2. Для каждого SCC C , для каждого возможного начального узла v в C , вычислить с помощью решения систем линейных уравнений (а) распределение дуг, оставляющих C и (b) вероятность посещения каждого узла в C . Лучший из известных мне способов достижения (б) - это рассмотреть граф продуктов, чьи узлы являются парами. Первым элементом пары является узел в C . Второй элемент - это подмножество узлов в C , которые были посещены. Дуги унаследованы от C . Решите некоторые линейные уравнения, чтобы узнать распределение последних узлов в этом новом графике.
3. Подготовьте новый график H на вершинах G с дугами от v до w при v и w находятся в разных компонентах G и есть путь от v до w . Вероятность этой дуги определена на шаге 2 (а).
4. Решить ациклическую проблему на H .
5. Для каждого узла вычислите взвешенную сумму вероятностей из шага 2 (b).

Этот алгоритм в основном линейный по размеру графика, но экспоненциальный по размеру SCC. Я не уверен, как выглядят ваши циклы.