Изменения

{{Задача|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>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>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину для всех возможных путей за O(''Ans'') ===вершин, в которые есть ребро из <tex>v</tex>, причем он производится независимо от того, были эти вершины посещены ранее, или нет.

Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины Функция <tex>\mathrm{countPaths(g, s, t)}</tex>. При каждом посещении вершины принимает граф <tex>vg</tex> проверимв виде списка смежности, не является ли она искомой вершиной начальную вершину <tex>ts</tex>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от всех детей конечную вершину <tex>vt</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</codetex> ответ также не посчитан (<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</tex>, что позволяет вычислить <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>. == См. также ==* [[Динамическое программирование]]* [[Кратчайший путь в ациклическом графе]]* [[Задача о расстановке знаков в выражении]]* [[Задача о порядке перемножения матриц]] ==Источники информации==* Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9.. [[Категория:Дискретная математика и алгоритмы]][[Категория:Динамическое программирование]]