Начните с решения более простой проблемы: учитывая две точки A и B в DAG, можете ли вы подсчитать все пути, начинающиеся с A и заканчивающиеся на B? («Путь» определяется как список ребер, где конечный узел одного из них равен начальному узлу следующего.)
Звучит сложно. Можем ли мы это упростить?
Хорошо, что самый простой случай заключается в том, что A и B фактически являются одним и тем же узлом. В этом случае есть нулевые пути, потому что граф ацикличен.
Предположим, что А и В разные. WOLOG предполагает, что A имеет ровно два соседа C и D, ни один из которых не является B. Количество путей от A до B должно быть равно числу путей от C до B, а также количеству путей от D до B.
В более общем смысле: если A имеет n соседей, ни один из которых не является B, найдите количество путей от каждого соседа до B и суммируйте их.
Если A делает, у вас есть сосед B, то не забудьте добавить его к общей сумме для пути A-> B.
Теперь мы разделили это на множество под-проблем, и каждый из них строго меньше предыдущей проблемы.
Вы подумали бы, что прямое рекурсивное решение будет делать трюк, но, к сожалению, это не так. Рассмотрим этот граф:
A
/\
C D
\/
E
/\
F G
\/
H
/\
I J
\/
B
- Дорожки от А до В равно пути от С до В плюс пути от D до B. Таким образом, рассчитать те.
- Пути от C до B равны дорожкам от E до B.
- Пути от D до B равны дорожкам от E до B.
И ... мы только что вычислили пути от E до B дважды. Это, в свою очередь, рассчитает пути от H до B дважды, в общей сложности четыре раза. Алгоритм, который я набросал, может вычислить одни и те же вещи 2 n раз, где n пропорционально количеству узлов на графике!
Что вам нужно сделать, это сделать memoizer, так что, как только ответ будет рассчитан один раз, он никогда не будет рассчитываться снова.
Итак, решайте более простую задачу, создав рекурсивный, memoized алгоритм , который вычисляет общее количество путей между двумя заданными узлами.
Итак, давайте попробуем. Сколько путей существует от A до B? Обозначим это ab. Мы вычисляем:
ab = cb + db, but we don't know them...
cb = eb, but we don't know it...
eb = fb + gb, but we don't know them...
fb = hb, but we don't know it...
hb = ib + jb, but we don't know them...
ib = 1
jb = 1
therefore hb = 2
therefore fb = 2
gb = hb, but we already know that is 2
therefore eb = 4
therefore cb = 4
db = eb, but we already know that is 4
therefore ab is 8
И все готово.
Как только вы можете найти количество путей между двумя узлами, просто вычислить все пути, которые содержат заданное ребро. Например, пути от A до B, которые проходят через E-G, равны числу путей от A до E, умноженному на количество путей от G до B.
Давайте попробуем.
ae = ce + de
ce = 1
de = 1
so ae = 2
gb = hb
hb = ib + jb
ib = 1
jb = 1
so hb = 2
so gb = 2
и есть ae * gb = 4 пути от A до B, которые проходят через EG. Давайте проверим нашу работу. Пути:
AC-CE-EG-GH-HI-IB
AC-CE-EG-GH-HI-JB
AD-DE-EG-GH-HI-IB
AD-DE-EG-GH-HI-JB
Да, их четыре.
Имеют смысл?
Можете ли вы опубликовать код, который у вас есть сейчас? – univerio
не сразу - это вроде беспорядок, во всяком случае. Я связал парсер для эзотерического набора данных в том же коде. – user2388189
Из того, что я прочитал, я должен включить топологический вид, а затем проанализировать вывод для данной ссылки; Мне интересно, насколько это эффективно вычислить, поскольку я знаю определенную ссылку априори и, более того, возможно, пакет python, который может сделать это для меня вместо того, чтобы кодировать сам алгоритм. – user2388189