Изменения

'''{{Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой. Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования. * '''Постановка задачи'''Дан |definition = Задан [[Основные определения теории графов|ациклический граф ]] <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.}}</noinclude><includeonly>{{#if: {{{neat|}}}|<div style="background-color: #fcfcfc; float:left;"><div style="background-color: #ddd;">'''Задача:'''</div><div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div></div>|<table border="0" width="100%"><tr><td style="background-color: #ddd">'''Задача:'''</td></tr><tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr></table>}}</includeonly>

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

<code> count'''countPaths'''(g, v, t): '''if ''' v == t: ans += '''return''' 1 '''else:''' s = 0 '''for(child : ''' to '''in''' g[v):] counts += '''countPaths'''(childg, to, t) '''return''' s

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> — число путей в графе из <tex>s</tex> в <tex>t</tex>. Например, на следующем графе данный алгоритм будет иметь время работы <tex>O(2^{n/2})</tex>. Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до <tex>O(n)</codetex>.

Время [[Файл:Dp-countpaths-example.png‎|600px| Пример графа, на котором алгоритм имеет время работы данного алгоритма <tex>O(Ans2^{n/2})</tex>, где <tex>Ans</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>P(v)</tex> вызывается от каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ begin(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex> Асимптотика алгоритма <tex>O(V + E)</tex>, где <tex>V</tex> - количество вершин графа, <tex>E</tex> - количество вершин. Значения функции <tex>P(v)</tex> вычисляются один раз для кажой вершины, и каждый раз просматриваются ребра <tex>P(v)</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>\mathrm{count(v)}</tex> будет возвращать ответ для вершины <tex>v</tex>. Удобнее всего это реализовать в виде рекурсивной функции с помощью ленивой рекурсии, тогда запоминанием. В этом случае значения массива <tex>d</tex> будут вычисляться по мере необходимости, а засчет запоминания результатов они и не будут считаться лишний раз:

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

<code> '''count'''(g, v): '''if ''' w[v]:

'''else:'''

w[v] = ''true'' '''for(parent : ''' c '''in''' g[v):] sum += '''count'''(parentg, c)

w[v] = true '''return ''' sum

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

w[s] = ''true'' answer = '''count'''(t) '''return''' answer Значение функции <tex>\mathrm{count(v)}</tex> считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ end(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма в худшем случае оценивается как <tex>O(V+E)</tex>, где <tex>V</tex> — число вершин графа, <tex>E</tex> — число ребер. == Пример работы == Рассмотрим пример работы алгоритма на следующем графе: [[Файл: count-path-graph-example.png|thumb|300px ]] Изначально массивы <tex>d</tex> и <tex>w</tex> инициализированы следующим образом:{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''вершина''' || S || 1 || 2 || 3 || 4 || T|-| '''w''' || true || false || false || false || false || false|-| '''d''' || 1 || 0 || 0 || 0 || 0 || 0|}Сначала функция <tex>\mathrm{count}</tex> будет вызвана от вершины <tex>T</tex>. Ответ для нее еще не посчитан (<tex>w[T] = false</tex>), следовательно <tex>\mathrm{count}</tex> будет вызвана от вершин <tex>3</tex> и <tex>4</tex>. Для вершины <tex>3</tex> ответ также не посчитан (<tex>w[3] = false</tex>), следовательно <tex>\mathrm{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;"|-| '''вершина''' || S || 1 || 2 || 3 || 4 || T|-| '''w''' || true || false || '''true''' || false || false || false|-| '''d''' || 1 || 0 || '''1''' || 0 || 0 || 0|} Теперь мы знаем значения для вершин <tex>2</tex> и <tex>S</codetex>, что позволяет вычислить <tex>d[3] = d[2] + d[S] = 2</tex>. Также обновим значения в массиве <tex>w</tex>: <tex>w[3] = true</tex>. {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''вершина''' || S || 1 || 2 || 3 || 4 || T|-| '''w''' || true || false || true || '''true''' || false || false|-| '''d''' || 1 || 0 || 1 || '''2''' || 0 || 0|} В самом начале для вычисления <tex>d[T]</tex> нам требовались значения <tex>d[3]</tex> и <tex>d[4]</tex>. Теперь нам известно значение <tex>d[3]</tex>, поэтому проследим за тем, как будет вычисляться <tex>d[4]</tex>. <tex>\mathrm{d[4] = count(3) + count(2) + count(1)}</tex>, но <tex>w[3] = true, w[2] = true</tex>, следовательно значения <tex>d[3]</tex> и <tex>d[2]</tex> мы уже знаем, и нам необходимо вызвать <tex>\mathrm{count(1)}</tex>. Ответ для этой вершины равен <tex>d[S]</tex>, так как это единственная вершина, ребро из которой входит в <tex>1</tex>. Обновим соответствующие значения массивов <tex>d</tex> и <tex>w</tex>: {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''вершина''' || S || 1 || 2 || 3 || 4 || T|-| '''w''' || true || '''true''' || true || true || false || false|-| '''d''' || 1 || '''1''' || 1 || 2 || 0 || 0|} Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины <tex>4</tex>. <tex>d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4</tex>: {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''вершина''' || S || 1 || 2 || 3 || 4 || T|-| '''w''' || true || true || true || true || '''true''' || false|-| '''d''' || 1 || 1 || 1 || 2 || '''4''' || 0|} Наконец, вычислим <tex>d[T] = d[3] + d[4] = 2 + 4 = 6</tex> и обновим таблицы <tex>d</tex> и <tex>w</tex>: {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"|-| '''вершина''' || S || 1 || 2 || 3 || 4 || T|-| '''w''' || true || true || true || true || true || '''true'''|-| '''d''' || 1 || 1 || 1 || 2 || 4 || '''6'''|} Этот алгоритм позволяет вычислить количество путей от какой-либо вершины <tex>S</tex> не только до <tex>T</tex>, но и для любой вершины, лежащей на любом из путей от <tex>S</tex> до <tex>T</tex>. Для этого достаточно взять значение в соответствующей ячейке <tex>d</tex>. == См. также ==* [[Динамическое программирование]]* [[Кратчайший путь в ациклическом графе]]* [[Задача о расстановке знаков в выражении]]* [[Задача о порядке перемножения матриц]]