Как найти наиболее вероятные пути прохождения ориентированного графа?
Добрый день.
Есть такая задача:
Задан направленный граф, одна из вершин которого является "входом" (нет входящих ребер), другая - "выходом" (нет исходящих ребер). В графе могут присутствовать циклы. Из входа можно дойти до любой другой вершины, а из любой вершины - до выхода.
Есть набор вариантов "прохождения" этого графа - последовательности вершин, через которые можно пройти от входа к выходу.
Есть предположение, что существует некоторый небольшой базовый набор таких прохождений, а все варианты являются модификацией того или иного базового случая (т.е. сначала шли по нему, потом ушли немного куда-то в сторону, потом снова вернулись на этот путь).
Как можно выделить этот базовый набор?
При этом надо учитывать, что вероятность перехода из произвольной вершины в другие зависит от контекста, от истории предыдущих переходов. Т.е. может быть два пути, например, А -> Б -> В и Г -> Б -> Д, и куда мы пойдем из Б зависит от того, откуда мы в неё пришли.
Замкнуть выход на вход. Каждой вершине придумать вероятности (да хоть 1/n).
Получаем цепь Маркова, остаётся найти её эргодическое распределение.
Надо только придумать разглючку на случай, если ЦМ будет периодической — но, возможно, стандартные методы регуляризации СЛАУ с этим справятся.
- сопоставить каждой вершине идентификатор
- представить путь как последовательность вершин
- для каждой пары путей - найти общие последовательности вершин
- для каждого пути - найти длину последовательностей, которые оказались общими с другими (хотя - скорее её отношение к длине пути).
Похоже, что она будет максимальна у удовлетворяющего нашим требованиям пути.
Но это таки какое-то костыльное решение.
Во первых, я не уверен в его верности (строгого доказательства нет).
Во вторых - требуется создать (или создавать на ходу) набор всех возможных путей из входа в выход.
Вишенка на торте - сложность предпоследнего этапа в N^2 * сложностьПоискаОбщихПоследовательностей :-)
Средний
Простой