Задача о числе путей в ациклическом графе — различия между версиями
Nafanya (обсуждение | вклад) (→Перебор всех возможных путей) |
м (rollbackEdits.php mass rollback) |
||
(не показано 17 промежуточных версий 6 участников) | |||
Строка 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|}}}| | ||
+ | <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> | ||
== Решение задачи == | == Решение задачи == | ||
Строка 7: | Строка 20: | ||
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Запустим обход в глубину от вершины <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>countPaths(g, s, t)</tex> принимает граф <tex>g</tex>, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. | + | Функция <tex>\mathrm{countPaths(g, s, t)}</tex> принимает граф <tex>g</tex> в виде списка смежности, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. |
'''countPaths'''(g, v, t) | '''countPaths'''(g, v, t) | ||
Строка 15: | Строка 28: | ||
s = 0 | s = 0 | ||
'''for''' to '''in''' g[v] | '''for''' to '''in''' g[v] | ||
− | s += ''' | + | s += '''countPaths'''(g, to, t) |
'''return''' s | '''return''' s | ||
− | Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> | + | Время работы данного алгоритма в худшем случае <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>]] | [[Файл:Dp-countpaths-example.png|600px| Пример графа, на котором алгоритм имеет время работы <tex>O(2^{n/2})</tex>]] | ||
Строка 24: | Строка 37: | ||
=== Метод динамического программирования === | === Метод динамического программирования === | ||
− | Пусть <tex>P(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>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>s</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_{c}count(c), & w[v]=false | + | \sum\limits_{c|cv \in E}count(c), & w[v]=false |
\end{array} | \end{array} | ||
\right. | \right. | ||
Строка 44: | Строка 57: | ||
'''else''' | '''else''' | ||
sum = 0 | sum = 0 | ||
+ | w[v] = ''true'' | ||
'''for''' c '''in''' g[v] | '''for''' c '''in''' g[v] | ||
sum += '''count'''(g, c) | sum += '''count'''(g, c) | ||
d[v] = sum | d[v] = sum | ||
− | |||
'''return''' sum | '''return''' sum | ||
'''countPaths'''(g, s, t) | '''countPaths'''(g, s, t) | ||
d[s] = 1 | d[s] = 1 | ||
− | w[s] = | + | w[s] = ''true'' |
answer = '''count'''(t) | answer = '''count'''(t) | ||
'''return''' answer | '''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>\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> — число ребер. |
== Пример работы == | == Пример работы == | ||
Строка 73: | Строка 86: | ||
| '''d''' || 1 || 0 || 0 || 0 || 0 || 0 | | '''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>\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;" | {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;" | ||
Строка 95: | Строка 108: | ||
|} | |} | ||
− | В самом начале для вычисления <tex>d[T]</tex> нам требовались значения <tex>d[3]</tex> и <tex>d[4]</tex>. Теперь нам известно значение <tex>d[3]</tex>, поэтому проследим за тем, как будет вычисляться <tex>d[4]</tex>. <tex>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>count(1)</tex>. Ответ для этой вершины равен <tex>d[S]</tex>, так как это единственная вершина, ребро из которой входит в <tex>1</tex>. Обновим соответствующие значения массивов <tex>d</tex> и <tex>w</tex>: | + | В самом начале для вычисления <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;" | {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;" | ||
Строка 117: | Строка 130: | ||
|} | |} | ||
− | Наконец, вычислим <tex>d[T] = d[3] + d[4] = 2 + 4 = 6</tex> и обновим таблицы <tex>d</tex> и<tex>w</tex>: | + | Наконец, вычислим <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;" | {| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;" | ||
Строка 129: | Строка 142: | ||
Этот алгоритм позволяет вычислить количество путей от какой-либо вершины <tex>S</tex> не только до <tex>T</tex>, но и для любой вершины, лежащей на любом из путей от <tex>S</tex> до <tex>T</tex>. Для этого достаточно взять значение в соответствующей ячейке <tex>d</tex>. | Этот алгоритм позволяет вычислить количество путей от какой-либо вершины <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
Задача: |
Задан ациклический граф и две вершины и . Необходимо посчитать количество путей из вершины в вершину по рёбрам графа . |
Содержание
Решение задачи
Перебор всех возможных путей
Небольшая модификация алгоритма обхода в глубину. Запустим обход в глубину от вершины . При каждом посещении вершины проверим, не является ли она искомой вершиной . Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину для всех вершин, в которые есть ребро из , причем он производится независимо от того, были эти вершины посещены ранее, или нет.
Функция
принимает граф в виде списка смежности, начальную вершину и конечную вершину .countPaths(g, v, t) if v == t return 1 else s = 0 for to in g[v] s += countPaths(g, to, t) return s
Время работы данного алгоритма в худшем случае
, где — число путей в графе из в . Например, на следующем графе данный алгоритм будет иметь время работы . Если же использовать метод динамического программирования, речь о котором пойдет ниже, то асимптотику можно улучшить до .Метод динамического программирования
Пусть
— число путей от вершины до вершины . Тогда зависит только от вершин, ребра из которых входят в . Тогда таких , что есть ребро из в . Мы свели нашу задачу к меньшим подзадачам, причем мы также знаем, что . Это позволяет решить задачу методом динамического программирования.Псевдокод
Пусть
— стартовая вершина, а — конечная, для нее и посчитаем ответ. Будем поддерживать массив , где — число путей из вершины до вершины и массив , где , если ответ для вершины уже посчитан, и в противном случае. Изначально для всех вершин , кроме , а . Функция будет возвращать ответ для вершины . Удобнее всего это реализовать в виде рекурсивной функции с запоминанием. В этом случае значения массива будут вычисляться по мере необходимости и не будут считаться лишний раз:
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
Значение функции
считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра . Всего таких ребер для всех вершин в графе , следовательно, время работы алгоритма в худшем случае оценивается как , где — число вершин графа, — число ребер.Пример работы
Рассмотрим пример работы алгоритма на следующем графе:
Изначально массивы
и инициализированы следующим образом:вершина | S | 1 | 2 | 3 | 4 | T |
w | true | false | false | false | false | false |
d | 1 | 0 | 0 | 0 | 0 | 0 |
Сначала функция
будет вызвана от вершины . Ответ для нее еще не посчитан ( ), следовательно будет вызвана от вершин и . Для вершины ответ также не посчитан ( ), следовательно будет вызвана уже для вершин и . А вот для них ответ мы уже можем узнать: для он равен , так как это — единственная вершина, ребро из которой входит в нее. Непосредственно для ответ нам также известен. На текущий момент таблица будет выглядеть следующим образом:вершина | S | 1 | 2 | 3 | 4 | T |
w | true | false | true | false | false | false |
d | 1 | 0 | 1 | 0 | 0 | 0 |
Теперь мы знаем значения для вершин
и , что позволяет вычислить . Также обновим значения в массиве : .вершина | S | 1 | 2 | 3 | 4 | T |
w | true | false | true | true | false | false |
d | 1 | 0 | 1 | 2 | 0 | 0 |
В самом начале для вычисления
нам требовались значения и . Теперь нам известно значение , поэтому проследим за тем, как будет вычисляться . , но , следовательно значения и мы уже знаем, и нам необходимо вызвать . Ответ для этой вершины равен , так как это единственная вершина, ребро из которой входит в . Обновим соответствующие значения массивов и :вершина | S | 1 | 2 | 3 | 4 | T |
w | true | true | true | true | false | false |
d | 1 | 1 | 1 | 2 | 0 | 0 |
Теперь нам известны все три значения, требующиеся для вычисления ответа для вершины
. :вершина | S | 1 | 2 | 3 | 4 | T |
w | true | true | true | true | true | false |
d | 1 | 1 | 1 | 2 | 4 | 0 |
Наконец, вычислим
и обновим таблицы и :вершина | S | 1 | 2 | 3 | 4 | T |
w | true | true | true | true | true | true |
d | 1 | 1 | 1 | 2 | 4 | 6 |
Этот алгоритм позволяет вычислить количество путей от какой-либо вершины
не только до , но и для любой вершины, лежащей на любом из путей от до . Для этого достаточно взять значение в соответствующей ячейке .См. также
- Динамическое программирование
- Кратчайший путь в ациклическом графе
- Задача о расстановке знаков в выражении
- Задача о порядке перемножения матриц
Источники информации
- Акулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9..