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

Теорема о рекурсии

2019-04-26T01:35:04Z

Arimon: /* Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка */

==Теорема о рекурсии==

Рассмотрим произвольную вычислимую функцию от двух аргументов — <tex>V(x, y)</tex>. Теорема о рекурсии утверждает, что всегда можно найти эквивалентную ей <tex>p(y) = V(p, y)</tex>, которая будет использовать саму себя для вычисления значения. Сформулируем теорему более формально.
{{Теорема
|id=th1
|author=Клини
|about=о рекурсии / ''Kleene's recursion theorem''
|statement= Пусть <tex>V(n, x)</tex> {{---}} [[Вычислимые функции|вычислимая функция]]. Тогда найдётся такая вычислимая <tex>p</tex>, что <tex>\forall y:</tex> <tex>p(y) = V(p, y)</tex>.
|proof=
Приведем конструктивное доказательство теоремы.

Введем новые обозначения для псевдокода. Внутри блока '''program''' располагаются функции, среди которых есть функция <tex>\mathrm{main}</tex>:
'''program int''' p('''int''' x):
...

'''int''' main():
...

...
Тогда вызов <tex>\mathrm{p(x)}</tex> — вызов функции <tex>\mathrm{main}</tex> от соответствующего аргумента.

Все входные данные далее можно интерпретировать как строки, поэтому все типы аргументов и возвращаемых значений будут иметь тип '''string'''. Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
'''program string''' p('''string''' y):
'''string''' V('''string''' x, '''string''' y):
...

'''string''' main():
'''return''' V(getSrc(), y)

'''string''' getSrc():
...
Теперь нужно определить функцию <tex>\mathrm{getSrc()}</tex>. Предположим, что внутри <tex>p(y)</tex> мы можем определить функцию <tex>\mathrm{getOtherSrc()}</tex>, состоящую из одного оператора <tex>\mathrm{return}</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.

'''program string''' p('''string''' y):
'''string''' V('''string''' x, '''string''' y):
...

'''string''' main():
'''return''' V(getSrc(), y)

'''string''' getSrc():
'''string''' src = getOtherSrc()
'''return''' ```$src // символ $ перед названием переменной используется для подстановки значения этой переменной в строку
<nowiki>|</nowiki>string getOtherSrc(): // многострочные строки заключаются в ``` и используют <nowiki>|</nowiki> в качестве разделителя
<nowiki>|</nowiki> return $src```

'''string''' getOtherSrc():
...

Теперь <tex>\mathrm{getOtherSrc()}</tex> определяется очевидным образом, и мы получаем '''итоговую версию''' функции <tex>p(y)</tex>:
<code>
'''program string''' p('''string''' y):
'''string''' V('''string''' x, '''string''' y):
...

'''string''' main():
'''return''' V(getSrc(), y)

'''string''' getSrc():
'''string''' src = getOtherSrc()
'''return''' ```$src
<nowiki>|</nowiki>string getOtherSrc():
<nowiki>|</nowiki> return $src```

'''string''' getOtherSrc():
'''return''' ```function p(int y):
<nowiki>|</nowiki> int V(string x, int y):
<nowiki>|</nowiki> ...
<nowiki>|</nowiki>
<nowiki>|</nowiki> int main():
<nowiki>|</nowiki> return V(getSrc(), y)
<nowiki>|</nowiki>
<nowiki>|</nowiki> string getSrc():
<nowiki>|</nowiki> string src = getOtherSrc()
<nowiki>|</nowiki> return \```$src
<nowiki>|</nowiki> <nowiki>|</nowiki>string getOtherSrc():
<nowiki>|</nowiki> <nowiki>|</nowiki> return \$src\```
</code>
}}

Иначе говоря, если рассмотреть <tex>V(x, y)</tex>, как программу, использующую <tex>x</tex> в качестве исходного кода и выполняющую действие над <tex>y</tex>, то теорема о рекурсии показывает, что мы можем написать эквивалентную ей программу <tex>p(y) = V(p, y)</tex>, которая будет использовать собственный исходный код.

Приведем так же альтернативую формулировку теоремы и альтернативное (неконструктивное) доказательство.

==Теорема о неподвижной точке==
Введем на множестве натуральных чисел следующее отношение: <tex>x \equiv y \Leftrightarrow U_x = U_y</tex> и докажем вспомогательную лемму.
{{Определение
|definition = Функция <tex>g</tex> называется '''<tex>\equiv</tex> {{---}} продолжением (<tex>\equiv</tex> {{---}} continuation)''' функции <tex>f</tex>, если для всех таких <tex>x</tex>, что <tex>f(x)</tex> определено, <tex>g(x) \equiv f(x)</tex>.
}}
{{Лемма
|statement= Для всякой вычислимой функции <tex>f</tex> существует вычислимая и всюду определенная функция <tex>g</tex>, являющаяся ее <tex>\equiv</tex> {{---}} продолжением.
|proof= Рассмотрим вычислимую функцию от двух аргументов <tex> V(n, x) = U(f(n), x)</tex>. Так как <tex>V</tex> — вычислимая, то существует вычислимая и всюду определенная функция <tex>s(n)</tex> такая, что: <tex>V(n, x) = U(s(n), x)</tex>.

Покажем, что <tex>s(n)</tex> будет являться <tex>\equiv</tex> {{---}} продолжением функции <tex>f(n)</tex>. Если <tex>f(n)</tex> определено, то <tex>s(n)</tex> вернет другой номер той же вычислимой функции. Если же <tex>f(n)</tex> не определено, то <tex>s(n)</tex> вернет номер нигде не определенной функции.
Таким образом, мы нашли <tex>\equiv</tex> {{---}} продолжение для произвольно взятой вычислимой функции <tex>f</tex>.
}}
{{Теорема
|id=th2
|author=Роджерс
|about=о неподвижной точке / ''Rogers' fixed-point theorem''
|statement= Пусть <tex>U</tex> {{---}} [[Диагональный_метод|универсальная функция]] для класса вычислимых функций одного аргумента, <tex>h</tex> {{---}} всюду определённая [[Вычислимые_функции|вычислимая функция]] одного аргумента. Тогда найдется такое <tex>n</tex>, что <tex>U_n=U_{h(n)}</tex>, то есть <tex>n</tex> и <tex>h(n)</tex> — номера одной функции.
|proof=
Будем доказывать теорему от противного: предположим, что существует всюду определенная вычислимая функция <tex>h</tex>, такая, что <tex>U_n \neq U_{h(n)}</tex> для любого <tex>n</tex>. В терминах введенного нами отношения, это значит, что <tex>h</tex> не имеет <tex>\equiv</tex> {{---}} неподвижных точек.

Рассмотрим некоторую вычислимую функцию, от которой никакая вычислимая функция не может отличаться всюду. Такой будет, например <tex>f(x) = U(x, x)</tex> (действительно, если предположить, что существует вычислимая функция <tex>g(n)</tex>, всюду отличная от <tex>f(n) = U(n, n)</tex>, то нарушается определение универсальной функции.)

Согласно доказанной нами лемме, существует вычислимая и всюду определенная функция <tex>g(x)</tex>, являющаяся <tex>\equiv</tex> {{---}} продолжением функции <tex>f(x)</tex>. Давайте зададим функцию <tex>t(x)</tex> следующим образом: <tex>t(x) = h(g(x))</tex>, где <tex>h(x)</tex> — искомая всюду определенная, вычислимая функция, не имеющая <tex>\equiv</tex> {{---}} неподвижных точек. Тогда <tex>t(x)</tex> всюду отличается от <tex>f(x)</tex> (в силу того, что <tex>h(x)</tex> не имеет неподвижных точек.) Получили противоречие, из чего следует, что такой функции <tex>h</tex> не существует.
}}

{{Утверждение
|id=идентификатор (необязательно), пример: proposalF.
|statement = <tex> \exists n : W_n = \{n\} </tex>, где <tex> W_n </tex> {{---}} множество слов, допускаемых программой с номером <tex> n </tex>.
|proof=
По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы.
Напишем такую программу:
<code>
<tex>p(q){:}</tex>
'''if''' <tex>p. \mathrm{getSrc()}</tex> == <tex>q. \mathrm{getSrc()}</tex>
'''return''' 1
'''else'''
'''while''' ''true''
</code>
Программа <tex> p </tex> знает свой код, что то же самое, что и знает свой номер. Как видно из её кода, она допускает только одно число {{---}} свой номер.
}}

==Пример использования теоремы о рекурсии в доказательстве о неразрешимости языка==
Используя теорему о рекурсии, приведём простое доказательство неразрешимости языка <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex>.
{{Лемма
|id=st2
|statement= Язык <tex>L=\{p \mid p(\varepsilon)=\perp\}</tex> неразрешим.
|proof=
Предположим обратное, тогда существует программа <tex>r</tex> разрещающая <tex>L</tex>.
Рассмотрим следущую программу:
<code>
<tex>p(x){:}</tex>
'''if''' r(getSrc())
'''return''' 1
'''while''' ''true''
</code>
Пусть <tex>p(\epsilon)=\perp</tex>. Тогда условие <tex>r(p)</tex> выполняется и <tex>p(\epsilon)=1</tex>. Противоречие. Если <tex>p(\epsilon) \ne \perp</tex>, то <tex>r(p)</tex> не выполняется и <tex>p(\epsilon)=\perp</tex>. Противоречие.
}}

==См. также==
*[[Участник:Shersh/Теорема_о_рекурсии]]

==Источники информации==
* [[wikipedia:Kleene's_recursion_theorem | Wikipedia {{---}} Kleene's recursion theorem]]
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции''' — М.: МЦНМО, 1999 - С. 176
* ''Kleene, Stephen'' '''On notation for ordinal numbers''' - The Journal of Symbolic Logic, 1938 - С. 150-155

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

Обход в ширину

2018-11-08T14:24:10Z

Arimon:

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==
[[Image: Graph-BFS.gif|thumb|240px|Алгоритм BFS 
посещенные вершины ]]

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==
ш-
Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й <tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

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

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину, цвета вершин]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-08T14:16:56Z

Arimon:

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==
[[Image: Graph-BFS.gif|thumb|240px|Алгоритм BFS 
посещенные вершины ]]

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

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

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину, цвета вершин]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Файл:Graph-BFS.gif

2018-11-08T14:10:48Z

Arimon: Визуализация BFS

Визуализация BFS

Обход в ширину

2018-11-08T14:02:02Z

Arimon:

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до <tex> w </tex> найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

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

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. После этого добавления, дополнительный введенный инвариант в доказательстве [[#Корректность | расположения элементов в деке в порядке неубывания]] продолжает выполняться, поэтому порядок в деке сохраняется. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину, цвета вершин]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-06T16:15:54Z

Arimon: /* См. также */

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

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

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину, цвета вершин]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-06T16:15:09Z

Arimon: Добавлено см. также

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

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

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

== См. также ==
* [[Обход в глубину]]
* [[Алгоритм Дейкстры]]
* [[Теория графов]]

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-06T16:11:07Z

Arimon: Исправления, переформулировка 0-1 BFS

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага алгоритма элементы в очереди неубывают.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

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

Вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque). Если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, то будем добавлять вершину в начало, а иначе в конец. И, соответственно, релаксируем расстояние до всех смежных вершин и, при успешной релаксации, добавляем их в дек.

Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1 \ldots k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2 \ldots u_{m - 1}v</tex> (где <tex>u_1 \ldots u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex> G </tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-06T15:58:38Z

Arimon: переформулировано доказательство ут. 1

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

Введем дополнительный инвариант: у любых двух вершин из очереди, расстояние до <tex> s </tex> отличается не более чем на <tex> 1 </tex>.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex>.

'''Переход''': пусть после <tex> i-й </tex> итерации в очереди <tex> a + 1 </tex> вершин с расстоянием <tex> x </tex> и <tex> b </tex> вершин с расстоянием <tex> x + 1 </tex>.

Рассмотрим <tex> i-ю </tex> итерацию. Из очереди достаем вершину <tex> v </tex>, с расстоянием <tex> x </tex>. Пусть у v есть <tex>r </tex> непосещенных смежных вершин. Тогда, после их добавления, в очереди находится <tex> a </tex> вершин с расстоянием <tex> x </tex> и, после них, <tex> b + r </tex> вершин с расстоянием <tex> x + 1 </tex>.

Оба инварианта сохранились, <tex> \Rightarrow </tex> после любого шага в очереди элементы неубывают
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (u, v) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

== Вариации алгоритма ==
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque), а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex>G</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-06T15:24:30Z

Arimon: /* Реализация */ немного поправлен псевдокод

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием <tex> 0 </tex>, утверждение верно.

'''Переход''': пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex> (возможно, <tex> 0 </tex>) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием <tex> k + 1 </tex>, что соответствует нашему инварианту.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' v: (v, u) '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

== Вариации алгоритма ==
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque), а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex>G</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Обход в ширину

2018-11-06T15:19:35Z

Arimon: Переформатировано описание

'''Обход в ширину''' (Поиск в ширину, англ. ''BFS'', ''Breadth-first search'') — один из простейших алгоритмов обхода [[Основные определения теории графов|графа]], являющийся основой для многих важных алгоритмов для работы с графами.

== Описание алгоритма ==

Пусть задан невзвешенный ориентированный граф <tex> G = (V, E) </tex>, в котором выделена исходная вершина <tex>s</tex>. Требуется найти длину кратчайшего пути (если таковой имеется) от одной заданной вершины до другой. Частным случаем указанного графа является невзвешенный неориентированный граф, т.е. граф, в котором для каждого ребра найдется обратное, соединяющее те же вершины в другом направлении.

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

== Анализ времени работы ==

Оценим время работы для входного графа <tex>G = (V, E)</tex>, где множество ребер <tex> E </tex> представлено списком смежности. В очередь добавляются только непосещенные вершины, поэтому каждая вершина посещается не более одного раза. Операции внесения в очередь и удаления из нее требуют <tex> O(1) </tex> времени, так что общее время работы с очередью составляет <tex> O(|V|) </tex> операций. Для каждой вершины <tex> v </tex> рассматривается не более <tex> \mathrm{deg}(v) </tex> ребер, инцидентных ей. Так как <tex> \sum\limits_{v \in V} \mathrm{deg}(v) = 2|E| </tex>, то время, используемое на работу с ребрами, составляет <tex> O(|E|) </tex>. Поэтому общее время работы алгоритма поиска в ширину — <tex> O(|V| + |E|) </tex>.

== Корректность ==

{{Утверждение
|statement=
В очереди поиска в ширину расстояние вершин до <tex>s</tex> монотонно неубывает.
|proof=
Докажем это утверждение индукцией по числу выполненных алгоритмом шагов.

'''База''': изначально очередь содержит только одну вершину <tex> s </tex> с расстоянием <tex> 0 </tex>, утверждение верно.

'''Переход''': пусть после <tex> l </tex>-ого шага алгоритма очередь содержит <tex> p </tex> вершин с расстоянием <tex> k </tex> и <tex> q </tex> вершин с расстоянием <tex> k + 1 </tex>. Тогда на <tex> l+1 </tex>-ом шаге мы извлечем из очереди одну вершину и добавим в нее все непосещенные(<tex> r </tex> вершин), связанные с ней; расстояние до них, очевидно, будет равно <tex> k + 1 </tex>. У нас останется <tex> p - 1 </tex> (возможно, <tex> 0 </tex>) вершин с расстоянием <tex> k </tex> и <tex> q + r </tex> вершин с расстоянием <tex> k + 1 </tex>, что соответствует нашему инварианту.
}}

{{Теорема
|statement=
Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.
|proof=
Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от <tex> s </tex> найдены некорректно, ту, настоящее расстояние до которой минимально. Пусть это вершина <tex> u </tex>, и она имеет своим предком в дереве обхода в ширину <tex> v </tex>, а предок в кратчайшем пути до <tex> u </tex> — вершина <tex> w </tex>.

Так как <tex> w </tex> — предок <tex> u </tex> в кратчайшем пути, то <tex> \rho(s, u) = \rho(s, w) + 1 > \rho(s, w) </tex>, и расстояние до w найдено верно, <tex> \rho(s, w) = d[w] </tex>. Значит, <tex> \rho(s, u) = d[w] + 1 </tex>.

Так как <tex> v </tex> — предок <tex> u </tex> в дереве обхода в ширину, то <tex> d[u] = d[v] + 1 </tex>.

Расстояние до <tex> u </tex> найдено некорректно, поэтому <tex> \rho(s, u) < d[u] </tex>. Подставляя сюда два последних равенства, получаем <tex> d[w] + 1 < d[v] + 1 </tex>, то есть, <tex> d[w] < d[v] </tex>. Из ранее доказанной леммы следует, что в этом случае вершина <tex> w </tex> попала в очередь и была обработана раньше, чем <tex> v </tex>. Но она соединена с <tex> u </tex>, значит, <tex> v </tex> не может быть предком <tex> u </tex> в дереве обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.
}}

== Дерево обхода в ширину ==

Поиск в ширину также может построить [[Дерево, эквивалентные определения|дерево]] поиска в ширину. Изначально оно состоит из одного корня <tex> s </tex>. Когда мы добавляем непосещенную вершину в очередь, то добавляем ее и ребро, по которому мы до нее дошли, в дерево. Поскольку каждая вершина может быть посещена не более одного раза, она имеет не более одного родителя. После окончания работы алгоритма для каждой достижимой из <tex> s </tex> вершины <tex> t </tex> путь в дереве поиска в ширину соответствует кратчайшему пути от <tex> s </tex> до <tex> t </tex> в <tex> G </tex>.

== Реализация ==

Предложенная ниже функция возвращает кратчайшее расстояние между двумя вершинами.
*<tex> \mathtt{source} </tex> — исходная вершина
*<tex> \mathtt{destination} </tex> — конечная вершина
*<tex> \mathtt{G} </tex> — граф, состоящий из списка вершин <tex> \mathtt{V} </tex> и списка смежности <tex> \mathtt{E} </tex>. Вершины нумеруются целыми числами.
*<tex> \mathtt{Q} </tex> — очередь.
*В поле <tex> \mathtt{d[u]} </tex> хранится расстояние от <tex> \mathtt{source} </tex> до <tex> \mathtt{u} </tex>.

'''int''' '''BFS'''(G: (V, E), source: '''int''', destination: '''int'''):
d = '''int'''[|V|]
'''fill'''(d, <tex> \infty </tex>)
d[source] = 0
Q = <tex> \varnothing </tex>
Q.push(source)
'''while''' Q <tex> \ne \varnothing </tex>
u = Q.pop()
'''for''' vu '''in''' E
'''if''' d[v] == <tex> \infty </tex>
d[v] = d[u] + 1
Q.push(v)
'''return''' d[destination]

Если требуется найти расстояние лишь между двумя вершинами, из функции можно выйти, как только будет установлено значение <tex> \mathtt{d[destination]} </tex>.
Еще одна оптимизация может быть проведена при помощи метода [[Meet-in-the-middle#Задача о нахождении кратчайшего расстояния между двумя вершинами в графе|meet-in-the-middle]].

== Вариации алгоритма ==
=== 0-1 BFS ===
Пусть в графе разрешены ребра веса <tex> 0 </tex> и <tex> 1 </tex>, необходимо найти кратчайший путь между двумя вершинами. Для решения данной задачи модифицируем приведенный выше алгоритм следующим образом: вместо очереди будем использовать [[Персистентный_дек|дек]] (или можно даже steque), а вместо добавления вершины в конец будем добавлять вершину в начало, если рассматриваемое ее ребро имеет вес <tex> 0 </tex>, а иначе в конец. Соответственно релаксируем расстояние до вершины. Таким образом, в начале дека всегда будет вершина, расстояние до которой меньше либо равно расстоянию до остальных вершин дека, и инвариант [[#Корректность | расположения элементов в деке в порядке неубывания]] сохраняется. Значит, алгоритм корректен на том же основании, что и обычный BFS. Очевидно, что каждая вершина войдет в дек не более двух раз, значит, асимптотика у данного алгоритма та же, что и у обычного BFS.

=== 1-k BFS ===
Пусть в графе разрешены ребра целочисленного веса из отрезка <tex>1..k</tex>, необходимо найти кратчайший путь между двумя вершинами. Представим ребро <tex>uv</tex> веса <tex>m</tex> как последовательность ребер <tex>uu_1u_2..u_{m - 1}v</tex> (где <tex>u_1..u_{m - 1}</tex> — новые вершины). Применим данную операцию ко всем ребрам графа <tex>G</tex>. Получим граф, состоящий (в худшем случае) из <tex>k|E|</tex> ребер и <tex>|V| + (k - 1)|E|</tex> вершин. Для нахождения кратчайшего пути следует запустить BFS на новом графе. Данный алгоритм будет иметь асимптотику <tex> O(|V| + k|E|) </tex>.

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

* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2007. — с. 459. — ISBN 5-8489-0857-4
* [http://e-maxx.ru/algo/bfs MAXimal :: algo :: Поиск в ширину]
* [[wikipedia:en:Breadth-first_search| Wikipedia {{---}} Breadth-first search]]
* [[wikipedia:ru:Поиск_в_ширину| Wikipedia {{---}} Поиск в ширину]]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-general/bfs-2002 Визуализатор алгоритма]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах]]

Хроматический многочлен

2018-10-31T16:50:23Z

Arimon: /* Хроматический многочлен колеса */

{{Определение
|definition=Пусть дан фиксированный граф <tex>G</tex> и фиксированное число красок <tex>x</tex>. Количество способов правильной <tex>x</tex> — [[Раскраска графа|раскраски графа]] <tex>G</tex> называется '''хроматическим многочленом''' (англ. ''chromatic polynomial''). Обозначение: <tex>P(G,x)</tex>.
}}

== Рекуррентные формулы для хроматических многочленов ==
{{Определение
|definition='''Стягивание ребра''' (англ. ''edge contraction'') — замена концов ребра одной вершиной, соседями новой вершины становятся соседи этих концов. Будем обозначать за <tex>G/uv</tex> граф, полученный из графа <tex>G</tex> стягиванием ребра <tex>uv</tex>.}}
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> — несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G\cup uv</tex>, а <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)+P(G_2,x)</tex>.
|proof=
Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>uv</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>.
}}
'''Замечание:'''
Если к некоторому произвольному графу добавлять ребра последовательно, не меняя его вершин, то на каком-то шаге мы получим полный граф. Аналогично мы получим полный граф, если в произвольном графе уменьшим число вершин, путем их отождествления, не меняя числа ребер.

'''Следствие:'''
Хроматический многочлен любого графа <tex>G</tex> равен сумме хроматических многочленов некоторого числа полных графов, число вершин в которых не больше, чем в графе <tex>G</tex>.

{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> — смежные вершины графа <tex>G</tex>. Если <tex>G_1=G\backslash uv</tex> и <tex>G_2=G/uv</tex>, то <tex>P(G,x)=P(G_1,x)-P(G_2,x)</tex>.
|proof=
Следует из предыдущей теоремы.
}}

== Примеры хроматических многочленов ==
=== Хроматический многочлен полного графа ===
<tex>P(K_{n},x)=x(x-1)...(x-n+1)=x^{\underline{n}}</tex>, так как первую вершину полного графа <tex>K_{n}</tex> можно окрасить в любой из <tex>x</tex> цветов, вторую — в любой из оставшихся <tex>x-1</tex> цветов и т. д. Очевидно, что если <tex>x</tex> меньше <tex>n</tex>, то и многочлен равен <tex>0</tex>, так как один из его множителей <tex>0</tex>.

=== Хроматический многочлен нуль-графа ===
{{Определение
|definition='''Нуль-граф''' (пустой граф, вполне несвязный граф; англ. ''null graph'', ''empty graph'', ''edgeless graph'') — регулярный граф степени <tex>0</tex>, т.е. граф без рёбер.}}
<tex>P(O_{n},x)=x^{n}</tex>, так как каждую из <tex>n</tex> вершин нулевого графа <tex>O_{n}</tex> можно независимо окрасить в любой из <tex>x</tex> цветов. 
'''Примечание:''' Нулевой граф <tex>O_{n}</tex> также можно обозначать <tex>\overline{K_{n}}</tex> (дополнительный граф для полного графа <tex>K_{n}</tex>).

=== Хроматический многочлен простой цепи ===
Пусть <tex>T_n</tex> — простая цепь, состоящая из <tex>n</tex> вершин. Рассмотрим процесс раскраски простой цепи: первую вершину можно покрасить в один из <tex>x</tex> цветов, вторую и последующие в один из <tex>x - 1</tex> цветов (т.е. так, чтобы цвет не совпадал с предыдущей вершиной). Тогда <tex>P(T_n, x) = x(x - 1) ^ {n - 1}</tex>.

=== Хроматический многочлен цикла ===
{{Теорема
|about=
хроматический многочлен цикла
|statement=
Пусть <tex>C_n</tex> — цикл длины <tex>n</tex>. Тогда хроматический многочлен цикла <tex>P(C_n, x) = (x - 1)^n + (-1)^n(x - 1)</tex>.
|proof=
Докажем по индукции по количеству вершин. 
'''База индукции''': рассмотрим случай <tex>n = 3</tex>: <tex>P(C_3, x) = x(x - 1)(x - 2) = (x^3 - 3x^2 + 3x - 1) - (x - 1) = (x - 1)^3 + (-1)^3(x - 1)</tex>, что удовлетворяет формулировке теоремы. 
'''Индукционный переход''': пусть <tex>P(C_k, x) = (x - 1)^k + (-1)^k(x - 1)</tex>. 
Рассмотрим случай <tex>n = k + 1</tex>. По теореме о [[#Рекуррентные_формулы_для_хроматических_многочленов|рекуррентной формуле для хроматических многочленов]]: <tex>P(C_{k + 1}, x ) = P(C_{k + 1} \setminus e, x) - P(C_{k + 1} / e, x)</tex> (где <tex>e</tex> — любое ребро <tex>C_{k + 1}</tex>).
Заметим, что граф <tex>C_{k + 1} / e</tex> изоморфен <tex>C_k</tex>, а граф <tex>C_{k + 1} \setminus e</tex> является [[#Хроматический_многочлен_простой_цепи|простой цепью]].
Тогда <tex>P(C_{k + 1}, x)=P(T_{k + 1}, x)-P(C_k, x)=x(x-1)^k-(x-1)^k-(-1)^k(x-1)=</tex> <tex>(x-1)^{k+1}+(-1)^{k+1}(x-1)</tex>.
}}

=== Хроматический многочлен колеса ===
Пусть <tex>W_n</tex> — [[Двойственный_граф_планарного_графа|колесо]] с <tex>n</tex> вершинами. Выбрав и зафиксировав один из <tex>x</tex> цветов на вершине, связнной со всеми остальными, имеем <tex> P(C_{n - 1}, x - 1) </tex> вариантов раскраски оставшегося графа. Тогда хроматический многочлен колеса <tex>P_{W_n}(x) = x \cdot P_{C_{n - 1}}(x - 1) = x((x - 2)^{(n - 1)} - (-1)^{(n - 1)}(x - 2))</tex>.

=== Хроматический многочлен дерева ===
{{Теорема
|about=
хроматический многочлен дерева
|statement=
Граф <tex>G</tex> с <tex>n</tex> вершинами является деревом тогда и только тогда, когда <tex>P(G,x)=x(x-1)^{n-1}</tex>.
|proof=
<tex>\Rightarrow</tex> 
Сначала покажем, что хроматический многочлен любого дерева <tex>T</tex> с <tex>n</tex> вершинами есть <tex>x(x-1)^{n-1}</tex>.
Доказательство индукцией по числу <tex>n</tex>. Для <tex>n=1</tex> и <tex>n=2</tex> результат очевиден. Предположим, что <tex>P(T',x)=x(x-1)^{n-2}</tex> для любого дерева <tex>T'</tex> с количеством вершин равным <tex>n-1</tex>. Пусть <tex>uv</tex> — ребро дерева <tex>T</tex>, такое что <tex>v</tex> является висячей вершиной. Хроматический многочлен дерева <tex>T</tex> без ребра <tex>uv</tex> равен <tex>P(T/uv,x)=x(x-1)^{n-2}</tex> по нашему предположению. Вершину <tex>v</tex> можно окрасить <tex>x-1</tex> способом, так как её цвет должен только лишь отличаться от цвета вершины <tex>u</tex>. Итого: <tex>P(T,x)=(x-1)P(T/uv,x)=x(x-1)^{n-1}</tex>. 
<tex>\Leftarrow</tex> 
Обратно, пусть <tex>G</tex> — граф, у которого <tex>P(G,x)=x(x-1)^{n-1}</tex>. Тогда верны два следующих утверждения:
<ol>
<li>Граф <tex>G</tex> связен, потому что если было бы две компоненты связности (или больше), то <tex>P(G,x)</tex> делился бы на <tex>x^2</tex> без остатка. </li>
<li>В графе <tex>G</tex> количество рёбер равно <tex>n-1</tex>, так как по одной из теорем о коэффициентах хроматического многочлена ([[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена]], теорема 4), количество рёбер в графе соответствует коэффициенту при <tex>x^{n-1}</tex>, взятому со знаком минус. В нашем случае, этот коэффициент удобно искать, используя бином Ньютона: 
<tex>{P(G,x)=x(x-1)^{n-1}=x\left(x^{n-1}-{n-1 \choose 1}x^{n-2}+{n-1 \choose 2}x^{n-3}-...+(-1)^{n-1}\right)=x^{n}-(n-1)x^{n-1}+...+(-1)^{n-1}x}</tex> </li>
</ol>
Из этих двух утверждений (связность и <tex>n-1</tex> ребро) следует, что граф <tex>G</tex> является деревом (см. [[Дерево, эквивалентные определения]], утверждения 1 и 3).
}}

== Коэффициенты хроматического многочлена ==
{{Теорема
|about=
1
|statement=
Свободный член хроматического многочлена равен <tex>0</tex>.
|proof=
По определению хроматического многочлена графа <tex>G</tex>, его значение в точке <tex>x</tex> равно количеству способов раскрасить вершины <tex>G</tex> правильным образом в <tex>x</tex> цветов. Количество способов раскрасить граф в <tex>0</tex> цветов равно <tex>0</tex>. То есть <tex>P(G,0)=0</tex>. Из этого следует, что <tex>P(G,x)</tex> кратен <tex>x</tex>, следовательно его свободный член равен <tex>0</tex>.
}}

{{Теорема
|about=
2
|statement=
Старший коэффициент хроматического многочлена равен <tex>1</tex>.
|proof=
Воспользуемся рекуррентной формулой: 
<tex>P(G,x) = P(G_{1},x) + P(G_{2},x)</tex>, 
где <tex>G_{1}</tex> — граф, полученный из <tex>G</tex> добавлением отсутствующего в <tex>G</tex> ребра <tex>uv</tex>, а <tex>G_{2}</tex> — граф, полученный из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex> в одну и удалением возникших при этом кратных ребер.
Применяя рекуррентную формулу повторно, хроматический полином можно представить в виде суммы хроматических полиномов полных графов, то есть: 
<tex>P(G,x) = {P(K_{n},x) + a_{1}P(K_{n-1},x) + a_{2}P(K_{n-2},x) + \ldots = x^{\underline{n}} + a_{1}x^{\underline{n-1}}+a_{2}x^{\underline{n-2}}+\ldots}</tex> 
Из этой формулы видно, что хроматический многочлен имеет старший коэффициент, равный <tex>1</tex>.
}}

{{Теорема
|about=
3
|statement=
Коэффициенты хроматического многочлена составляют знакопеременную последовательность.
|proof=
Индукция по количеству вершин. 
'''База индукции:''' 
Теорема верна для графа <tex>G</tex> из одной вершины, потому что <tex>P(G,x)=x</tex>. 
'''Индукционный переход''' (<tex>n \to n+1)</tex>: 
Предположим, что теорема верна для всех графов на <tex>n</tex> вершинах. Рассмотрим графы на <tex>n+1</tex> вершине.
Индукционный переход будем доказывать индукцией по количеству ребер графа <tex>G</tex>. Если <tex>G</tex> не содержит ребер, то есть <tex>G</tex> является <tex>O_{n+1}</tex>, то его хроматический многочлен <tex>P(G,x)=x^{n+1}</tex> обладает доказываемым свойством. Теперь предположим, что для всех <tex>(n+1,m)</tex>-графов теорема верна. Возьмем <tex>(n+1,m+1)</tex>-граф <tex>G_{1}</tex> и его ребро <tex>uv</tex>. Обозначим за <tex>G</tex> граф, полученный из <tex>G_{1}</tex> удалением ребра <tex>uv</tex> (<tex>G=G_{1}-uv</tex>), а за <tex>G_{2}</tex> — граф, полученный из <tex>G_{1}</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>. Тогда из рекуррентной формулы следует: 
<tex>P(G_{1},x)=P(G,x)-P(G_{2},x)</tex>.
Так как <tex>G</tex> — <tex>(n+1,m)</tex>-граф, а в <tex>G_{2}</tex> — <tex>n</tex> вершин, то для <tex>G</tex> и <tex>G_{2}</tex> теорема верна: 
<tex>{P(G,x)=x^{n+1}-a_{1}x^{n}+a_{2}x^{n-1}-a_{3}x^{n-2}+\ldots}</tex> , 
<tex>{P(G_{2},x)=x^{n}-b_{1}x^{n-1}+b_{2}x^{n-2}+\ldots}</tex> , 
где <tex>a_{1}</tex>, <tex>a_{2}</tex> … <tex>a_{n+1}</tex>, <tex>b_{1}</tex>, <tex>b_{2}</tex> … <tex>b_{n}</tex> — некоторые неотрицательные целые числа. Из этих равенств получаем: 
<tex>P(G_{1},x)=x^{n+1}-(a_{1}+1)x^{n}+(a_{2}+b_{1})x^{n-1}+\ldots</tex>.
Видно, что в этом полученном полиноме коэффициенты составляют знакопеременную последовательность.
}}

{{Теорема
|about=
4
|statement=
Второй коэффициент хроматического многочлена равен по модулю количеству ребер графа.
|proof=
Из доказательства '''Теоремы (3)''' видно, что при увеличении количества ребер графа на <tex>1</tex>, второй коэффициент также увеличивается на <tex>1</tex>. Так как для пустого графа второй коэффициент равен <tex>0</tex>, то утверждение верно для любого графа.
}}

== Источники информации ==
* Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. - СПб.: Издательство "Лань", 2010. - 368 с.: ил. - (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
* Харари Ф. — Теория графов: Изд. 4-е. - М.: Книжный дом "ЛИБРОКОМ", 2009. - 296 с. ISBN 978-5-397-00622-4
* [[wikipedia:en:Chromatic_polynomial| Wikipedia {{---}} Chromatic polynomial]]
* [[wikipedia:ru:Хроматическое_число#Хроматический_многочлен| Wikipedia {{---}} Хроматический многочлен]]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]

Использование обхода в глубину для поиска точек сочленения

2018-10-19T21:07:17Z

Arimon: /* Описание алгоритма */

{{Задача
|definition=Дан [[Отношение связности, компоненты связности|связный]] [[Основные определения теории графов|неориентированный граф]] <tex> G </tex>. Найти все [[Точка сочленения, эквивалентные определения|точки сочленения]] в <tex> G </tex> за время <tex> O(|V| + |E|).</tex>
}}

== Алгоритм ==

=== Описание алгоритма ===
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины графа; обозначим её через <tex>root</tex>. Заметим следующий факт:

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

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

[[Файл:Joint_point_2_rsz.png‎|280px|thumb|left| Красным цветом обозначены точки сочленения Синим — ребра по которым идет DFS]]
Пусть <tex>tin[u]</tex> — время входа поиска в глубину в вершину <tex>u</tex>. Через <tex>up[u]</tex> обозначим минимум из времени захода в саму вершину <tex>tin[u]</tex>, времен захода в каждую из вершин <tex>p</tex>, являющуюся концом некоторого обратного ребра <tex>(u,p)</tex>, а также из всех значений <tex>up[v]</tex> для каждой вершины <tex>v</tex>, являющейся непосредственным сыном <tex>u</tex> в дереве поиска.

Тогда из вершины <tex>u</tex> или её потомка есть обратное ребро в её предка <tex>\Leftrightarrow \exists</tex> такой сын <tex>v</tex>, что <tex>up[v] \geqslant tin[u]</tex>.

Таким образом, если для текущей вершины <tex>u \ne root </tex> существует непосредственный сын <tex>v</tex>: <tex>up[v] \geqslant tin[u]</tex>, то вершина <tex>u</tex> является точкой сочленения, в противном случае она точкой сочленения не является.

 

=== Псевдокод ===

'''function''' findCutPoints(G[n]: '''Graph'''): // функция принимает граф G с количеством вершин n и выполняет поиск точек сочленения во всем графе 
visited = array[n, ''false'']

'''function''' dfs(v: '''int''', p: '''int'''):
time = time + 1
up[v] = tin[v] = time
visited[v] = ''true''
count = 0
'''for''' u: (v, u) '''in''' G
'''if''' u == p
'''continue'''
'''if''' visited[u]
up[v] = min(up[v], tin[u])
'''else'''
dfs(u, v)
count = count + 1
up[v] = min(up[v], up[u])
'''if''' p != -1 '''and''' up[u] >= tin[v]
v — cutpoint
'''if''' p == -1 '''and''' count >= 2
v — cutpoint

'''for''' i = 1 '''to''' n
'''if''' '''not''' visited[i]
dfs(i, -1)

=== Доказательство корректности ===
{{Теорема
|statement=
Пусть <tex>T</tex> — дерево [[Обход в глубину, цвета вершин|обхода в глубину]], <tex>root</tex> — корень <tex>T</tex>.
* Вершина <tex>u \ne root</tex> — точка сочленения <tex>\Leftrightarrow \exists v \in T</tex> — сын <tex>u</tex> : из <tex>v</tex> или любого потомка вершины <tex>v</tex> нет обратного ребра в предка вершины <tex>u</tex>.
* <tex>root</tex> — точка сочленения <tex>\Leftrightarrow root</tex> имеет хотя бы двух сыновей в дереве поиска в глубину.
|proof=
[[Файл:Joint_point_1.png|48px |thumb|‎ | Рисунок к <tex>\Leftarrow</tex>]]
<tex>\Leftarrow</tex>

#Удалим <tex>u</tex> из <tex>G</tex>. Докажем, что не существует пути из <tex>v</tex> в любого предка вершины <tex>u</tex>. Пусть это не так. Тогда <tex>\exists x \in T</tex> — предок <tex>u</tex> : <tex>\exists</tex> путь из <tex>v</tex> в <tex>x</tex> в <tex>G \backslash u</tex>. Пусть <tex>w</tex> — предпоследняя вершина на этом пути, <tex>w</tex> — потомок <tex>v</tex>. <tex>(w, x)</tex> — не ребро дерева <tex>T</tex>(в силу единственности пути в дереве) <tex>\Rightarrow (w, x)</tex> — обратное ребро, что противоречит условию.
#Пусть у <tex>root</tex> хотя бы два сына. Тогда при удалении <tex>root</tex> не существует пути между его поддеревьями, так как не существует перекрестных ребер <tex>\Rightarrow root</tex> — точка сочленения.

<tex>\Rightarrow</tex>
#Докажем что из отрицания второго утверждения следует отрицание первого. Обозначим через <tex>G'</tex> граф, состоящий из вершин, не являющихся потомками <tex>u</tex>. Удалим вершину <tex>u</tex>. Очевидно, что граф <tex>G'</tex> и все поддеревья вершины <tex>u</tex> останутся связными, кроме того из каждого поддерева есть ребро в <tex>G' \Rightarrow G \backslash u</tex> — связный <tex>\Rightarrow u</tex> — не точка сочленения.
#Пусть <tex>root</tex> — точка сочленения и у него есть только один сын. Тогда при удалении <tex>root</tex> остается дерево с корнем в его сыне, содержащее все остальные вершины графа, то есть оставшийся граф связен — противоречие с тем, что <tex>root</tex> — точка сочленения.
}}

 

=== Асимптотика ===
Оценим время работы алгоритма. Процедура <tex>\mathrm{dfs}</tex> вызывается от каждой вершины не более одного раза, а внутри процедуры рассматриваются все такие [[Основные определения теории графов|ребра]] <tex>\{e\ |\ \mathrm{begin(e)} = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма оценивается как <tex>O(V+E)</tex>. Такое же, как у [[Обход в глубину, цвета вершин|обхода в глубину]].

== См. также ==
* [[Использование обхода в глубину для поиска мостов]]
* [[Обход в глубину, цвета вершин]]
* [[Обход в ширину]]

== Источники информации==
* Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Лань, 2010. — 368 с. — ISBN 978-5-8114-1068-2
* [http://e-maxx.ru/algo/cutpoints MAXimal :: algo :: Поиск точек сочленения]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Расчёт вероятности поглощения в состоянии

2018-06-24T13:28:28Z

Arimon: /* Псевдокод */ исправлен псевдокод

[[Марковская цепь#Поглощающая цепь| Поглощающее состояние]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.

Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n], position: '''int'''[n]):
'''float''' probability[n]

'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob

'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-24T13:15:33Z

Arimon: /* Псевдокод */ добавлена инициализация Q и R

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Введем <tex>\mathtt{transition}:</tex> <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' '''jump''' i '''in''' transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0
'''float''' Q[n][n]
'''float''' R[n][n]
'''int''' position[n]

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' '''jump''' i '''in''' transition
'''if''' absorbing[i.to]
'''if''' !absorbing[i.from]
R[position[i.from]][position[i.to]] = i.prob
'''else'''
Q[position[i.from]][position[i.to]] = i.prob

'''return''' Q

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-24T12:58:25Z

Arimon: /* Псевдокод */ исправлен псевдокод

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Введем <tex>\mathtt{transition}:</tex> <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' '''jump''' i '''in''' transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return''' Q

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T21:30:34Z

Arimon: /* Псевдокод */ косметические изменение

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Введем <tex>\mathtt{transition}:</tex> <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' '''jump''' i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return''' Q

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-23T21:22:49Z

Arimon: добавлена ссылка

[[Марковская цепь#Поглощающая цепь| Поглощающее состояние]] — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.

Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n]):
'''float''' probability[n]

'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob

'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Расчёт вероятности поглощения в состоянии

2018-06-23T21:00:12Z

Arimon: /* Псевдокод */ исправлен псевдокод

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n]):
'''float''' probability[n]

'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob

'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Расчёт вероятности поглощения в состоянии

2018-06-23T20:59:21Z

Arimon: /* Псевдокод */ косметические изменение

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=\left(\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1\right)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Расчёт вероятности поглощения в состоянии

2018-06-23T20:55:15Z

Arimon: /* Псевдокод */

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=((\sum\limits_{k=1}^{n} \mathtt{G}[k][j]+1)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:49:29Z

Arimon: /* Подсчет количества поглощащих состояний */ косметические изменения

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Введем <tex>\mathtt{transition}:</tex> <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' '''jump''' i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:46:37Z

Arimon: /* Псевдокод */ исправлен псевдокод

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Введем <tex>\mathtt{transition}</tex>: <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' '''jump''' i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:45:42Z

Arimon: Косметические изменения

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Введем <tex>\mathtt{transition}</tex>: <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' jump i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:42:47Z

Arimon: Косметические изменения

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Пусть <tex>\mathtt{transition}</tex> — <tex> \mathtt{jump}[\mathtt{m}] </tex>, где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' jump i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:41:24Z

Arimon: Косметические изменения

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex>.

Пусть <tex>\mathtt{transition}</tex> — <tex> \mathtt{jump}[\mathtt{m}], где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.

Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' jump i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:39:51Z

Arimon: Косметические изменения

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex> jump.

Пусть <tex>\mathtt{transition}</tex> — <tex> \mathtt{jump}[\mathtt{m}], где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' jump i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T20:37:53Z

Arimon: Косметические изменения, введена структура jump, исправлен псевдокод

==Подсчет количества поглощащих состояний==
Для хранения переходов марковской цепи создадим структуру <tex> \mathtt{jump}</tex> jump.
Пусть <tex>\mathtt{transition}</tex> — <tex> \mathtt{jump}[\mathtt{m}], где <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.prob}</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.from}</tex> в <tex>\mathtt{transition}[\mathtt{i}]\mathtt{.to}</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}]\mathtt{.prob} = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''jump'''[m]):
'''boolean''' absorbing[n]

'''for''' jump i: transition
absorbing[i.from] = i.from == i.to '''and''' i.prob == 1

'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''float[][]''' buildTransitionMatrix(absorbing: '''boolean'''[n], transition: '''jump'''[m]):
'''int''' count_q = 0
'''int''' count_r = 0

'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++

'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i].to]
'''if''' !absorbing[transition[i].from]
R[position[transition[i].from]][position[transition[i].to]] = transition[i].prob
'''else'''
Q[position[transition[i].from]][position[transition[i].to]] = transition[i].prob

'''return Q'''

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-23T14:21:24Z

Arimon: /* Псевдокод */ изменен тип transition

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''float'''[m][3]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
absorbing[transition[i][0]] = transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix(absorbing: '''boolean'''[n]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-23T14:20:28Z

Arimon: Косметические изменения

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>\mathtt{G}</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> \mathtt{G} = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>\mathtt{G}</tex> определяется их суммированием по всем длинам пути из i в j: <tex>\mathtt{G} = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=((\sum\limits_{k=1}^{n} G[k][j]+1)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position}[\mathtt{i}]</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability}[\mathtt{i}]</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing}[\mathtt{i}]</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T22:15:35Z

Arimon: /* Псевдокод */ исправлен псевдокод

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
absorbing[transition[i][0]] = transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix(absorbing: '''boolean'''[n]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T22:07:07Z

Arimon: /* Построение матриц переходов */ косметические изменения

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
absorbing[transition[i][0]] = transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix(absorbing: '''boolean'''[]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-19T22:06:06Z

Arimon: /* Псевдокод */ косметические изменение

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=((\sum\limits_{k=1}^{n} G[k][j]+1)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: '''boolean'''[n], G: '''float'''[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T22:00:42Z

Arimon: /* Подсчет количества поглощащих состояний */ исправлен псевдокод

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
absorbing[transition[i][0]] = transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix(absorbing: boolean[]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T21:59:41Z

Arimon: /* Подсчет количества поглощащих состояний */ упразднен if

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
absorbing[transition[i][0]] = transition[i][1] '''and''' transition[i][2] == 1
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix(absorbing: boolean[]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T21:57:25Z

Arimon: /* Псевдокод */ исправлен псевдокод

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
'''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
absorbing[transition[i][0]] = ''true''
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix(absorbing: boolean[]):
'''int''' count_q = 0
'''int''' count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-19T21:44:34Z

Arimon: /* Псевдокод */ косметические

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=((\sum\limits_{k=1}^{n} G[k][j]+1)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли <tex>\mathtt{i}</tex>-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Расчёт вероятности поглощения в состоянии

2018-06-19T21:40:10Z

Arimon: /* Псевдокод */ исправлен псевдокод

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=((\sum\limits_{k=1}^{n} G[k][j]+1)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''float''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T21:22:36Z

Arimon: /* Псевдокод */ исправлен псевдокод

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}: boolean[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex> иначе <tex>\mathtt{absorbing}[\mathtt{i}] = false</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[n]
'''for''' i = 0 '''to''' m - 1
'''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
absorbing[transition[i][0]] = ''true''
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix():
count_q = 0
count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T21:12:09Z

Arimon: /* Подсчет количества поглощащих состояний */ изменен тип absorbing

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}: boolean[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[m]
'''for''' i = 0 '''to''' m - 1
'''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
absorbing[transition[i][0]] = ''true''
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix():
count_q = 0
count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-19T21:02:03Z

Arimon: Косметические изменения

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>0</tex>, в ином случае <tex>\mathtt{p_i}=((\sum\limits_{k=1}^{n} G[k][j]+1)/n</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>1</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>1</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''int''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-19T20:57:23Z

Arimon: Убрано mathtt с констант

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition}[\mathtt{i}][2]</tex> — вероятность перехода из состояния <tex>\mathtt{transition}[\mathtt{i}][0]</tex> в <tex>\mathtt{transition}[\mathtt{i}][1]</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition}[\mathtt{j}][2] = 1</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing}[\mathtt{i}] = true</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''boolean[]''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[m]
'''for''' i = 0 '''to''' m - 1
'''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
absorbing[transition[i][0]] = ''true''
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position}[\mathtt{n}]</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix():
count_q = 0
count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-19T20:43:56Z

Arimon: Косметические изменения

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{0}</tex>, в ином случае <tex>\mathtt{p_i=((\sum\limits_{k=1}^{n} G[k][j]+1)/n}</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим

'''float[]''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n]):
'''float''' probability[n]
'''for''' i = 0 '''to''' n - 1
'''int''' prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
'''return''' probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-16T14:13:47Z

Arimon: /* Подсчет количества поглощащих состояний */ все переменные в mathtt

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition[i][2]}</tex> — вероятность перехода из состояния <tex>\mathtt{transition[i][0]}</tex> в <tex>\mathtt{transition[i][1]}</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1}</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если <tex>\mathtt{i}</tex> — посглощающее состояние <tex>\mathtt{absorbing[i] = true}</tex>
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''function''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[m]
'''for''' i = 0 '''to''' m - 1
'''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
absorbing[transition[i][0]] = ''true''
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position[n]}</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix()
count_q = 0
count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-16T14:08:10Z

Arimon: /* См. также */

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{0}</tex>, в ином случае <tex>\mathtt{p_i=((\sum\limits_{k=1}^{n} G[k][j]+1)/n}</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим

'''function''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n])
float probability[n]
'''for''' i = 0 '''to''' n - 1
prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
return probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
*[[Математическое ожидание времени поглощения]]

==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Подсчёт количества поглощающих состояний и построение матриц переходов марковской цепи

2018-06-16T14:02:36Z

Arimon: Исправлены грамматические ошибки, добавлено см.также

==Подсчет количества поглощащих состояний==
Пусть <tex>\mathtt{transition}</tex> — массив переходов марковской цепи, где <tex>\mathtt{transition[i][2]}</tex> — вероятность перехода из состояния <tex>\mathtt{transition[i][0]}</tex> в <tex>\mathtt{transition[i][1]}</tex>.
Тогда, по определению поглощающего состояния, если <tex>\mathtt{j}</tex> — поглощающее состояние, то <tex>\mathtt{transition[j][2] = 1}</tex>. По этому признаку можно определить все поглощающие состояния в цепи.

===Псевдокод===
*<tex>\mathtt{absorbing}: boolean:[\mathtt{n}]</tex> — массив состояний. Если i — посглощающее состояние absorbing[i] = true
*<tex>\mathtt{n}</tex> — количество состояний
*<tex>\mathtt{m}</tex> — количество переходов

'''function''' findAbsorbings(transition: '''int'''[m][2]):
'''boolean''' absorbing[m]
'''for''' i = 0 '''to''' m - 1
'''if''' transition[i][0] == transition[i][1] '''and''' transition[i][2] == 1
absorbing[transition[i][0]] = ''true''
'''return''' absorbing

==Построение матриц переходов==
Cоздадим сначала массив <tex>\mathtt{position}</tex> где <tex>\mathtt{i}</tex>-ый элемент указывает под каким номером будет находиться <tex>\mathtt{i}</tex>-ое состояние среди существенных если оно существенное или несущественных в обратном случае, и заполним эти массивы.
===Псевдокод===
*<tex>\mathtt{position[n]}</tex> — массив нумерации состояний относительно существенной/несущественной матрицы.
*<tex>\mathtt{Q}</tex> — матрица перехода мужду несущественными состояниями.
*<tex>\mathtt{R}</tex> — матрица из несущественных состояний в поглощающие.

'''procedure''' buildTransitionMatrix()
count_q = 0
count_r = 0
'''for''' i = 0 '''to''' n - 1
'''if''' absorbing[i]
position[i] = count_r
count_r++
'''else'''
position[i] = count_q
count_q++
'''for''' i = 0 '''to''' m - 1
'''if''' absorbing[transition[i][1]]
'''if''' !absorbing[transition[i][0]]
R[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]
'''else'''
Q[position[transition[i][0]]][position[transition[i][1]]] = transition[i][2]

== См. также ==
*[[Марковская цепь]]
*[[Расчет вероятности поглощения в состоянии]]
*[[Математическое ожидание времени поглощения]]

== Источники информации ==
*[https://en.wikipedia.org/wiki/Absorbing_Markov_chain Wikipedia — Absorbing Markov chain]

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

Расчёт вероятности поглощения в состоянии

2018-06-16T13:28:18Z

Arimon: Поправлены: источники информации, см.также, дефисы, где нужно, заменены на тире

Поглощающее(существенное) состояние цепи Маркова — состояние с вероятностью перехода в самого себя <tex>p_{ii}=1</tex>.
Составим матрицу <tex>G</tex>, элементы которой <tex>g_{ij}</tex> равны вероятности того, что, выйдя из <tex>i</tex>, попадём в поглощающее состояние <tex>j</tex>.
{{Теорема
|statement=
<tex> G = N \cdot R </tex>, где <tex>N</tex> — фундаментальная матрица, и <tex>R</tex> — матрица перехода из несущественных состояний в существенные.
|proof=
Пусть этот переход будет осуществлён за <tex>r</tex> шагов: <tex>i</tex> → <tex>i_{1}</tex> → <tex>i_{2}</tex> → <tex>\ldots</tex> → <tex>i_{r-1}</tex> → j, где все <tex>i, i_{1}, \ldots i_{r-1}</tex> являются несущественными.
Тогда рассмотрим сумму <tex>\sum\limits_{\forall(i_{1} \ldots i_{r-1})} {p_{i, i_{1}} \cdot p_{i_{1}, i_{2}} \cdot \ldots \cdot p_{i_{r-1}, j}} = Q^{r-1} \cdot R</tex>, где <tex>Q</tex> — матрица переходов между несущественными состояниями, <tex>R</tex> — из несущественного в существенное.
Матрица <tex>G</tex> определяется их суммированием по всем длинам пути из i в j: <tex>G = \sum\limits_{r = 1}^{\infty}{Q^{r-1} \cdot R} = (I + Q + Q^{2} + Q^{3} + \ldots) \cdot R = NR</tex>, т.к. <tex>(I + Q + Q^2 + \ldots) \cdot (I - Q) = I - Q + Q - Q^{2} + \ldots = I</tex>, а фундаментальная матрица марковской цепи <tex>N = (I - Q)^{-1}</tex> }}
==Псевдокод==
Выведем ответ: в <tex>\mathtt{i}</tex>-ой строке вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии. Естественно, для несущественного состояния это <tex>\mathtt{0}</tex>, в ином случае <tex>\mathtt{p_i=((\sum\limits_{k=1}^{n} G[k][j]+1)/n}</tex> где <tex>\mathtt{j}</tex> — номер соответствующий <tex>\mathtt{i}</tex>-ому состоянию в матрице <tex>\mathtt{G}</tex> (т.е. под которым оно располагалось в матрице <tex> \mathtt{R} </tex> т.е. значение <tex>\mathtt{position[i]}</tex>). Прибавлять <tex>\mathtt{1}</tex> нужно т.к. вероятность поглотиться в <tex>\mathtt{i}</tex>-ом поглощающем состоянии, оказавшись изначально в нем же равна <tex>\mathtt{1}</tex>.
*<tex>\mathtt{probability[i]}</tex> — вероятность поглощения в <tex>\mathtt{i}</tex>-ом состоянии
*<tex>\mathtt{absorbing[i]}</tex> — является ли i-е состояние поглощающим

'''function''' getAbsorbingProbability(absorbing: boolean[n], G: float[n][n])
float probability[n]
'''for''' i = 0 '''to''' n - 1
prob = 0
'''if''' absorbing[i]
'''for''' j = 0 '''to''' nonabs - 1
prob += G[j][position[i]]
prob++
prob /= n
probability[i] = prob
return probability

==См. также==
*[[Марковская цепь]]
*[[Подсчет количества поглощающих состояний и построение матриц переходов марковской цепи]]
*[[Фундаментальная матрица]]
*[[Теорема о поглощении]]
==Источники информации==
* [http://ru.wikipedia.org/wiki/%D0%A6%D0%B5%D0%BF%D1%8C_%28%D0%BC%D0%B0%D1%82%D0%B5%D0%BC.%29 Википедия — Цепи Маркова]
* [http://www.studmed.ru/kemeni-dzh-snell-dzh-konechnye-cepi-markova_eb290d9f6f2.html Кемени Дж. и Снелл Дж., "Конечные цепи Маркова"]

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

[[Категория: Марковские цепи ]]

Получение номера по объекту

2017-12-25T22:43:33Z

Arimon: /* Разбиение на слагаемые */

== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).
Следующий алгоритм вычисляет эту сумму:
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,

'''int''' object2num(a: '''list<A>'''):
numOfObject = 0
'''for''' i = 1 '''to''' n // перебираем элементы комбинаторного объекта
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, в лексикографическом порядке меньшие рассматриваемого
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
numOfObject += d[i][j]
'''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.

== Битовые вектора ==
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,

'''int''' bitvector2num(bitvector: '''list<int>'''):
numOfBitvector = 0
'''for''' i = 1 '''to''' n
'''if''' bitvector[i] == 1
numOfBitvector += <tex>2^{n-i}</tex>
'''return''' numOfBitvector

Асимптотика алгоритма {{---}} <tex>O(n) </tex>.

== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,

'''int''' permutation2num(a: '''list<int>'''):
numOfPermutation = 0
'''for''' i = 1 '''to''' n // <tex>n</tex> {{---}} количество элементов в перестановке
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте
'''if''' was[j] == ''false'' // если элемент <tex>j</tex> ранее не был использован
numOfPermutation += P[n - i] // все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых
меньше нашего в лексикографическом порядке, идут раньше данной перестановки
was[a[i]] = ''true'' // <tex>i</tex>-й элемент использован
'''return''' numOfPermutation

Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.

== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,

'''int''' choose2num(choose: '''list<int>'''):
numOfChoose = 0
'''for''' i = 1 '''to''' K
'''for''' j = choose[i - 1] + 1 '''to''' choose[i] - 1
numOfChoose += C[N - j][K - i]
'''return''' numOfChoose

Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.

== Разбиение на слагаемые ==
Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.

*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.
*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.
*<tex>\mathtt{part[1 \ldots N]}</tex> {{---}} данное разбиение
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.

Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>.

Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>).

Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:


<tex dpi = "145">d[i][j] =
\left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + d[i - j][j], & i > j \end{array} \right.
</tex>


'''int''' part2num(part: '''list<int>'''):
'''int''' numOfPart = 0, last = 0, sum = 0
'''for''' i = 1 '''to''' part.size
'''for''' j = last '''to''' part[i] - 1 // перебираем все элементы, лексикографически меньшие нашего, но большие или равные предыдущего
numOfPart += d[N - sum - j][j] // прибавляем количество перестановок, которые могли начинаться с <tex>j</tex>
sum += part[i] // увеличиваем уже поставленную сумму
last = part[i] // обновляем последний поставленный элемент 
'''return''' numOfPart // возвращаем ответ

Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.

Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.

== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
*[[Получение следующего объекта|Получение следующего объекта]]
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]

== Источники информации ==
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Получение номера по объекту

2017-12-25T22:39:43Z

Arimon: /* Разбиение на слагаемые */ поправлен стиль псевдокода

== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).
Следующий алгоритм вычисляет эту сумму:
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,

'''int''' object2num(a: '''list<A>'''):
numOfObject = 0
'''for''' i = 1 '''to''' n // перебираем элементы комбинаторного объекта
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, в лексикографическом порядке меньшие рассматриваемого
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
numOfObject += d[i][j]
'''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.

== Битовые вектора ==
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,

'''int''' bitvector2num(bitvector: '''list<int>'''):
numOfBitvector = 0
'''for''' i = 1 '''to''' n
'''if''' bitvector[i] == 1
numOfBitvector += <tex>2^{n-i}</tex>
'''return''' numOfBitvector

Асимптотика алгоритма {{---}} <tex>O(n) </tex>.

== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,

'''int''' permutation2num(a: '''list<int>'''):
numOfPermutation = 0
'''for''' i = 1 '''to''' n // <tex>n</tex> {{---}} количество элементов в перестановке
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте
'''if''' was[j] == ''false'' // если элемент <tex>j</tex> ранее не был использован
numOfPermutation += P[n - i] // все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых
меньше нашего в лексикографическом порядке, идут раньше данной перестановки
was[a[i]] = ''true'' // <tex>i</tex>-й элемент использован
'''return''' numOfPermutation

Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.

== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,

'''int''' choose2num(choose: '''list<int>'''):
numOfChoose = 0
'''for''' i = 1 '''to''' K
'''for''' j = choose[i - 1] + 1 '''to''' choose[i] - 1
numOfChoose += C[N - j][K - i]
'''return''' numOfChoose

Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.

== Разбиение на слагаемые ==
Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.

*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.
*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.
*<tex>\mathtt{part[1 \ldots N]}</tex> {{---}} данное разбиение
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.

Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>.

Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>).

Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:


<tex dpi = "145">d[i][j] =
\left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + d[i - j][j], & i > j \end{array} \right.
</tex>


'''int''' part2num('''list<int>''' part):
'''int''' numOfPart = 0, last = 0, sum = 0
'''for''' i = 1 '''to''' part.size
'''for''' j = last '''to''' part[i] - 1 // перебираем все элементы, лексикографически меньшие нашего, но большие или равные предыдущего
numOfPart += d[N - sum - j][j] // прибавляем количество перестановок, которые могли начинаться с <tex>j</tex>
sum += part[i] // увеличиваем уже поставленную сумму
last = part[i] // обновляем последний поставленный элемент 
'''return''' numOfPart // возвращаем ответ

Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.

Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.

== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
*[[Получение следующего объекта|Получение следующего объекта]]
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]

== Источники информации ==
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Получение номера по объекту

2017-12-25T22:30:15Z

Arimon: /* Разбиение на слагаемые */ исправлена грамматика и косметические изменения

== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).
Следующий алгоритм вычисляет эту сумму:
*<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>,
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>,

'''int''' object2num(a: '''list<A>'''):
numOfObject = 0
'''for''' i = 1 '''to''' n // перебираем элементы комбинаторного объекта
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, в лексикографическом порядке меньшие рассматриваемого
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
numOfObject += d[i][j]
'''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.

== Битовые вектора ==
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,

'''int''' bitvector2num(bitvector: '''list<int>'''):
numOfBitvector = 0
'''for''' i = 1 '''to''' n
'''if''' bitvector[i] == 1
numOfBitvector += <tex>2^{n-i}</tex>
'''return''' numOfBitvector

Асимптотика алгоритма {{---}} <tex>O(n) </tex>.

== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,
*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,
*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,
*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,

'''int''' permutation2num(a: '''list<int>'''):
numOfPermutation = 0
'''for''' i = 1 '''to''' n // <tex>n</tex> {{---}} количество элементов в перестановке
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте
'''if''' was[j] == ''false'' // если элемент <tex>j</tex> ранее не был использован
numOfPermutation += P[n - i] // все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых
меньше нашего в лексикографическом порядке, идут раньше данной перестановки
was[a[i]] = ''true'' // <tex>i</tex>-й элемент использован
'''return''' numOfPermutation

Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта.

== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:
*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
*<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>,

'''int''' choose2num(choose: '''list<int>'''):
numOfChoose = 0
'''for''' i = 1 '''to''' K
'''for''' j = choose[i - 1] + 1 '''to''' choose[i] - 1
numOfChoose += C[N - j][K - i]
'''return''' numOfChoose

Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта.

== Разбиение на слагаемые ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного разбиения на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.

*<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.
*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.
*<tex>\mathtt{part[1 \ldots N]}</tex> {{---}} данное разбиение
*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.

Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>.

Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>).

Получаем рекуррентное соотношение для подсчёта <tex>d</tex>:


<tex dpi = "145">d[i][j] =
\left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + d[i - j][j], & i > j \end{array} \right.
</tex>


'''int''' part2num(part: '''list<int>'''):
numOfPart = 0
'''for''' i = 1 '''to''' part.size
'''for''' j = last '''to''' part[i] - 1 // перебираем все элементы, лексикографически меньшие нашего, но большие или равные предыдущего
numOfPart += d[N - sum - j][j] // прибавляем количество перестановок, которые могли начинаться с <tex>j</tex>
sum += part[i] // увеличиваем уже поставленную сумму
last = part[i] // обновляем последний поставленный элемент 
'''return''' numOfPart // возвращаем ответ

Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.

Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.

== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
*[[Получение следующего объекта|Получение следующего объекта]]
*[[Правильные скобочные последовательности#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]]

== Источники информации ==
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]