Привет, все.
На днях я придумал одну [очень] интересную задачу.
Собственно задача:
У нас есть ориентированный граф n вершин и m ребер. Вы находитесь в вершине 1. Также известно, что, будучи в вершине v вы пойдете в вершину u с определенной вероятностью. Также с некоторой вероятностью вы останетесь в этой вершине и не пойдете больше никуда. Очевидно, что сумма вероятностей прохождения по какому-то ребру и того, что вы останетесь на месте, — равна 1. Нужно посчитать вероятность с которой вы попадете в вершину to, начав свой путь с вершины 1.
Мое решение, а точнее сказать размышления о решении под катом.
UPD решение было найдено. Пару слов в конце.
Мои раздумия (сразу предупреждаю: буду описывать ход своих мыслей — поэтому может быть немного лишнего):
1. возьмем такой пример: у нас есть путь v₁ = 1, v₂,..., v_k = to. Имея хоть немного знаний в теории вероятностей, можно увидеть, что вероятность прохождения именно по этому пути равна произведению вероятностей каждого ребра. Это вроде и очевидно, но вдруг кто не знает?..
2. сразу хочется запустить какой-то поиск по графу, и именно эта идея пока играет ключевую роль.
2.1. поиск в ширину не подходит, по причине того, что в вершину u может приходить несколько путей разной длины, но мы в нее зайдем только раз, и вероятность которую мы получим через второй путь мы недосчитаем во всех вершинах, которые доступны из u. Поэтому мы его сразу бракуем.
2.2. значит у нас остается поиск в глубину. Правда с ним тоже не все гладко: за сколько будет работать такой алгоритм, я пока понять не смог...
3. с горем пополам таки пишем эту идею. Профит. Но радость длится недолго.
4. вспоминаем, что в графах бывают циклы, плачем,:
с первого взгляда кажется, что из-за циклов, ответ для вершин, по пути к которым есть циклы, будет бесконечно большим, но это не так: цикл, как известно, является замкнутым путем, и вероятность прохождения по нему также можно посчитать.
5. замечаем, что в случае с вероятностями, все числа в пределах [0,1], а значит с каждым прохождением по циклу к вероятности прихода в вершину добавляются члены геометричесской прогрессии. Ее знаменателем будет вероятность прохождения по циклу, а первым членом посчитанная ранее вероятность прихода в эту вершину. Как известно, по этих данных можно найти предел этой суммы, и это очень просто. Но радоваться все еще очень рано... Даже в таком случае не очень-то ясно как именно считать теперь это все. В случае с одним циклом все выворачивается само собой, но когда циклов побольше — то даже интуитивно не понятно как считать эту гребаную веротность...
Так вот, я хотел бы попросить у вас помощи, или хотя бы хоть какого-то объективного доказательства, что решить эту задачу нереально.
P.S. если кто-то подскажет программу, в которой можно не прикладая много усилий рисовать графы — то я добавлю сюда немного картинок.
UPD. к счастью, или к сожалению, сойти с ума не вышло. Решение помогли найти, и оно оказалось намного проще, чем я думал. Метод решения описан тут. Код решения от pavel.savchenkov. От себя добавлю очень похожа на задачу о нахождении количества путей заданой длины. Даже могу сказать, что задачи мало отличаются друг от друга.