Задача о числе путей в ациклическом графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение задачи)
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 8 участников)
Строка 1: Строка 1:
'''Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой.
+
{{Задача
 
+
|definition = Задан [[Основные определения теории графов|ациклический граф]] <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования.
+
}}
 
+
</noinclude>
* '''Постановка задачи'''
+
<includeonly>{{#if: {{{neat|}}}|
Дан ациклический граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
+
<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>
  
 
== Решение задачи ==
 
== Решение задачи ==
Строка 10: Строка 18:
 
=== Перебор всех возможных путей ===
 
=== Перебор всех возможных путей ===
  
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <tex>s</tex>. При каждом посещении вершины <tex>v</tex> проверим, не является ли она искомой вершиной <tex>t</tex>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от всех детей <tex>v</tex>, причем он производится независимо от того, были ли эти вершины посещены ранее, или нет.
+
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <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>
+
  '''countPaths'''(g, v, t)
  count(v):
+
     '''if''' v == t
     if v == t:
+
         '''return''' 1
         ans += 1
+
     '''else'''
     else:
+
        s = 0
         for(child : v):
+
         '''for''' to '''in''' g[v]
             count(child)
+
             s += '''countPaths'''(g, to, t)
 +
        '''return''' s
  
</code>
+
Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> — число путей в графе из <tex>s</tex> в <tex>t</tex>. Например, на следующем графе данный алгоритм будет иметь время работы <tex>O(2^{n/2})</tex>. Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до <tex>O(n)</tex>.
  
Время работы данного алгоритма <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.
+
[[Файл:Dp-countpaths-example.png‎|600px| Пример графа, на котором алгоритм имеет время работы <tex>O(2^{n/2})</tex>]]
  
 
=== Метод динамического программирования ===
 
=== Метод динамического программирования ===
  
Пусть <tex>P(v)</tex> - количество путей до вершины <tex>v</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>v</tex>. Мы свели нашу задачу к более мелким подзадачам, причем мы также знаем, что <tex>P(s) = 1</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>v</tex> и массив <tex>w</tex>, где <tex>w[v] = true</tex>, если ответ для вершины <tex>v</tex> уже посчитан, и <tex>w[v] = false</tex> в противном случае. Изначально <tex>w[i] = false</tex> для всех вершин, кроме <tex>s</tex>, а <tex>d[s] = 1</tex>. Функция <tex>count(v)</tex> будет возвращать ответ для вершины <tex>v</tex>. Удобнее всего это реализовать с помощью ленивой рекурсии, тогда значения массива <tex>d</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> будут вычисляться по мере необходимости и не будут считаться лишний раз:  
  
 
<tex> count(v) = \left \{  
 
<tex> count(v) = \left \{  
 
\begin{array}{ll}
 
\begin{array}{ll}
 
  d[v], & w[v]=true \\
 
  d[v], & w[v]=true \\
  \sum\limits_{parent}count(parent), & w[v]=false  
+
  \sum\limits_{c|cv \in E}count(c), & w[v]=false
 
  \end{array}
 
  \end{array}
 
  \right.
 
  \right.
 
</tex>
 
</tex>
  
<code>
+
  '''count'''(g, v)
  count(v):
+
     '''if''' w[v]
     if w[v]:
 
 
         return d[v]
 
         return d[v]
     else:
+
     '''else'''
 
         sum = 0
 
         sum = 0
         for(parent : v):
+
         w[v] = ''true''
             sum += count(parent)
+
        '''for''' c '''in''' g[v]
 +
             sum += '''count'''(g, c)
 
         d[v] = sum
 
         d[v] = sum
         w[v] = true
+
         '''return''' sum
        return sum
 
 
   
 
   
  countPaths(s, t):
+
'''countPaths'''(g, s, t)
 
     d[s] = 1
 
     d[s] = 1
     w[s] = true
+
     w[s] = ''true''
     answer = count(t)
+
     answer = '''count'''(t)
</code>
+
    '''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</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..
 +
 
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Динамическое программирование]]

Текущая версия на 19:37, 4 сентября 2022

Задача:
Задан ациклический граф [math]G[/math] и две вершины [math]s[/math] и [math]t[/math]. Необходимо посчитать количество путей из вершины [math]s[/math] в вершину [math]t[/math] по рёбрам графа [math]G[/math].



Решение задачи

Перебор всех возможных путей

Небольшая модификация алгоритма обхода в глубину. Запустим обход в глубину от вершины [math]s[/math]. При каждом посещении вершины [math]v[/math] проверим, не является ли она искомой вершиной [math]t[/math]. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину для всех вершин, в которые есть ребро из [math]v[/math], причем он производится независимо от того, были эти вершины посещены ранее, или нет.

Функция [math]\mathrm{countPaths(g, s, t)}[/math] принимает граф [math]g[/math] в виде списка смежности, начальную вершину [math]s[/math] и конечную вершину [math]t[/math].

countPaths(g, v, t)
    if v == t
        return 1
    else
        s = 0
        for to in g[v]
            s += countPaths(g, to, t)
        return s

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

Пример графа, на котором алгоритм имеет время работы [math]O(2^{n/2})[/math]

Метод динамического программирования

Пусть [math]P(v)[/math] — число путей от вершины [math] s [/math] до вершины [math] v [/math]. Тогда [math]P(v)[/math] зависит только от вершин, ребра из которых входят в [math]v[/math]. Тогда [math]P(v) = \sum\limits_{c}P(c)[/math] таких [math]c[/math], что есть ребро из [math]c[/math] в [math]v[/math]. Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что [math]P(s) = 1[/math]. Это позволяет решить задачу методом динамического программирования.

Псевдокод

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

[math] count(v) = \left \{ \begin{array}{ll} d[v], & w[v]=true \\ \sum\limits_{c|cv \in E}count(c), & w[v]=false \end{array} \right. [/math]

count(g, v)
    if w[v]
        return d[v]
    else
        sum = 0
        w[v] = true
        for c in g[v]
            sum += count(g, c)
        d[v] = sum
        return sum

countPaths(g, s, t)
    d[s] = 1
    w[s] = true
    answer = count(t)
    return answer

Значение функции [math]\mathrm{count(v)}[/math] считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра [math]\{e\ |\ end(e) = v\}[/math]. Всего таких ребер для всех вершин в графе [math]O(E)[/math], следовательно, время работы алгоритма в худшем случае оценивается как [math]O(V+E)[/math], где [math]V[/math] — число вершин графа, [math]E[/math] — число ребер.

Пример работы

Рассмотрим пример работы алгоритма на следующем графе:

Count-path-graph-example.png

Изначально массивы [math]d[/math] и [math]w[/math] инициализированы следующим образом:

вершина S 1 2 3 4 T
w true false false false false false
d 1 0 0 0 0 0

Сначала функция [math]\mathrm{count}[/math] будет вызвана от вершины [math]T[/math]. Ответ для нее еще не посчитан ([math]w[T] = false[/math]), следовательно [math]\mathrm{count}[/math] будет вызвана от вершин [math]3[/math] и [math]4[/math]. Для вершины [math]3[/math] ответ также не посчитан ([math]w[3] = false[/math]), следовательно [math]\mathrm{count}[/math] будет вызвана уже для вершин [math]2[/math] и [math]S[/math]. А вот для них ответ мы уже можем узнать: для [math]2[/math] он равен [math]d[S][/math], так как это [math]S[/math] — единственная вершина, ребро из которой входит в нее. Непосредственно для [math]S[/math] ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:

вершина S 1 2 3 4 T
w true false true false false false
d 1 0 1 0 0 0

Теперь мы знаем значения для вершин [math]2[/math] и [math]S[/math], что позволяет вычислить [math]d[3] = d[2] + d[S] = 2[/math]. Также обновим значения в массиве [math]w[/math]: [math]w[3] = true[/math].

вершина S 1 2 3 4 T
w true false true true false false
d 1 0 1 2 0 0

В самом начале для вычисления [math]d[T][/math] нам требовались значения [math]d[3][/math] и [math]d[4][/math]. Теперь нам известно значение [math]d[3][/math], поэтому проследим за тем, как будет вычисляться [math]d[4][/math]. [math]\mathrm{d[4] = count(3) + count(2) + count(1)}[/math], но [math]w[3] = true, w[2] = true[/math], следовательно значения [math]d[3][/math] и [math]d[2][/math] мы уже знаем, и нам необходимо вызвать [math]\mathrm{count(1)}[/math]. Ответ для этой вершины равен [math]d[S][/math], так как это единственная вершина, ребро из которой входит в [math]1[/math]. Обновим соответствующие значения массивов [math]d[/math] и [math]w[/math]:

вершина S 1 2 3 4 T
w true true true true false false
d 1 1 1 2 0 0

Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины [math]4[/math]. [math]d[4] = d[3] + d[2] + d[1] = 2 + 1 + 1 = 4[/math]:

вершина S 1 2 3 4 T
w true true true true true false
d 1 1 1 2 4 0

Наконец, вычислим [math]d[T] = d[3] + d[4] = 2 + 4 = 6[/math] и обновим таблицы [math]d[/math] и [math]w[/math]:

вершина S 1 2 3 4 T
w true true true true true true
d 1 1 1 2 4 6

Этот алгоритм позволяет вычислить количество путей от какой-либо вершины [math]S[/math] не только до [math]T[/math], но и для любой вершины, лежащей на любом из путей от [math]S[/math] до [math]T[/math]. Для этого достаточно взять значение в соответствующей ячейке [math]d[/math].

См. также

Источники информации

  • Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..