Изменения

'''Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан ациклический граф, не содержащий циклов, в котором необходимо <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество различных путей от одной из вершины до другой<tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.

Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования. * '''Постановка задачи'''Дан ациклический граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>с помощью динамики.

Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <tex>s</tex>. При каждом посещении вершины <tex>v</tex> проверим, не является ли она искомой вершиной <tex>t</tex>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от всех детей вершин, ребра в которые выходят из <tex>v</tex>, причем он производится независимо от того, были ли эти вершины посещены ранее, или нет. Функция <tex>countPaths(s, t)</tex> принимает начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. В глобальной переменной <tex>answer</tex> содержится ответ.

answer = 0 '''count'''(v): '''if ''' v == t: ans answer += 1 '''else:''' '''for'''(child : всех <tex>to</tex> смежных с <tex>v</tex>): '''count'''(to) '''countPaths'''(s, t) answer = 0 count(childs) return answer

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

Можно заметить, что <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, где что <tex>\exists</tex> ребро из <tex>c</tex> - предок в <tex>v</tex>. Мы свели нашу задачу к более мелким подзадачам, причем мы также знаем, что <tex>P(s) = 1</tex>. Это позволяет решить задачу методом динамического программирования.  Асимптотика алгоритма <tex>O(V + E)</tex>, где <tex>V</tex> - количество вершин графа, <tex>E</tex> - количество вершин. Функция <tex>P(v)</tex> вызывается от каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ begin(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>

Пусть <tex>s</tex> - стартовая вершина, а <tex>t</tex> - конечная, для нее и посчитаем ответ. Будем поддерживать массив <tex>d</tex>, где <tex>d[v]</tex> - количество путей до вершины <tex>v</tex> и массив <tex>w</tex>, где <tex>w[v] = true</tex>, если ответ для вершины <tex>v</tex> уже посчитан, и <tex>w[v] = false</tex> в противном случае. Изначально <tex>w[i] = false</tex> для всех вершин<tex>i</tex>, кроме <tex>s</tex>, а <tex>d[s] = 1</tex>. Функция <tex>count(v)</tex> будет возвращать ответ для вершины <tex>v</tex>. Удобнее всего это реализовать с помощью ленивой рекурсии, тогда значения массива <tex>d</tex> будут вычисляться по мере необходимости, а засчет запоминания результатов они не будут считаться лишний раз:

\sum\limits_{parentc}count(parentc), & w[v]=false

'''count'''(v): '''if ''' w[v]: '''return ''' d[v] '''else:'''

'''for'''(parent : всех <tex>c</tex> смежных с <tex>v</tex>): sum += '''count'''(parentc)

'''return ''' sum

'''countPaths'''(s, t):

answer = '''count'''(t) '''return''' answer