Викиконспекты - Вклад участника [ru]

Перечислимые языки

2016-01-19T00:58:48Z

Nafanya:

== Основные определения ==
{{Определение
|definition =
'''Полуразрешимый язык''' (англ. ''semi-decidable language'') {{---}} язык, для которого существует программа <tex>p</tex> такая, что
* <tex>\forall x \in L \Leftrightarrow p(x)=1</tex>,
* <tex>\forall x \notin L \Leftrightarrow p(x)=0</tex> или зависнет.
}}

{{Определение
|definition =
'''Перечислимый язык''' (англ. ''recursively enumerable language'') {{---}} язык, для которого существует программа <tex>g</tex> такая, что <tex>g(i) = x_i, L = \{x_1, x_2, .., x_n, ..\}</tex>. Язык <tex>L</tex> называется '''коперечислимым''' (англ. ''co-enumerable''), если <tex>\overline L</tex> {{---}} перечислимый. Класс всех перечислимых языков называется <tex> \mathrm{RE} </tex>, а всех коперечислимих <tex> \mathrm{co}</tex>-<tex>\mathrm{RE}</tex> .
}}

{{Определение
|definition =
Пусть имеется некоторая программа <tex>p</tex>, которая может либо завершиться за конечное время и что-то вернуть, либо зависнуть. Запуск программы <tex>p</tex> с '''тайм-лимитом''' (англ. ''time limit'') <tex>TL</tex> будем обозначать как <tex>p|_{TL}</tex> и иметь в виду следующее: если за <tex>TL</tex> операций программа <tex>p</tex> корректно завершилась и что-то вернула, то <tex>p|_{TL}</tex> вернёт то же самое; если же за <tex>TL</tex> операций программа <tex>p</tex> не успела завершиться, то <tex>p|_{TL}</tex> вернёт <tex>\bot</tex> (символ зависания).
}}

{{Теорема
|id=th1
|statement=
<tex>L</tex> {{---}} перечислимый <tex>\Leftrightarrow L</tex> {{---}} полуразрешимый.
|proof=
<tex> \Longrightarrow </tex>:

Пусть <tex>L</tex> {{---}} перечислимый язык. Тогда для него существует программа <tex>g</tex>, которая по номеру <tex>i</tex> выводит слово из <tex>L</tex>. Значит, для всех <tex>x</tex> из <tex>L</tex> путем перебора значений функции <tex>g</tex> мы можем найти такое <tex>i</tex>, что <tex> g(i) = x</tex>. Следовательно, существует программа <tex>p</tex>, такая, что <tex>\forall x: x \in L \Leftrightarrow p(x)=1</tex>. Тогда <tex>L</tex> является полуразрешимым языком.
<tex>{\bf p}</tex>(x):
'''for''' <tex> i = 1 ~ .. ~ \infty</tex>
'''if''' <tex> g(i) == </tex>x
'''return''' <tex> 1</tex>

<tex> \Longleftarrow </tex>:

Пусть <tex>L</tex> {{---}} полуразрешимый язык. Тогда для него существует программа <tex>p</tex>, результат которой равен <tex>1</tex> для любого слова из <tex>L</tex>. Чтобы программа <tex>p</tex> не зависала на словах, которые не принадлежат <tex>L</tex>, будем запускать ее с тайм-лимитом. Для поиска <tex>i</tex>-го слова из языка <tex>L</tex> будем перебирать <tex>k</tex> {{---}} тайм-лимит с которым будем запускать программу <tex>p</tex>. Таким образом существует программа <tex>g_0</tex>, которая выводит <tex>i</tex> слово языка <tex>L</tex> с повторениями. Для того, чтобы выводить слова без повторений, заведем множество <tex>U</tex>, в котором будем хранить уже выведенные слова. Программа <tex>g</tex> доказывает, что <tex>L</tex> является перечислимым языком.
<code>
<tex>{\bf g_0}</tex>(i):
<tex>cnt = 0</tex>
'''for''' <tex> k = 1 ~ .. ~ \infty</tex>
'''for''' <tex> x \in \{x_1, x_2, .., x_k\}</tex>
'''if''' <tex> p|_k(x) == 1</tex>
<tex>cnt</tex>++
'''if''' <tex> cnt == i</tex>
'''return''' <tex> x</tex>
</code>
<code>
<tex>{\bf g}</tex>(i):
<tex>U = \emptyset</tex>
'''for''' <tex> j = 1 ~ .. ~ \infty</tex>
<tex>x = {\bf g_0}(j)</tex>
'''if''' <tex> x \notin U</tex>
<tex>cnt</tex>++
'''if''' <tex> cnt == i</tex>
'''return''' <tex> x</tex>
<tex>U.insert(x)</tex>
</code>
}}

{{Теорема
|id=th2
|statement=
Любой [[Разрешимые_(рекурсивные)_языки | разрешимый язык]] <tex>L</tex> является перечислимым.
|proof=
Любой разрешимый язык <tex>L</tex> является полуразрешимым. Так как любой полуразрешимый язык является перечислимым, то <tex>L</tex> является перечислимым.
}}

{{Теорема
|statement=
<tex>L</tex> {{---}} перечислим и коперечислим <tex>\Rightarrow</tex> <tex>L</tex> {{---}} [[Разрешимые_(рекурсивные)_языки|разрешим]].
|proof=
Рассмотрим полуразрешители для <tex>L</tex> и <tex>\overline L</tex> и одновременно запустим их для одного и того же элемента <tex>x</tex>. <tex>x</tex> принадлежит либо <tex> L </tex>, либо <tex>\overline{L}</tex>, поэтому один из полуразрешителей успешно отработает и не зависнет. Значит, мы за конечное время узнаем, лежит ли <tex>x</tex> в <tex>L</tex> или нет. Таким образом, мы построили разрешитель для <tex>L</tex>, то есть <tex>L</tex> {{---}} разрешимый.
}}
== Примеры перечислимых языков ==

{{Утверждение
|id=st1
|statement=
Язык натуральных чисел перечислим.
|proof=
Приведём программу, перечисляющую язык натуральных чисел:
<code>
<tex>p(i) {:} </tex>
'''return''' i
</code>

}}

{{Утверждение
|id=st2
|statement=
Язык чётных неотрицательных чисел перечислим.
|proof=
Приведём программу, перечисляющую язык чётных неотрицательных чисел:
<code>
<tex>p(i) {:} </tex>
'''return''' i * 2
</code>

}}

== Примеры коперечислимых языков ==

{{Утверждение
|id=st2
|statement=
Язык нечётных неотрицательных чисел коперечислим.
|proof=
<tex>\overline L</tex> - язык чётных неотрицательных чисел. Так как язык чётных неотрицательных чисел перечислим, то и язык нечётных неотрицательных чисел тоже перечислим.

}}

== Примеры неперечислимых языков ==

{{Утверждение
|id=st2
|statement=
Язык пар <tex>\langle n, bb(n)\rangle</tex> неперечислим.
|proof=
Функция [[Busy_beaver | busy beaver]] <tex>bb(n)</tex> {{---}} невычислима, следовательно такой язык неперечислим.
}}

== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* [http://en.wikipedia.org/wiki/Recursively_enumerable_language Wikipedia {{---}} Recursively enumerable language]
* [http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%BE_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA Википедия {{---}} Рекурсивно перечислимый язык]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]

Файл:Mt3.png

2016-01-18T02:13:38Z

Nafanya: загружена новая версия «Файл:Mt3.png»

Машина Тьюринга

2016-01-18T02:08:14Z

Nafanya:

'''Машина Тьюринга''' (англ. ''Turing machine'') — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головки, которая представляет собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].

При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.

== Определение ==
=== Определение машины ===
{{Определение
|definition=
Формально '''машина Тьюринга''' (англ. ''Turing machine'') определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,
* <tex>\Pi \supset \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины,
* <tex>B \in \Pi \setminus \Sigma</tex> — пробельный символ (от слова ''blank''),
* <tex>Q</tex> — множество состояний управляющего автомата,
* <tex>Y \in Q</tex> — допускающее состояние автомата,
* <tex>N \in Q</tex> — отвергающее состояние автомата,
* <tex>S \in Q</tex> — стартовое состояние автомата,
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата.
}}
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.

=== Определение процесса работы ===
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
{{Определение
|id=conf
|definition=
Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где
* <tex>q \in Q</tex> — текущее состояние автомата,
* <tex>w, v \in (\Pi \setminus \{B\})^*</tex> — строки слева и справа от головки до первого пробельного символа соответственно.
}}
В данной записи головка находится над ячейкой, на которой написана первая буква <tex>v</tex> (или <tex>B</tex>, если <tex>v = \varepsilon</tex>).

В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
{{Определение
|definition=
Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</tex>:
* если <tex>\delta(q, x) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle</tex>,
* если <tex>\delta(q, x) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle</tex>,
* если <tex>\delta(q, x) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle</tex>,

Особо следует рассмотреть случай переходов по пробельному символу:
* если <tex>\delta(q, B) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle</tex>
}}
Очевидно, что определённое отношение является функциональным: для каждой конфигурации <tex>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.

Для машины Тьюринга, которая пишет символ <tex>B</tex> на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

=== Результат работы ===
Машину Тьюринга можно рассматривать как распознаватель слов [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|формального языка]]. Пусть <tex>M</tex> — машина Тьюринга, распознаваемый ей язык определяется как <tex>\mathcal L(M) = \{ x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \}</tex>.

Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина <tex>M</tex> задаёт [[Вычислимые функции|вычислимую функцию]] <tex>f</tex>, причём <tex>f(x) = y \Leftrightarrow \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle</tex>. Переход автомата в состояние <tex>N</tex> можно интерпретировать как аварийное завершение программы (например, при некорретном входе).

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

== Примеры машин Тьюринга ==
=== Прибавление единицы ===
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
* в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
* встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние <tex>R</tex>,
* в состоянии <tex>R</tex> головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
* встретив в состоянии <tex>R</tex> пробельный символ, головка перемещается на один символ вправо и переходит в состояние <tex>Y</tex>, завершая работу.

Формально: <tex>\Sigma = \{0, 1 \}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, R, Y, N \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:

{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle R, 1, \downarrow \rangle</tex>
| <tex>\langle S, 0, \rightarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \rightarrow \rangle</tex>
|}

=== Проверка того, является ли слово палиндромом ===
В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом <tex>\{0, 1\}</tex>. Алгоритм следующий:
* если строка на ленте — пустая, то перейти в допускающее состояние
* надо запомнить первый символ слова в состоянии автомата,
* стереть его,
* перейти в конец ленты:
** если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
** если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
** в случае несовпадения перейти в отвергающее состояние

Формально: <tex>\Sigma = \{0, 1\}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, F_0, F_1, B_0, B_1, R \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:
{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle F_0, B, \rightarrow \rangle</tex>
| <tex>\langle F_1, B, \rightarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>F_0</tex>
| <tex>\langle F_0, 0, \rightarrow \rangle</tex>
| <tex>\langle F_0, 1, \rightarrow \rangle</tex>
| <tex>\langle B_0, B, \leftarrow \rangle</tex>
|-
| <tex>F_1</tex>
| <tex>\langle F_1, 0, \rightarrow \rangle</tex>
| <tex>\langle F_1, 1, \rightarrow \rangle</tex>
| <tex>\langle B_1, B, \leftarrow \rangle</tex>
|-
| <tex>B_0</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle N, 1, \downarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>B_1</tex>
| <tex>\langle N, 0, \downarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle S, B, \rightarrow \rangle</tex>
|}

== Варианты машины Тьюринга ==
В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности.

=== Многодорожечная машина Тьюринга ===
Машиной Тьюринга с <tex>n</tex> дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из <tex>n</tex> дорожек, на каждой из которых записаны символы ленточного алфавита. У многодорожечной машины одна головка, которая за один шаг переходит в одном направлении на всех дорожках одновременно. Соответственно, функция перехода имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}</tex>. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом <tex>\Pi' = \Pi^n</tex>.

=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.
{{Теорема
|author=
|statement=Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом:

[[Файл:Mt1.png]]

Затем перенумеруем ячейки, и запишем символ <tex>c \in \Pi \setminus \Sigma, B</tex> в начало ленты, который будет означать границу рабочей зоны:

[[Файл:Mt2.png]]

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны:

[[Файл:Mt3.png]]

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.
}}

=== Многоленточная машина Тьюринга ===
В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу перемещаться по-разному. То есть, функция перехода теперь имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}^n</tex>.

Многоленточная машина с <tex>n</tex> дорожками эмулируется многодорожечной машиной с <tex>2n</tex> дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом <tex>*</tex> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:
{{Утверждение
|about=Тезис Чёрча-Тьюринга
|statement=
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
}}
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

== Универсальная машина Тьюринга ==

Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.

== См. также ==
* [[Стековые машины, эквивалентность двухстековой машины МТ|Стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|Счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|Клеточные автоматы]]
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|Произвольные формальные грамматики]]
* [[Лямбда-исчисление|Нетипизированное лямбда-исчисление]]

== Источники информации ==
* [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf Alan Turing {{---}} On computable numbers, with an application to the Entscheidungsproblem.]
* [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf F. C. Hennie, R. E. Stearn {{---}} Two-tape simulation of multitape Turing machines.]
* [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft Sanjeev Arora, Boaz Barak {{---}} Computational Complexity: A Modern Approach.]
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.8958 Turlough Neary, Damien Woods {{---}} Four Small Universal Turing Machines.]
* [http://www.jflap.org/ JFLAP {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]

Файл:Mt1.png

2016-01-18T02:06:59Z

Nafanya: загружена новая версия «Файл:Mt1.png»

Файл:Mt2.png

2016-01-18T02:06:37Z

Nafanya: загружена новая версия «Файл:Mt2.png»

Файл:Mt3.png

2016-01-17T21:35:30Z

Nafanya: загружена новая версия «Файл:Mt3.png»

Файл:Mt3.png

2016-01-17T21:35:09Z

Nafanya: загружена новая версия «Файл:Mt3.png»

Файл:Mt3.png

2016-01-17T21:09:01Z

Nafanya:

Машина Тьюринга

2016-01-14T14:19:29Z

Nafanya:

'''Машина Тьюринга''' (англ. ''Turing machine'') — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головки, которая представляет собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].

При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.

== Определение ==
=== Определение машины ===
{{Определение
|definition=
Формально '''машина Тьюринга''' (англ. ''Turing machine'') определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова,
* <tex>\Pi \supset \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины,
* <tex>B \in \Pi \setminus \Sigma</tex> — пробельный символ (от слова ''blank''),
* <tex>Q</tex> — множество состояний управляющего автомата,
* <tex>Y \in Q</tex> — допускающее состояние автомата,
* <tex>N \in Q</tex> — отвергающее состояние автомата,
* <tex>S \in Q</tex> — стартовое состояние автомата,
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата
}}
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.

=== Определение процесса работы ===
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
{{Определение
|id=conf
|definition=
Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где <tex>q \in Q</tex> — текущее состояние автомата, а <tex>w, v \in (\Pi \setminus \{B\})^*</tex> — строки слева и справа от головки до первого пробельного символа соответственно.
}}
В данной записи головка находится над ячейкой, на которой написана первая буква <tex>v</tex> (или <tex>B</tex>, если <tex>v = \varepsilon</tex>).

В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
{{Определение
|definition=
Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</tex>:
* если <tex>\delta(q, x) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle</tex>,
* если <tex>\delta(q, x) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle</tex>,
* если <tex>\delta(q, x) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle</tex>,

Особо следует рассмотреть случай переходов по пробельному символу:
* если <tex>\delta(q, B) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle</tex>
}}
Очевидно, что определённое отношение является функциональным: для каждой конфигурации <tex>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.

Для машины Тьюринга, которая пишет символ <tex>B</tex> на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

=== Результат работы ===
Машину Тьюринга можно рассматривать как распознаватель слов [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|формального языка]]. Пусть <tex>M</tex> — машина Тьюринга, распознаваемый ей язык определяется как <tex>\mathcal L(M) = \{ x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \}</tex>.

Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина <tex>M</tex> задаёт [[Вычислимые функции|вычислимую функцию]] <tex>f</tex>, причём <tex>f(x) = y \Leftrightarrow \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle</tex>. Переход автомата в состояние <tex>N</tex> можно интерпретировать как аварийное завершение программы (например, при некорретном входе).

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

== Примеры машин Тьюринга ==
=== Прибавление единицы ===
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
* в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
* встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние <tex>R</tex>,
* в состоянии <tex>R</tex> головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
* встретив в состоянии <tex>R</tex> пробельный символ, головка перемещается на один символ вправо и переходит в состояние <tex>Y</tex>, завершая работу.

Формально: <tex>\Sigma = \{0, 1 \}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, R, Y, N \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:

{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle R, 1, \downarrow \rangle</tex>
| <tex>\langle S, 0, \rightarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \rightarrow \rangle</tex>
|}

=== Проверка того, является ли слово палиндромом ===
В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом <tex>\{0, 1\}</tex>. Алгоритм следующий:
* если строка на ленте — пустая, то перейти в допускающее состояние
* надо запомнить первый символ слова в состоянии автомата,
* стереть его,
* перейти в конец ленты:
** если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
** если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
** в случае несовпадения перейти в отвергающее состояние

Формально: <tex>\Sigma = \{0, 1\}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, F_0, F_1, B_0, B_1, R \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:
{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle F_0, B, \rightarrow \rangle</tex>
| <tex>\langle F_1, B, \rightarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>F_0</tex>
| <tex>\langle F_0, 0, \rightarrow \rangle</tex>
| <tex>\langle F_0, 1, \rightarrow \rangle</tex>
| <tex>\langle B_0, B, \leftarrow \rangle</tex>
|-
| <tex>F_1</tex>
| <tex>\langle F_1, 0, \rightarrow \rangle</tex>
| <tex>\langle F_1, 1, \rightarrow \rangle</tex>
| <tex>\langle B_1, B, \leftarrow \rangle</tex>
|-
| <tex>B_0</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle N, 1, \downarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>B_1</tex>
| <tex>\langle N, 0, \downarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle S, B, \rightarrow \rangle</tex>
|}

== Варианты машины Тьюринга ==
В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности.

=== Многодорожечная машина Тьюринга ===
Машиной Тьюринга с <tex>n</tex> дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из <tex>n</tex> дорожек, на каждой из которых записаны символы ленточного алфавита. У многодорожечной машины одна головка, которая за один шаг переходит в одном направлении на всех дорожках одновременно. Соответственно, функция перехода имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}</tex>. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом <tex>\Pi' = \Pi^n</tex>.

=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.
{{Теорема
|author=
|statement=Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом:

[[Файл:Mt1.png]]

Затем перенумеруем ячейки, и запишем символ <tex>c \in \Pi \setminus \Sigma, B</tex> в начало ленты, который будет означать границу рабочей зоны:

[[Файл:Mt2.png]]

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны:

[[Файл:Mt3.jpg]]

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.
}}

=== Многоленточная машина Тьюринга ===
В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу перемещаться по-разному. То есть, функция перехода теперь имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}^n</tex>.

Многоленточная машина с <tex>n</tex> дорожками эмулируется многодорожечной машиной с <tex>2n</tex> дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом <tex>*</tex> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:
{{Утверждение
|about=Тезис Чёрча-Тьюринга
|statement=
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
}}
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

== Универсальная машина Тьюринга ==

Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.

== См. также ==
* [[Стековые машины, эквивалентность двухстековой машины МТ|стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|клеточные автоматы]]
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|произвольные формальные грамматики]]
* [[Лямбда-исчисление|нетипизированное лямбда-исчисление]]

== Источники информации ==
* [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf Alan Turing {{---}} On computable numbers, with an application to the Entscheidungsproblem.]
* [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf F. C. Hennie, R. E. Stearn {{---}} Two-tape simulation of multitape Turing machines.]
* [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft Sanjeev Arora, Boaz Barak {{---}} Computational Complexity: A Modern Approach.]
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.8958 Turlough Neary, Damien Woods {{---}} Four Small Universal Turing Machines.]
* [http://www.jflap.org/ JFLAP {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]

[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]

Файл:Mt2.png

2016-01-14T01:03:51Z

Nafanya:

Файл:Mt1.png

2016-01-10T19:29:17Z

Nafanya:

Машина Тьюринга

2016-01-07T18:57:34Z

Nafanya: тикет 3.14

'''Машина Тьюринга''' (англ. ''Turing machine'') — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое - проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе - не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.

Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головки, которая представляет собой [[Детерминированные конечные автоматы|детерминированный конечный автомат]].

При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.

== Определение ==
=== Определение машины ===
{{Определение
|definition=
Формально '''машина Тьюринга''' определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
* <tex>\Pi \supset \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины
* <tex>B \in \Pi \setminus \Sigma</tex> — пробельный символ (от слова ''blank'')
* <tex>Q</tex> — множество состояний управляющего автомата
* <tex>Y \in Q</tex> — допускающее состояние автомата
* <tex>N \in Q</tex> — отвергающее состояние автомата
* <tex>S \in Q</tex> — стартовое состояние автомата
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — всюду определённая функция перехода автомата
}}
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.

=== Определение процесса работы ===
Кроме формального определения самой машины требуется также формально описать процесс её работы. В определении для простоты будем предполагать, что головка в процессе работы не записывает на ленту символ <tex>B</tex>. Это не ограничивает вычислительной мощности машин Тьюринга, поскольку для каждой машины можно сопоставить аналогичную ей, но не пищущую <tex>B</tex> на ленту.
{{Определение
|id=conf
|definition=
Назовём '''конфигурацией''' машины Тьюринга тройку <tex>\langle w, q, v \rangle</tex>, где <tex>q \in Q</tex> — текущее состояние автомата, а <tex>w, v \in (\Pi \setminus \{B\})^*</tex> — строки слева и справа от головки до первого пробельного символа соответственно.
}}
В данной записи головка находится над ячейкой, на которой написана первая буква <tex>v</tex> (или <tex>B</tex>, если <tex>v = \varepsilon</tex>).

В дальнейшем используются следующие обозначения: <tex>x, y, z \in \Pi</tex>, <tex>w, v \in \Pi^*</tex>
{{Определение
|definition=
Определим на конфигурациях отношение перехода <tex>\langle w_1, q_1, v_1 \rangle \vdash \langle w_2, q_2, v_2 \rangle</tex>:
* если <tex>\delta(q, x) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, xv \rangle \vdash \langle w, p, zyv \rangle</tex>
* если <tex>\delta(q, x) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle wy, p, v \rangle</tex>
* если <tex>\delta(q, x) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, xv \rangle \vdash \langle w, p, yv \rangle</tex>

Особо следует рассмотреть случай переходов по пробельному символу:
* если <tex>\delta(q, B) = \langle p, y, \leftarrow \rangle</tex>, то <tex>\langle wz, q, \varepsilon \rangle \vdash \langle w, p, zy \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle</tex>
}}
Очевидно, что определённое отношение является функциональным: для каждой конфигурации <tex>C</tex> существует не более одной конфигурации <tex>C'</tex>, для которой <tex>C \vdash C'</tex>.

Для машины Тьюринга, которая пишет символ <tex>B</tex> на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.

=== Результат работы ===
Машину Тьюринга можно рассматривать как распознаватель слов [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|формального языка]]. Пусть <tex>M</tex> — машина Тьюринга, распознаваемый ей язык определяется как <tex>\mathcal L(M) = \{ x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \}</tex>.

Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина <tex>M</tex> задаёт [[Вычислимые функции|вычислимую функцию]] <tex>f</tex>, причём <tex>f(x) = y \Leftrightarrow \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle</tex>. Переход автомата в состояние <tex>N</tex> можно интерпретировать как аварийное завершение программы (например, при некорретном входе).

Примеры машин-распознавателей и машин-преобразователей будут даны ниже.

== Примеры машин Тьюринга ==
=== Прибавление единицы ===
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
* в стартовом состоянии головка идёт вправо от младшего бита к старшему, заменяя все единицы на нули,
* встретив нуль или пробельный символ головка записывает единицу, после чего переходит в состояние <tex>R</tex>,
* в состоянии <tex>R</tex> головка идёт влево от старшего бита к младшему, не изменяя символы 0 и 1 на ленте,
* встретив в состоянии <tex>R</tex> пробельный символ, головка перемещается на один символ вправо и переходит в состояние <tex>Y</tex>, завершая работу.

Формально: <tex>\Sigma = \{0, 1 \}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, R, Y, N \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:

{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle R, 1, \downarrow \rangle</tex>
| <tex>\langle S, 0, \rightarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \rightarrow \rangle</tex>
|}

=== Проверка того, является ли слово палиндромом ===
В качестве примера машины-распознавателя приведём машину, распознающую палиндромы над алфавитом <tex>\{0, 1\}</tex>. Алгоритм следующий:
* если строка на ленте — пустая, то перейти в допускающее состояние
* надо запомнить первый символ слова в состоянии автомата,
* стереть его,
* перейти в конец ленты:
** если оставшаяся строка на ленте — пустая, то перейти в допускающее состояние
** если последний символ совпадает с запомненным, стереть его, перейти в начало ленты и повторить с первого шага
** в случае несовпадения перейти в отвергающее состояние

Формально: <tex>\Sigma = \{0, 1\}</tex>, <tex>\Pi = \{0, 1, B\}</tex>, <tex>Q = \{S, F_0, F_1, B_0, B_1, R \}</tex>. Таблица функции <tex>\delta</tex> приведена ниже:
{| border="0" cellspacing="5"
|-
|width="30"|
|width="100"| <tex>0</tex>
|width="100"| <tex>1</tex>
|width="100"| <tex>B</tex>
|-
| <tex>S</tex>
| <tex>\langle F_0, B, \rightarrow \rangle</tex>
| <tex>\langle F_1, B, \rightarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>F_0</tex>
| <tex>\langle F_0, 0, \rightarrow \rangle</tex>
| <tex>\langle F_0, 1, \rightarrow \rangle</tex>
| <tex>\langle B_0, B, \leftarrow \rangle</tex>
|-
| <tex>F_1</tex>
| <tex>\langle F_1, 0, \rightarrow \rangle</tex>
| <tex>\langle F_1, 1, \rightarrow \rangle</tex>
| <tex>\langle B_1, B, \leftarrow \rangle</tex>
|-
| <tex>B_0</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle N, 1, \downarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>B_1</tex>
| <tex>\langle N, 0, \downarrow \rangle</tex>
| <tex>\langle R, B, \leftarrow \rangle</tex>
| <tex>\langle Y, B, \downarrow \rangle</tex>
|-
| <tex>R</tex>
| <tex>\langle R, 0, \leftarrow \rangle</tex>
| <tex>\langle R, 1, \leftarrow \rangle</tex>
| <tex>\langle S, B, \rightarrow \rangle</tex>
|}

== Варианты машины Тьюринга ==
В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности.

=== Многодорожечная машина Тьюринга ===
Машиной Тьюринга с <tex>n</tex> дорожками называется вычислитель, аналогичный машине Тьюринга, лишь с тем отличием, что лента состоит из <tex>n</tex> дорожек, на каждой из которых записаны символы ленточного алфавита. У многодорожечной машины одна головка, которая за один шаг переходит в одном направлении на всех дорожках одновременно. Соответственно, функция перехода имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}</tex>. Многодорожечная машина Тьюринга тривиально эквивалентна обычной с ленточным алфавитом <tex>\Pi' = \Pi^n</tex>.

=== Машина Тьюринга с полубесконечной лентой ===
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.
{{Теорема
|author=
|statement=Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.
|proof=Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с ''бесконечной лентой'' следующим образом:

[[Файл:Mt1.jpg]]

Затем перенумеруем ячейки, и запишем символ <tex>c \in \Pi \setminus \Sigma, B</tex> в начало ленты, который будет означать границу рабочей зоны:

[[Файл:Mt2.jpg]]

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе машины Тьюринга встретится символ <tex>c</tex>, значит головка достигла границы рабочей зоны:

[[Файл:Mt3.jpg]]

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.
}}

=== Многоленточная машина Тьюринга ===
В отличие от многодорожечной машины Тьюринга, ленты не зависят друг от друга и головки во время одного шага могу перемещаться по-разному. То есть, функция перехода теперь имеет тип <tex>\delta : Q \times \Pi^n \to Q \times \Pi^n \times \{\leftarrow, \rightarrow, \downarrow\}^n</tex>.

Многоленточная машина с <tex>n</tex> дорожками эмулируется многодорожечной машиной с <tex>2n</tex> дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом <tex>*</tex> позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов <tex>*</tex> символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

=== Другие эквивалентные вычислительные формализмы ===
Существуют также другие формализации понятия алгоритма, которые по вычислительным возможностям эквивалентны машинам Тьюринга:
* [[Стековые машины, эквивалентность двухстековой машины МТ|стековые машины]]
* [[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ|счётчиковые машины]]
* [[Линейный клеточный автомат, эквивалентность МТ|клеточные автоматы]]
* [[Возможность порождения формальной грамматикой произвольного перечислимого языка|произвольные формальные грамматики]]
* [[Лямбда-исчисление|нетипизированное лямбда-исчисление]]

Аланом Тьюрингом было сформулировано следующее утверждение:
{{Утверждение
|about=Тезис Чёрча-Тьюринга
|statement=
Класс перечислимых языков совпадает с классом языков, перечислимых с помощью машин Тьюринга
}}
Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

== Универсальная машина Тьюринга ==

Существует машина Тьюринга, которая принимает на вход закодированное описание произвольной машины и входную строку и эмулирует работу закодированной машины на заданном входном слове. Иными словами, [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|универсальный язык]] перечислим с помощью машины Тьюринга. Ссылки на явные конструкции универсальных машин Тьюринга приведены ниже.

== Источники информации ==
* [http://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf Alan Turing {{---}} On computable numbers, with an application to the Entscheidungsproblem.]
* [http://www.ccs.neu.edu/home/viola/classes/papers/HennieStearns66.pdf F. C. Hennie, R. E. Stearn {{---}} Two-tape simulation of multitape Turing machines.]
* [http://www.cs.princeton.edu/theory/index.php/Compbook/Draft Sanjeev Arora, Boaz Barak {{---}} Computational Complexity: A Modern Approach.]
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.8958 Turlough Neary, Damien Woods {{---}} Four Small Universal Turing Machines.]
* [http://www.jflap.org/ JFLAP {{---}} ПО для изучения формальных языков, включает в себя эмулятор одноленточных и многоленточных машин Тьюринга с визуальным редактором.]

[[Категория: Теория формальных языков]]

Файл:Mt3.jpg

2016-01-07T09:59:01Z

Nafanya: Машина Тьюринга на полубесконечной ленте - переходы

Машина Тьюринга на полубесконечной ленте - переходы

Файл:Mt2.jpg

2016-01-07T09:05:38Z

Nafanya: Машина Тьюринга на полубесконечной ленте - нумерация ячеек

Машина Тьюринга на полубесконечной ленте - нумерация ячеек

Файл:Mt1.jpg

2016-01-07T09:03:26Z

Nafanya: Машина Тьюринга на полубесконечной ленте

Машина Тьюринга на полубесконечной ленте

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

2014-01-03T16:49:27Z

Nafanya: /* Пример работы */

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

Функция <tex>countPaths(g, s, t)</tex> принимает граф <tex>g</tex> в виде списка смежности, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>.

'''countPaths'''(g, v, t)
'''if''' v == t
'''return''' 1
'''else'''
s = 0
'''for''' to '''in''' g[v]
s += '''count'''(g, 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)</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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

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

'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2014-01-03T16:48:44Z

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

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

Функция <tex>countPaths(g, s, t)</tex> принимает граф <tex>g</tex> в виде списка смежности, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>.

'''countPaths'''(g, v, t)
'''if''' v == t
'''return''' 1
'''else'''
s = 0
'''for''' to '''in''' g[v]
s += '''count'''(g, 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)</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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

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

'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2014-01-03T16:47:22Z

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

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

Функция <tex>countPaths(g, s, t)</tex> принимает граф <tex>g</tex>, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>.

'''countPaths'''(g, v, t)
'''if''' v == t
'''return''' 1
'''else'''
s = 0
'''for''' to '''in''' g[v]
s += '''count'''(g, 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)</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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

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

'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2014-01-03T16:36:37Z

Nafanya:

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

Функция <tex>countPaths(g, s, t)</tex> принимает граф <tex>g</tex>, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>.

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

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

[[Файл:Dp-countpaths-example.png‎|600px| Пример графа, на котором алгоритм имеет время работы <tex>O(2^n)</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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

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

'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2014-01-03T16:26:52Z

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

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

Функция <tex>countPaths(g, s, t)</tex> принимает граф <tex>g</tex>, начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>.

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

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

[[Файл:Dp-countpaths-example.png‎|left|thumb|600px| Пример графа, на котором алгоритм имеет время работы <tex>O(2^n)</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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

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

'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

Файл:Dp-countpaths-example.png

2014-01-03T16:16:53Z

Nafanya:

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

2013-12-29T18:22:56Z

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

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

Функция <tex>countPaths(s, t)</tex> принимает начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. В глобальной переменной <tex>answer</tex> содержится ответ.

<code>
answer = 0

'''count'''(v)
'''if''' v == t
answer += 1
'''else'''
'''for'''(всех <tex>to</tex> смежных с <tex>v</tex>)
'''count'''(to)

'''countPaths'''(s, t)
answer = 0
count(s)
'''return''' answer

</code>

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе из <tex>s</tex> в <tex>t</tex>.

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

Пусть <tex>P(v)</tex> - количество путей до вершины <tex>v</tex>.
Можно заметить, что <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, что <tex>\exists</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>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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

<code>
'''count'''(v)
'''if''' w[v]
'''return''' d[v]
'''else'''
sum = 0
'''for'''(всех <tex>c</tex> смежных с <tex>v</tex>)
sum += '''count'''(c)
d[v] = sum
w[v] = true
'''return''' sum

'''countPaths'''(s, t)
d[s] = 1
w[s] = true
answer = '''count'''(t)
'''return''' answer
</code>

Значение функции <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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2013-12-29T15:30:14Z

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

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

Функция <tex>countPaths(s, t)</tex> принимает начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. В глобальной переменной <tex>answer</tex> содержится ответ.

<code>
answer = 0

'''count'''(v)
'''if''' v == t
answer += 1
'''else'''
'''for'''(всех <tex>to</tex> смежных с <tex>v</tex>)
'''count'''(to)

'''countPaths'''(s, t)
answer = 0
count(s)
'''return''' answer

</code>

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</tex> - количество путей до вершины <tex>v</tex>.
Можно заметить, что <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, что <tex>\exists</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>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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

<code>
'''count'''(v)
'''if''' w[v]
'''return''' d[v]
'''else'''
sum = 0
'''for'''(всех <tex>c</tex> смежных с <tex>v</tex>)
sum += '''count'''(c)
d[v] = sum
w[v] = true
'''return''' sum

'''countPaths'''(s, t)
d[s] = 1
w[s] = true
answer = '''count'''(t)
'''return''' answer
</code>

Значение функции <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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2013-12-29T15:29:39Z

Nafanya: описание картинки

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

Функция <tex>countPaths(s, t)</tex> принимает начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. В глобальной переменной <tex>answer</tex> содержится ответ.

<code>
answer = 0

'''count'''(v)
'''if''' v == t
answer += 1
'''else'''
'''for'''(всех <tex>to</tex> смежных с <tex>v</tex>)
'''count'''(to)

'''countPaths'''(s, t)
answer = 0
count(s)
return answer

</code>

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</tex> - количество путей до вершины <tex>v</tex>.
Можно заметить, что <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, что <tex>\exists</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>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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

<code>
'''count'''(v)
'''if''' w[v]
'''return''' d[v]
'''else'''
sum = 0
'''for'''(всех <tex>c</tex> смежных с <tex>v</tex>)
sum += '''count'''(c)
d[v] = sum
w[v] = true
'''return''' sum

'''countPaths'''(s, t)
d[s] = 1
w[s] = true
answer = '''count'''(t)
'''return''' answer
</code>

Значение функции <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> - количество ребер.

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

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

[[Файл: 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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2013-12-29T15:26:09Z

Nafanya:

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

Функция <tex>countPaths(s, t)</tex> принимает начальную вершину <tex>s</tex> и конечную вершину <tex>t</tex>. В глобальной переменной <tex>answer</tex> содержится ответ.

<code>
answer = 0

'''count'''(v)
'''if''' v == t
answer += 1
'''else'''
'''for'''(всех <tex>to</tex> смежных с <tex>v</tex>)
'''count'''(to)

'''countPaths'''(s, t)
answer = 0
count(s)
return answer

</code>

Время работы данного алгоритма в худшем случае <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</tex> - количество путей до вершины <tex>v</tex>.
Можно заметить, что <tex>P(v)</tex> зависит только от вершин, ребра из которых входят в <tex>v</tex>. Тогда <tex>P(v) = \sum\limits_{c}P(c)</tex> таких <tex>c</tex>, что <tex>\exists</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>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 \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{c}count(c), & w[v]=false
\end{array}
\right.
</tex>

<code>
'''count'''(v)
'''if''' w[v]
'''return''' d[v]
'''else'''
sum = 0
'''for'''(всех <tex>c</tex> смежных с <tex>v</tex>)
sum += '''count'''(c)
d[v] = sum
w[v] = true
'''return''' sum

'''countPaths'''(s, t)
d[s] = 1
w[s] = true
answer = '''count'''(t)
'''return''' answer
</code>

Значение функции <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> - количество ребер.

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

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

[[Файл: count-path-graph-example.png|thumb|300px| description ]]

Изначально массивы <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>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;"
|-
| '''вершина''' || 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>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>:

{| 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>.

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2013-12-26T22:36:12Z

Nafanya:

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

2013-12-22T13:16:43Z

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

'''Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой.

Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования.

* '''Постановка задачи'''
Дан ациклический граф <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>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от всех детей <tex>v</tex>, причем он производится независимо от того, были ли эти вершины посещены ранее, или нет.

<code>
count(v):
if v == t:
ans += 1
else:
for(child : v):
count(child)

</code>

Время работы данного алгоритма <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</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>O(V + E)</tex>, где <tex>V</tex> - количество вершин графа, <tex>E</tex> - количество вершин. Функция <tex>P(v)</tex> вызывается от каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ begin(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</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> count(v) = \left \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{parent}count(parent), & w[v]=false
\end{array}
\right.
</tex>

<code>
count(v):
if w[v]:
return d[v]
else:
sum = 0
for(parent : v):
sum += count(parent)
d[v] = sum
w[v] = true
return sum

countPaths(s, t):
d[s] = 1
w[s] = true
answer = count(t)
</code>

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

Файл:Count-path-graph-example.png

2013-12-21T22:01:35Z

Nafanya: Пример графа для задачи о числе путей в ациклическом графе.

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

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

2013-12-21T21:36:29Z

Nafanya: /* Решение задачи */

'''Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой.

Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования.

* '''Постановка задачи'''
Дан ациклический граф <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>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от всех детей <tex>v</tex>, причем он производится независимо от того, были ли эти вершины посещены ранее, или нет.

<code>
count(v):
if v == t:
ans += 1
else:
for(child : v):
count(child)

</code>

Время работы данного алгоритма <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</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>\{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> count(v) = \left \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{parent}count(parent), & w[v]=false
\end{array}
\right.
</tex>

<code>
count(v):
if w[v]:
return d[v]
else:
sum = 0
for(parent : v):
sum += count(parent)
d[v] = sum
w[v] = true
return sum

countPaths(s, t):
d[s] = 1
w[s] = true
answer = count(t)
</code>

[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]

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

2013-12-21T21:33:52Z

Nafanya: /* Решение задачи */

'''Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой.

Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования.

* '''Постановка задачи'''
Дан ациклический граф <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>. Если это так, то ответ увеличивается на единицу и обход прекращается. В противном случае производится запуск обхода в глубину от всех детей <tex>v</tex>, причем он производится независимо от того, были ли эти вершины посещены ранее, или нет.

<code>
count(v):
if v == t:
ans += 1
else:
for(child : v):
count(child)

</code>

Время работы данного алгоритма <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</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>\{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> count(v) = \left \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{parent}count(parent), & w[v]=false
\end{array}
\right.
</tex>

<code>
count(v):
if w[v]:
return d[v]
else:
sum = 0
for(parent : v):
sum += count(parent)
d[v] = sum
w[v] = true
return sum

countPaths(s, t):
d[s] = 1
w[s] = true
answer = count(t)
</code>

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

2013-12-21T21:32:49Z

Nafanya: initial commit

'''Задача о числе путей в ациклическом графе''' - одна из классических задач на тему динамического программирования. В этой задаче нам дан граф, не содержащий циклов, в котором необходимо посчитать количество различных путей от одной вершины до другой.

Число таких путей может быть велико даже на небольших графах, поэтому перебор всех возможных вариантов займет много времени. Однако, данную задачу можно решить гораздо быстрее методом динамического программирования.

* '''Постановка задачи'''
Дан ациклический граф <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.

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

=== Перебор всех возможных путей за O(''Ans'') ===

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

<code>
count(v):
if v == t:
ans += 1
else:
for(child : v):
count(child)

</code>

Время работы данного алгоритма <tex>O(Ans)</tex>, где <tex>Ans</tex> - количество путей в графе.

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

Пусть <tex>P(v)</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>\{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> count(v) = \left \{
\begin{array}{ll}
d[v], & w[v]=true \\
\sum\limits_{parent}count(parent), & w[v]=false
\end{array}
\right.
</tex>

<code>
count(v):
if w[v]:
return d[v]
else:
sum = 0
for(parent : v):
sum += count(parent)
d[v] = sum
w[v] = true
return sum

countPaths(s, t):
d[s] = 1
w[s] = true
answer = count(t)
</code>