Изменения
Нет описания правки
'''Задача о числе путей в ациклическом графе''' - — одна из классических задач на тему динамического программирования. В этой задаче нам дан ациклический граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
== Решение задачи ==
'''return''' s
Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество — число путей в графе из <tex>s</tex> в <tex>t</tex>. Например, на следующем графе данный алгоритм будет иметь время работы <tex>O(2^{n/2})</tex>. Если же использовать метод динамичекого программиованиядинамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до <tex>O(n)</tex>.
[[Файл:Dp-countpaths-example.png|600px| Пример графа, на котором алгоритм имеет время работы <tex>O(2^{n/2})</tex>]]
=== Метод динамического программирования ===
Пусть <tex>P(v)</tex> - количество — число путей от вершины <tex> s </tex> до вершины <tex> v </tex>.
Тогда <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, что есть ребро из <tex>c</tex> в <tex>v</tex>. Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что <tex>P(s) = 1</tex>. Это позволяет решить задачу методом динамического программирования.
=== Псевдокод ===
Пусть <tex>s</tex> - — стартовая вершина, а <tex>t</tex> - — конечная, для нее и посчитаем ответ. Будем поддерживать массив <tex>d</tex>, где <tex>d[v]</tex> - количество — число путей из вершины <tex> s </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> будут вычисляться по мере необходимости и не будут считаться лишний раз:
<tex> count(v) = \left \{
'''return''' answer
Значение функции <tex>count(v)</tex> считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ end(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма в худшем случае оценивается как <tex>O(V+E)</tex>, где <tex>V</tex> - количество — число вершин графа, <tex>E</tex> - количество — число ребер.
== Пример работы ==
| '''d''' || 1 || 0 || 0 || 0 || 0 || 0
|}
Сначала функция <tex>count</tex> будет вызвана от вершины <tex>T</tex>. Ответ для нее еще не посчитан (<tex>w[T] = false</tex>), следовательно <tex>count</tex> будет вызвана от вершин <tex>3</tex> и <tex>4</tex>. Для вершины <tex>3</tex> ответ также не посчитан (<tex>w[3] = false</tex>), следовательно <tex>count</tex> будет вызвана уже для вершин <tex>2</tex> и <tex>S</tex>. А вот для них ответ мы уже можем узнать: для <tex>2</tex> он равен <tex>d[S]</tex>, так как это <tex>S</tex> - единствнная — единственная вершина, ребро из которой входит в нее. Непосредственно для <tex>S</tex> ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
