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

Обсуждение:Собственные векторы и собственные значения

2013-06-12T12:02:25Z

Mihver1: Новая страница: «Там, где не доказаны леммы, подразумевается не сложное упражнение. В последнем это лишь п...»

Там, где не доказаны леммы, подразумевается не сложное упражнение. В последнем это лишь пример, а не доказательство. Все доказательство сводится к строчке (ссылка не теорему высшей алгебры, что у любого полинома комплексной переменной есть корень). Не плохо было бы сделать какое-то оглавление. Хорошо было бы начинать предложения с заглавных букв, иначе трудно читать. Есть мелкие опечатки. '''(Одинцова)'''

Заглавие, хоть и искусственное, теперь есть. Леммы-упражнения пока не доказал, остальное все исправил? '''(Шаламов)'''

Я там сама многое поправила, если найдешь значок равно с восклицательным знаком сверху (единственным образом), то замени его в первой лемме. А так все хорошо. '''(Одинцова)'''

Поправил чутка, можешь глянуть. А там где туда и обратно, а из этого следует доказательство - тоже чото неочевидно как доказывать, хотя в конспекте так же написано '''(Исаев)'''

Посмотрите еще раз. я не знаю как доказать одну из лемм, кроме как поверить, а у второй доказалельство по определению '''(Шаламов)'''

Думаю вторую лемму можно совсем тогда убрать, а в первой посмотри определение подпространства, и мы же знаем что сумма св и умножение св на число оставляет их св, вот эти два пункта и приведут к доказательству. Если что могу вечером сама это дописать '''(Одинцова)'''

Динамика по поддеревьям

2013-01-13T21:43:24Z

Mihver1: /* Динамика по поддеревьям */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, так как они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. То есть необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
Заполним изначально массив <tex>dp[V][2]</tex> числами -1. (<tex>V</tex> {{---}} число вершин)

calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else: //случай 2: берем какое-то ребро
max1 = dp[v][0]
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:42:43Z

Mihver1: /* Рекуррентная формула */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
Заполним изначально массив <tex>dp[V][2]</tex> числами -1. (<tex>V</tex> {{---}} число вершин)

calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else: //случай 2: берем какое-то ребро
max1 = dp[v][0]
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:38:34Z

Mihver1: /* Реализация */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
Заполним изначально массив <tex>dp[V][2]</tex> числами -1. (<tex>V</tex> {{---}} число вершин)

calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else: //случай 2: берем какое-то ребро
max1 = dp[v][0]
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:33:00Z

Mihver1: /* Реализация */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
Заполним изначально массив <tex>dp[V][2]</tex> числом -1. (<tex>V</tex> {{---}} число вершин)

calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else:
max1 = dp[v][0] //случай 2: берем какое-то ребро
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:32:31Z

Mihver1: /* Реализация */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
Заполним изначально массив dp[V][2] числом -1. (V {{---}} число вершин)

calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else:
max1 = dp[v][0] //случай 2: берем какое-то ребро
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:30:48Z

Mihver1: /* Реализация */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
Заполним изначально массив dp[N][2] числом -1.

calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if useRoot == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
else:
max1 = dp[v][0] //случай 2: берем какое-то ребро
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:17:01Z

Mihver1: /* Реализация */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
calculate(v, useRoot):
if dp[v][useRoot] не было посчитанно ранее:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if use_root == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
return sum
max1 = dp[v][0] //случай 2: берем какое-то ребро
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T21:14:20Z

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

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Реализация===
calculate(v, useRoot):
if dp[v][useRoot] != -1:
return dp[v][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if use_root == 0: //случай 1: не берем ребра из корня
for (для) всех u из множества детей v:
sum += calculate(u, 1)
dp[v][useRoot] = sum
return sum
max1 = dp[v][0] //случай 2: берем какое-то ребро
for (для) всех x из множества детей v:
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[v,x])
dp[v][useRoot] = max1
return dp[v][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:51:08Z

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

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
calculate(vertex, useRoot):
if dp[vertex][useRoot] != -1:
return dp[vertex][useRoot] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if use_root == 0: //случай 1: не берем ребра из корня
for u in child(vertex):
sum += calculate(u, 1)
dp[vertex][useRoot] = sum
return sum
max1 = dp[vertex][0]
for x in child(vertex): //случай 2: берем какое-то ребро
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[vertex,x])
dp[vertex][useRoot] = max1
return dp[vertex][useRoot]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:49:17Z

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

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
calculate(vertex, use_root):
if dp[vertex][root] != -1:
return dp[vertex][use_root] //вернули уже посчитанное значение dp[vertex][root]
sum = 0
if use_root == 0: //случай 1: не берем ребра из корня
for u in child(vertex):
sum += calculate(u, 1)
dp[vertex][use_root] = sum //выполняем мемоизацию
return sum
max1 = dp[vertex][0]
for x in child(vertex): //случай 2: берем какое-то ребро
max1 = max(max1, calculate(x, 0) + calculate(vertex, 0) - calculate(x, 1) + w[vertex,x])
dp[vertex][use_root] = max1 //выполняем мемоизацию
return dp[vertex][use_root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:45:59Z

Mihver1: /* Динамика по поддеревьям */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по поддеревьям является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:43:24Z

Mihver1: /* Рекуррентная формула */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>vertex</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:26:43Z

Mihver1: /* Формулировка */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной, и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:24:54Z

Mihver1: /* Формулировка */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, чтобы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Дискретная математика, алгоритмы и структуры данных

2013-01-13T20:23:08Z

Mihver1: /* Динамическое программирование */

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

Убедительная просьба читать [[Обсуждение:Дискретная_математика_и_алгоритмы | правила оформления вики-конспектов]].

= Первый семестр =

== Отношения ==
*[[Определение отношения]]
*[[Степень отношений]]
*[[Композиция отношений|Композиция отношений. Обратное отношение]]
*[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]]
*[[Симметричное отношение]]
*[[Антисимметричное отношение]]
*[[Транзитивное отношение]]
*[[Транзитивное замыкание|Транзитивное замыкание отношения]]
*[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]]
*[[Транзитивный остов]]
*[[Отношение порядка]]
*[[Отношение эквивалентности]]

== Булевы функции ==
*[[Определение булевой функции]]
*[[Суперпозиции]]
*[[ДНФ]]
*[[КНФ]]
*[[Полином Жегалкина]]
*[[Полные системы функций. Теорема Поста о полной системе функций]]
*[[Сокращенная и минимальная ДНФ]]
*[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]]
*[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]]
*[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]]
*[[Представление функции класса DM с помощью медианы]]
*[[Пороговая функция]]

== Схемы из функциональных элементов ==
*[[Реализация булевой функции схемой из функциональных элементов]]
*[[Cумматор]]
*[[Каскадный сумматор]]
*[[Двоичный каскадный сумматор]]
*[[Реализация вычитания сумматором]]
*[[Матричный умножитель]]
*[[Дерево Уоллеса]]

== Представление информации ==
*[[Кодирование информации]]
*[[Представление целых чисел: прямой код, код со сдвигом, дополнительный код]]
*[[Представление вещественных чисел]]
*[[Представление символов, таблицы кодировок]]

== Алгоритмы сжатия ==
*[[Алгоритм Хаффмана]]
*[[Алгоритм LZW]]
*[[Алгоритмы LZ77 и LZ78]]
*[[Преобразование Барроуза-Уиллера]]
*[[Обратное преобразование Барроуза-Уиллера]]
*[[Преобразование MTF]]
*[[Расстояние Хэмминга]]
*[[Избыточное кодирование, код Хэмминга]]
*[[Неравенство Крафта]]
*[[Неравенство Макмиллана]]
*[[Алгоритм Ху-Таккера]]

== Комбинаторика ==
*[[Комбинаторные объекты]]
*[[Лексикографический порядок]]
*[[Формула включения-исключения]]
*[[Генерация комбинаторных объектов в лексикографическом порядке]]
*[[Получение номера по объекту]]
*[[Получение объекта по номеру]]
*[[Получение следующего объекта]]
*[[Коды Грея]]
*[[Коды Грея для перестановок]]
*[[Коды антигрея]]
*[[Цепные коды]]
*[[Правильные скобочные последовательности]]
*[[Действие перестановки на набор из элементов, представление в виде циклов]]
*[[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
*[[Методы генерации случайного сочетания]]
*[[Таблица инверсий]]
*[[Умножение перестановок, обратная перестановка, группа перестановок]]
*[[Теорема Кэли]]
*[[Матричное представление перестановок]]
*[[Задача о минимуме/максимуме скалярного произведения]]
*[[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
*[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
*[[Производящая функция]]
*[[Задача об ожерельях]]

== [[Динамическое программирование]] ==
*[[Кратчайший путь в ациклическом графе]]
*[[Задача о расстановке знаков в выражении]]
*[[Задача о наибольшей общей подпоследовательности]]
*[[Задача о порядке перемножения матриц]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
*[[Задача о паросочетании максимального веса в дереве, амортизированные оценки для ДП на дереве]]
*[[Метод четырех русских для умножения матриц]]
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]
*[[Задача коммивояжера, ДП по подмножествам]]
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
*[[Задача о расстоянии Дамерау-Левенштейна]]
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
*[[Задача о наибольшей подпоследовательности-палиндроме]]
*[[Meet-in-the-middle]]
*[[Динамическое программирование по профилю]]
*[[Задача о рюкзаке]]
*[[Динамика по поддеревьям]]

== Теория вероятностей ==
*[[Вероятностное пространство, элементарный исход, событие]]
*[[Независимые события]]
*[[Условная вероятность]]
*[[Формула Байеса]]
*[[Формула полной вероятности]]
*[[Дискретная случайная величина]]
*[[Независимые случайные величины]]
*[[Математическое ожидание случайной величины]]
*[[Дисперсия случайной величины]]
*[[Ковариация случайных величин]]
*[[Корреляция случайных величин]]
*[[Энтропия случайного источника]]
*[[Симуляция одним распределением другого]]
*[[Арифметическое кодирование]]
*[[Парадоксы теории вероятностей]]
*[[Схема Бернулли]]

== Марковские цепи ==

* [[Марковская цепь]]
* [[Теорема о поглощении]]
* [[Фундаментальная матрица]]
* [[Математическое ожидание времени поглощения]]
* [[Расчет вероятности поглощения в состоянии]]
* [[Эргодическая марковская цепь]]
* [[Регулярная марковская цепь]]
* [[Примеры использования Марковских цепей]]

= Второй семестр =

== Амортизационный анализ ==
* [[Амортизационный анализ]]
* [[Саморасширяющийся массив]]
* [[Массив с увеличением/уменьшением размера]]
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Персистентный стек]]
* [[Персистентный дек]]

== Приоритетные очереди ==

* [[Двоичная куча]]
* [[Биномиальная куча]]
* [[Фибоначчиева куча]]

== Система непересекающихся множеств ==
* [[СНМ (наивные реализации) | Наивные реализации]]
* [[СНМ (списки с весовой эвристикой) | Списки с весовой эвристикой]]
* [[СНМ(реализация с помощью леса корневых деревьев) | Реализация с помощью леса корневых деревьев]]

== Поисковые структуры данных ==
* [[Упорядоченное множество]]
* [[Дерево поиска, наивная реализация]]
* [[АВЛ-дерево]]
* [[2-3 дерево]]
* [[B-дерево]]
* [[Красно-черное дерево]]
* [[Декартово дерево]]
* [[Декартово дерево по неявному ключу]]
* [[Splay-дерево]]
* [[Рандомизированное бинарное дерево поиска]]
* [[Дерево ван Эмде Боаса]]
* [[Список с пропусками]]

== Дерево отрезков ==

* [[Статистики на отрезках. Корневая эвристика]]
* [[Дерево отрезков. Построение]]
* [[Реализация запроса в дереве отрезков сверху]]
* [[Реализация запроса в дереве отрезков снизу]]
* [[Несогласованные поддеревья. Реализация массового обновления]]
* [[Многомерное дерево отрезков]]
* [[Сжатое многомерное дерево отрезков]]

== Дерево Фенвика ==
* [[Дерево Фенвика]]
* [[Встречное дерево Фенвика]]
* [[Дерево Фенвика для некоммутативных операций]]
* [[Многомерное дерево Фенвика]]

== Хеширование ==
* [[Хеш-таблица]]
* [[Разрешение коллизий]]
* [[Хеширование кукушки]]
* [[Идеальное хеширование]]
* [[Перехеширование. Амортизационный анализ]]
* [[Фильтр Блума]]
* [[Универсальное семейство хеш-функций]]

== [[Сортировка]] ==
* [[Сортировка выбором]]
* [[Сортировка пузырьком]]
* [[Сортировка вставками]]
* [[Сортировка кучей]]
* [[Быстрая сортировка]]
* [[Сортировка слиянием]]
* [[Cортировка слиянием с использованием O(1) дополнительной памяти]]
* [[Теорема о нижней оценке для сортировки сравнениями]]
* [[Сортировка подсчетом]]
* [[Сортировка подсчетом сложных объектов]]
* [[Цифровая сортировка]]
* [[Карманная сортировка]]
* [[Поиск k-ой порядковой статистики]]
* [[Поиск k-ой порядковой статистики за линейное время]]
* [[Сортировка Хана]]

== Сортирующие сети ==
* [[Сортирующие сети]]
* [[0-1 принцип | Проверка сети компараторов на то, что она сортирующая. 0-1 принцип]]
* [[Сортирующие сети для квадратичных сортировок]]
* [[Сеть Бетчера]]

== Алгоритмы поиска ==
* [[Целочисленный двоичный поиск]]
* [[Вещественный двоичный поиск]]
* [[Троичный поиск]]
* [[Поиск с помощью золотого сечения]]
* [[Интерполяционный поиск]]

== Связь между структурами данных ==
* [[Связь между структурами данных]]

= Третий семестр =

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

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

== Остовные деревья ==
* [[Матрица Кирхгофа]]
* [[Связь матрицы Кирхгофа и матрицы инцидентности]]
* [[Подсчет числа остовных деревьев с помощью матрицы Кирхгофа]]
* [[Количество помеченных деревьев]]
* [[Коды Прюфера]]

== Обходы графов ==
* [[Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфов]]
* [[Покрытие ребер графа путями]]
* [[Алгоритм построения Эйлерова цикла]]
* [[Произвольно вычерчиваемые из заданной вершины графы]]
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
* [[Теорема Дирака]]
* [[Теорема Оре]]
* [[Турниры]]
* [[Теорема Редеи-Камиона]]

== Укладки графов ==
* [[Укладка графа на плоскости]]
* [[Формула Эйлера]]
* [[Непланарность K5 и K3,3|Непланарность <tex>K_5</tex> и <tex>K_{3,3}</tex>]]
* [[Укладка дерева]]
* [[Укладка графа с планарными компонентами реберной двусвязности]]
* [[Укладка графа с планарными компонентами вершинной двусвязности]]
* [[Теорема Понтрягина-Куратовского]]
* [[Двойственный граф планарного графа]]

== Раскраски графов ==
* [[Раскраска графа]]
* [[Двудольные графы и раскраска в 2 цвета]]
* [[Хроматический многочлен]]
** [[Хроматический многочлен#Хроматический многочлен полного графа|Хроматический многочлен полного графа]]
** [[Хроматический многочлен#Хроматический многочлен пустого графа|Хроматический многочлен пустого графа]]
** [[Хроматический многочлен#Хроматический многочлен дерева|Хроматический многочлен дерева]]
** [[Хроматический многочлен#Рекуррентные формулы для хроматических многочленов|Рекуррентные формулы для хроматических многочленов]]
** [[Хроматический многочлен#Коэффициенты хроматического многочлена|Коэффициенты хроматического многочлена: старший, второй коэффициенты, знакопеременность]]
* [[Формула Зыкова]]
* [[Формула Уитни]]
* [[Теорема Брукса]]
* [[Верхняя оценка хроматического числа длиной нечетного цикла]]
* [[Верхние и нижние оценки хроматического числа]]

== Обход в глубину ==
* [[Обход в глубину, цвета вершин]]
* [[Лемма о белых путях]]
* [[Использование обхода в глубину для проверки связности]]
* [[Использование обхода в глубину для поиска цикла в ориентированном графе]]
* [[Использование обхода в глубину для топологической сортировки]]
* [[Использование обхода в глубину для поиска компонент сильной связности]]
* [[Использование обхода в глубину для поиска точек сочленения]]
* [[Построение компонент вершинной двусвязности]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Построение компонент реберной двусвязности]]

== Кратчайшие пути в графах ==
* [[Обход в ширину]]
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Дейкстры]]
* [[Алгоритм Флойда]]
* [[Алгоритм A*]]
* [[Алгоритм Джонсона]]

== Построение остовных деревьев ==
* [[Лемма о безопасном ребре]]
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм Борувки]]
* [[Критерий Тарьяна минимальности остовного дерева|Теорема Тарьяна (критерий минимальности остовного дерева)]]
* [[Алгоритм двух китайцев]]

== Задача о паросочетании ==
* [[Теорема о максимальном паросочетании и дополняющих цепях]]
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
* [[Алгоритм Куна для поиска максимального паросочетания]]
* [[Теорема Холла]]
* [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах]]
* [[Связь вершинного покрытия и независимого множества]]
* [[Матрица Татта и связь с размером максимального паросочетания в двудольном графе]]
* [[Алгоритм вырезания соцветий|Паросочетания в недвудольных графах. Алгоритм вырезания соцветий]]

== Задача о максимальном потоке ==
* [[Определение сети, потока]]
* [[Разрез, лемма о потоке через разрез]]
* [[Дополняющая сеть, дополняющий путь]]
* [[Лемма о сложении потоков]]
* [[Теорема Форда-Фалкерсона]]
* [[Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
* [[Алоритм Эдмондса-Карпа]]
* [[Алгоритм масштабирования потока]]
* [[Блокирующий поток]]
* [[Схема алгоритма Диница]]
* [[Теоремы Карзанова о числе итераций алгоритма Диница в сети с целочисленными пропускными способностями]]
* [[Алгоритм поиска блокирующего потока в ациклической сети]]
* [[Метод проталкивания предпотока]]
* [[Алгоритм "поднять-в-начало"]]
* [[Теорема о декомпозиции]]
* [[Теорема о декомпозиционном барьере]]
* [[Циркуляция потока]]

== Задача о потоке минимальной стоимости ==
* [[Поток минимальной стоимости]]
* [[Теорема Форда-Фалкерсона о потоке минимальной стоимости]]
* [[Лемма об эквивалентности свойства потока быть минимальной стоимости и отсутствии отрицательных циклов в остаточной сети]]
* [[Поиск потока минимальной стоимости методом дополнения вдоль путей минимальной стоимости]]
* [[Использование потенциалов Джонсона при поиске потока минимальной стоимости]]
* [[Сведение задачи о назначениях к задаче о потоке минимальной стоимости]]
* [[Венгерский алгоритм решения задачи о назначениях]]

= Четвертый семестр =

== Основные определения. Простые комбинаторные свойства слов ==
* [[Основные определения, связанные со строками]]
* [[Период и бордер, их связь]]
* [[Слово Фибоначчи]]
* [[Слово Туэ-Морса]]

== Поиск подстроки в строке ==
* [[Наивный алгоритм поиска подстроки в строке]]
* [[Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа]]
* [[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
* [[Префикс-функция]]
* [[Алгоритм Кнута-Морриса-Пратта]]
* [[Z-функция]]
* [[Автомат для поиска образца в тексте]]
* [[Бор]]
* [[Алгоритм Ахо-Корасик]]

== Суффиксное дерево ==
* [[Суффиксный бор]]
* [[Сжатое суффиксное дерево]]
* [[Алгоритм Укконена]]

== Суффиксный массив ==
* [[Суффиксный массив]]
* [[Построение суффиксного массива с помощью стандартных методов сортировки]]
* [[Цифровая сортировка]]
* [[Алгоритм цифровой сортировки суффиксов циклической строки]]
* [[Алгоритм Касаи и др.]]
* [[Алгоритм Карккайнена-Сандерса]]
* [[Алгоритм поиска подстроки в строке с помощью суффиксного массива]]

== Задача о наименьшем общем предке ==
* [[Метод двоичного подъема]]
* [[Сведение задачи LCA к задаче RMQ]]
* [[Решение RMQ с помощью разреженной таблицы]]
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
* [[Алгоритм Шибера-Вишкина]]
* [[Сведение задачи RMQ к задаче LCA]]

== Матроиды ==
* [[Определение матроида]]
* [[Примеры матроидов]]
* [[Прямая сумма матроидов]]
* [[Теорема Радо-Эдмондса (жадный алгоритм)]]
* [[Жадный алгоритм поиска базы минимального веса]]
* [[Теорема о базах]]
* [[Аксиоматизация матроида базами]]
* [[Теорема о циклах]]
* [[Аксиоматизация матроида циклами]]
* [[Ранговая функция, полумодулярность]]
* [[Двойственный матроид]]
* [[Оператор замыкания для матроидов]]
=== Пересечение матроидов ===
* [[Пересечение матроидов, определение, примеры]]
* [[Лемма о паросочетании в графе замен]]
* [[Лемма о единственном паросочетании в графе замен]]
* [[Граф замен для двух матроидов]]
* [[Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем]]
* [[Алгоритм построения базы в пересечении матроидов]]
* [[Теорема Эдмондса-Лоулера]]
=== Объединение матроидов ===
* [[Объединение матроидов, проверка множества на независимость]]
* [[Объединение матроидов, доказательство того, что объединение является матроидом]]
* [[Алгоритм построения базы в объединении матроидов]]

== Теория расписаний ==
* [[Классификация задач]]
* [[Методы решения задач теории расписаний]]
* [[Правило Лаулера]]
* [[Flow shop]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* [[QpmtnCmax|<tex>Q \mid pmtn \mid C_{max}</tex>]]
* [[QpmtnriLmax|<tex>Q \mid pmtn, r_{i} \mid L_{max}</tex>]]
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]
* [[Opi1sumu|<tex>O \mid p_{ij} = 1 \mid \sum U_i</tex>]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i U_i</tex>]]
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
* [[1ridipi1|<tex>1 \mid r_{i}, d_{i}, p_{i} = 1 \mid -</tex>]]
* [[1outtreesumwc | <tex>1 \mid outtree \mid \sum w_i C_i</tex>]]
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
* [[P1sumu|<tex>1 \mid \mid \sum U_{i}</tex>]]

Динамика по поддеревьям

2013-01-13T20:22:05Z

Mihver1:

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

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

Динамика по поддеревьям

2013-01-13T20:20:27Z

Mihver1: /* Динамика по поддеревьям */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку.
* Запретить выбирать ребра из корня.

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(vertex, use\_root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>use\_root=1</tex>, то в этом поддереве мы разрешаем занимать корень, иначе нет. Обозначим вес ребра из <tex>v</tex> в <tex>u</tex> как <tex>w[v,u]</tex>

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ w[u, x] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(v, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Ссылки==
*[http://www.mathnet.ru/links/502560b495f4a3fab62422161e16895f/timb86.pdf Научная статья, решающая похожую задачу из примера (pdf)]

Динамика по поддеревьям

2013-01-13T19:59:11Z

Mihver1: /* Формулировка */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из его ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку
* Запретить выбирать ребра из корня

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе нет.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:39:51Z

Mihver1: /* Динамика по деревьям */

=Динамика по поддеревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку
* Запретить выбирать ребра из корня

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе нет.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:39:27Z

Mihver1: /* Динамика по деревьям */

=Динамика по деревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на ответы в других поддеревьях.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку
* Запретить выбирать ребра из корня

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе нет.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:36:39Z

Mihver1: /* Решение */

=Динамика по деревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на другие поддеревья.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Разрешить выбирать ребро из корня к ребенку
* Запретить выбирать ребра из корня

Если мы запрещаем, значит можем разрешить всем его детям выбрать ребро из своего корня к своим детям. В ином случае мы можем разрешить не всем детям, а только тем, которые не были выбраны ребром из корня.

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе нет.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:34:51Z

Mihver1: /* Формулировка */

=Динамика по деревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на другие поддеревья.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не имели бы общих вершин. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе нет.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:29:58Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на другие поддеревья.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не являлись бы соседними. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex>.
Если <tex>root=1</tex>, то в этом поддереве мы разрешаем занимать корень. Иначе нет.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:28:55Z

Mihver1: /* Решение */

=Динамика по деревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на другие поддеревья.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не являлись бы соседними. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex> и использующего корень, если <tex>root=1</tex> и наоборот.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:25:00Z

Mihver1: /* Динамика по деревьям */

=Динамика по деревьям=

Главной особенностью [[динамическое программирование|динамического программирования]] по дереву является необходимость учитывать ответы в поддеревьях, т.к. они могут влиять на другие поддеревья.
Рассмотрим для лучшего понимания динамики по поддеревьям задачу о максимальном взвешенном паросочетании в дереве.
==Задача о максимальном взвешенном паросочетании на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждом из ее ребер. Необходимо выбрать такое множество ребер, что бы сумма значений была максимальной и при этом выбранные ребра не являлись бы соседними. Т.е. необходимо решить задачу о максимальном взвешенном паросочетании.

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex> и использующего корень, если <tex>root=1</tex> и наоборот.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:20:53Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

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

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
Обозначим в качестве <tex>dp(u, root)</tex> функцию, возвращающую ответ для поддерева с корнем <tex>u</tex> и использующего корень, если <tex>root=1</tex> и наоборот.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:18:32Z

Mihver1: /* Общие принципы динамики по поддеревьям */

=Динамика по деревьям=

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

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

Динамика по поддеревьям

2013-01-13T18:18:00Z

Mihver1: /* Динамика по деревьям */

=Динамика по деревьям=

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

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Занять корень каким-то ребром
* Не занимать корень ребрами

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

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ w[u,x] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем ребра из корня
if root==0:
for u in child(v):
sum1 += calculate(u, 1)
#выполняем мемоизацию
dp[v][root] = sum1
return sum1
max1 = dp[v][0]
#случай 2: берем какое-то ребро
for x in child(v):
max1 = max(max1, calculate(x, 0) + calculate(v, 0) - calculate(x, 1) + w[v,x])
# выполняем мемоизацию
dp[v][root] = max1
return dp[v][root]

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T18:05:44Z

Mihver1: /* Решение */

=Динамика по деревьям=

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

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальное взвешенное паросочетание]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять какое-то ребро из корня
* Не взять ни одного ребра из корня

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u,w] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u, 1)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T18:05:13Z

Mihver1: /* Задача о максимальном независимом множестве на дереве */

=Динамика по деревьям=

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

===Решение===
[[Файл:parosochetanie.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять какое-то ребро из корня
* Не взять ни одного ребра из корня

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u,w] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u, 1)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Файл:Parosochetanie.png

2013-01-13T18:03:55Z

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

Файл:Parosochetanie.png

2013-01-13T17:58:16Z

Mihver1:

Динамика по поддеревьям

2013-01-13T17:45:00Z

Mihver1: /* Формулировка */

=Динамика по деревьям=

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

===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u, 1)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T17:43:28Z

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

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v, root):
if dp[v][root] != -1:
return dp[v][root]
#вернули уже посчитанное значение dp[v][root]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u, 1)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T17:34:20Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что вторую формулу можно упростить: 
<tex>\sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1) = dp(u, 0) - dp(x, 1)</tex>

Теперь наши формулы имеют вид: 
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ dp(u, 0) - dp(x, 1)\ +\ a[u] \}\right\}</tex>

Заметим, что с помощью этого преобразования мы сократили общее время вычисления с <tex>O(n^2)</tex> до <tex>O(n)</tex>.

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T17:27:16Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T17:25:03Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
Заметим, что в случае взятия корня мы сразу же можем перейти к внукам нашего корня.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(v, 1)\ +\ a[u] \}\right\}</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T17:20:38Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
Заметим, что в случае взятия корня мы сразу же можем перейти к внукам нашего корня.

<tex>dp(u, 0) = \sum_{\text{child}\ v\ of\ u}dp(w, 1)</tex> 
<tex>dp(u, 1) = \max\left\{dp(u, 0),\ \max_{\text{child}\ x\ of\ u}\{dp(x, 0)\ +\ \sum_{\text{child}\ v\ of\ u; \ v \ne x }dp(x, 1)\ +\ a[u] \}\right\}</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T16:06:28Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
Заметим, что в случае взятия корня мы сразу же можем перейти к внукам нашего корня.

<tex>I(u) = \max\left\{a[u]\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\}</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T16:02:05Z

Mihver1: /* Решение */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Максимальный независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
Заметим, что в случае взятия корня мы сразу же можем перейти к внукам нашего корня.

<tex dpi=180>I(u) = \max\left\{a[u]\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\}</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T16:00:44Z

Mihver1: /* Рекуррентная формула */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
Заметим, что в случае взятия корня мы сразу же можем перейти к внукам нашего корня.

<tex dpi=180>I(u) = \max\left\{a[u]\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\}</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T16:00:16Z

Mihver1: /* Динамика по дереву */

=Динамика по деревьям=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
==Задача о максимальном независимом множестве на дереве==
===Формулировка===
Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
===Решение===
[[Файл:Independent_set_tree.png|100px|right|frame|Независимый набор из красных вершин]]
Давайте заметим, что в случае дерева эта задача имеет решение методом динамического программирования, в отличии от общего случая на произвольном множестве. Это обобщение относится к классу NP-полных задач.
Главное отличие этой задачи от других динамически решаемых {{---}} ответ в одном поддереве влияет на решение в остальных.

Рассмотрим наше первое состояние, когда еще не выбрана ни одна вершина. В этом случае мы можем сделать две вещи:
* Взять корень в наше множество
* Не взять корень в наше множество

В первом случае мы не сможем рассматривать его детей вовсе (т.е. при переходе в его поддеревья, мы не будем рассматривать возможность добавления корня в множество). В ином случае мы переходим в его поддеревья и выполняем то же самое действие.

===Рекуррентная формула===
Заметим, что в случае взятия корня мы сразу же можем перейти к внукам нашего корня.

<tex>I(u) = \max\left\{a[u]\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\},</tex>

===Псевдокод===
function calculate(v):
if dp[v] != -1:
return dp[v]
#вернули уже посчитанное значение dp[v]
sum1 = 0
#случай 1: не берем корень
for u in child(v):
sum1 += calculate(u)
sum2 = a[v]
#случай 2: берем корень
for u in child(v):
for t in child(u): # считаем, что у нас нет ребер наверх, к корню
sum2 += calculate(t)
# выполняем мемоизацию
dp[v] = max(sum1, sum2)
return dp[v]

child(v) -- возвращает детей вершины v

==Общие принципы динамики по поддеревьям==
Самое главное и основное отличие {{---}} ответ в одном поддереве может влиять на другие ответы, как в предыдущей задаче влиял выбор корня.

Динамика по поддеревьям

2013-01-13T15:25:39Z

Mihver1:

=Динамика по дереву=

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
{{Определение
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
}}
[[Файл:Independent_set_tree.png|100px|right|frame|Независимый набор из красных вершин]]

Файл:Independent set tree.png

2013-01-13T15:20:40Z

Mihver1: загружена новая версия «Файл:Independent set tree.png»

Динамика по поддеревьям

2013-01-13T15:18:44Z

Mihver1:

Рассмотрим динамику по дереву на примере задачи о максимальном независимом множестве в дереве.
[[Файл:Independent_set_tree.png|100px|right|frame|Независимый набор из красных вершин]]
{{Определение
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Пусть дано подвешенное за корень дерево, имеющее веса на каждой из ее вершин. Необходимо выбрать такое множество вершин, что бы сумма значений была максимальной и при этом выбранные вершины не являлись бы друг-другу соседями (отец-сын).
}}

Файл:Independent set tree.png

2013-01-13T15:17:20Z

Mihver1:

Задача о порядке перемножения матриц

2012-12-23T16:43:26Z

Mihver1: /* Оптимизации динамическим программированием */

'''Задача о порядке перемножения матриц''' (англ. ''chain matrix multiplication'') — классическая задача, которая может быть решена с помощью динамического программирования. В этой задаче нам дается последовательность матриц, в которой мы хотим найти самый эффективный способ их перемножения.

У нас есть множество способов перемножить матрицы, потому что операция перемножения ассоциативна. Другими словами, нет разницы в каком порядке расставляются скобки между множителями, результат будет один и тот же.

[[Правильные скобочные последовательности | Расстановок скобок]] достаточно много и их количество очень быстро растет. Точное количество всевозможных вариантов равно ''n''–ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 числу Каталана].
Однако, порядок в котором расставляются скобки между матрицами повлияет на количество арифметических операций, которые потребуются на вычисление ответа, или, другими словами, на ''эффективность''.

Например, предположим, что А = (10 × 30), B = (30 × 5), C = (5 × 60). Тогда:

:(''AB'')''C'' = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 операций
:''A''(''BC'') = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 операций.

Как мы видим, первый способ гораздо эффективней.

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

=== Перебор всех вариантов ===

В данной задаче нужно узнать минимальное количество операций (или минимальную стоимость), необходимых для перемножения матриц. Если перемножить только две матрицы, то можно осуществить это едиственным способом, следовательно минимальная стоимость — это стоимость перемножения этих двух матриц. В общем, можно найти минимальную стоимость используя следующий рекурсивный алгоритм:

* Взять последовательность матриц и разделить её на две части.
* Найти минимальную стоимость перемножения на каждой подпоследовательности.
* Сложить эти две стоимости и прибавить к этому стоимость перемножения двух получившихся матриц.
* Сделать это для каждой возможной позиции в последовательности, в которой она может быть разделена и взять минимум среди всех результатов.

Или другими словами, давайте обозначим через <tex>f(i, j)</tex> минимальное количество скалярных умножений для вычисления матрицы <tex>M_{i..j}</tex>, то получаем следующее рекуррентное соотношение:
<tex> f(i,j) = \left \{
\begin{array}{ll}
0, & i=j \\
min(f(i,k) + f(k+1,j) + p_{i-1}p_kp_j | i \le k < j) & i < j
\end{array}
\right.
</tex>

Объясняется оно просто: для того, чтобы найти произведение матриц <tex>M_{i..j}</tex> при i=j не нужно ничего делать — это и есть сама матрица <tex>M_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>M_{i..j}</tex> на матрицы <tex>M_{i..k}</tex> и <tex>M_{k+1..j}</tex>, ищем количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>M_{i..j}</tex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>M_{i..k}M_{k+1..j}</tex>). Считаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>M_i</tex> равен <tex>p_{i-1} \times p_i</tex>.

Чтобы привести пример, давайте вернемся к нашим матрицам. Если у нас есть четыре матрицы ''ABCD'', то мы посчитаем для (''A'')(''BCD''), (''AB'')(''CD''), и (''ABC'')(''D''), делая рекурсивные вызовы на отрезках ''ABC'', ''AB'', ''CD'', и ''BCD'', чтобы найти минимальную стоимость. Потом среди них выбираем лучший вариант. Так же, этот алгоритм дает не только минимальную стоимость, но и показывает наилучший способ перемножения матриц: нужно только сгрупировать тем же образом матрицы, каким дается нам минимальная стоимость.

Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей. Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета ''ABC'' и ''AB''. Но нахождение наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется ''n''–ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 числу Каталана], да плюс вычисление для каждой правильной скобочной последовательности ''затрат'' на перемножение (то есть <tex>O(n \cdot C_n)</tex>). 

=== Оптимизации динамическим программированием ===
Одно из простых решений — это ''мемоизация'' (или ленивые вычисления). Каждый раз, когда считаем минимальную стоимость перемножения определенной подпоследовательности, давайте запоминать ответ. Если мы когда либо захотим посчитать это ещё раз, то уже будет иметь ответ и не будем пересчитывать. Поскольку существует всего <tex>O(n^2)</tex> подотрезков, где <tex>n</tex> — это количество матриц, то память занимаемая программой будет не так велика. С помощью запоминания ответа мы уменьшили асимптотику алгоритма (перебор) с <tex>O(n \cdot C_n)</tex> до <tex>O(n^3)</tex>, что является достаточно эффективным для реальных приложений.

=== Восстановление ответа ===
С помощью вышеописанного алгоритма можно восстановить порядок, в котором нам необходимо перемножать матрицы, чтобы достичь минимального количества арифметических операций, затрачиваемых на вычисление ответа. Когда узнаем, как нам нужно разбить отрезок на два подотрезка, то при восстановлении ответа, то заключаем эти два подотрезка(последовательности матриц) в скобки и передаем получившийся ответ выше по рекурсии.

=== Псевдокод ===
<pre>

int dp[][];
int v[];
// dp[i][j] — меморизация на отрезке [i, j)
// Массив v[] — хранит все размеры матриц по порядку
// Так как у нас размеры соседних матриц по вертикали и горизонтали совпадают, то они занесены в этот массив однократно
int matrixChainMultiplication(int l, int r)
{
//l — включая в отрезок
//r — исключая из отрезка
if dp[l][r] == -1 //Если значение динамики не посчитано
if l == r - 1
dp[l][r] = 0; //Если у нас подотрезок длины 1, то количество операций для перемножения равно нулю
else
dp[l][r] = infinity;
for (int i = l + 1; i < r; i++)
dp[l][r] = min(dp[l][r], v[l] * v[i] * v[r - 1] + matrixChainMultiplication(l, i) + matrixChainMultiplication(i, r));
return dp[l][r];
}
</pre>

== Литература ==

* Английская википедиа [http://en.wikipedia.org/wiki/Matrix_chain_multiplication Matrix chain multiplication]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория:Динамическое_программирование]]

Динамика по поддеревьям

2012-12-19T20:09:45Z

Mihver1: Создана основа статьи.

TODO:
* Merge со статьей berkeley
* Добавить еще примеры
* Конспект с лекции. Добавить затронутые темы.

Дерево {{---}} очередная структура данных, на которой можно увидеть принцип разбиения решения на подзадачи. Представьте дерево <tex>T</tex> с <tex>n</tex> вершинами. Так как в поддеревья <tex>T</tex> входят все потомки корня, то поддеревьев в <tex>T</tex> ровно столько же, сколько и вершин (<tex>n</tex> в данном случае).
== Максимальное независимое множество в дереве ==

Если данный граф является деревом, то задача о независимом множестве эффективно решается методом [[динамическое программирование|динамического программирования]].

=== Оптимальная подструктура задачи ===

Структура дерева сама подсказывает решение задачи: Обозначим корнем дерева любую вершину и назовем её <tex>r</tex>. Пусть <tex>I(u)</tex> обозначает размер максимального независимого множества вершин поддерева, корнем которого является вершина <tex>u</tex>. Тогда ответом на задачу будет являться <tex>I(r)</tex>.

Нетрудно видеть, что если мы включаем вершину ''u'' в максимальное независимое множество, то его [[Мощность множества|мощность]] увеличивается на 1, но его детей мы брать не можем (так как они соединены ребром с вершиной ''u''); если же мы не включаем эту вершину, то мощность максимального независимого множества будет равна сумме размеров независимых множеств детей этой вершины. Остается только выбрать максимум из этих двух вариантов, чтобы получить решение задачи:
: <tex>I(u) = \max\left\{1\ +\ \sum_{\text{grandchild}\ w\ of\ u}I(w),\ \sum_{\text{child}\ w\ of\ u}I(w) \right\},</tex>
где grandchild обозначает всякого «внука» вершины, а child обозначает всякого потомка вершины.

=== Псевдокод ===
Считаем, что в вершине u хранится <tex>I(u)</tex>:

get_independent_set(Node u)
если I(u) уже посчитано, то возвратить I(u)
//мощность множества, которое можно получить, если не брать вершину u
children_sum = 0
//мощность множества, которое можно получить, если взять вершину u
grandchildren_sum = 0
//цикл по всем детям
for i := 1 to child_num do
children_sum = children_sum + get_independent_set(children[i])
//цикл по всем внукам
for i:= 1 to grandchildren_num
grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
//запоминаем, чтобы не персчитывать ещё раз
I(u) = max(1 + grandchildren_sum, children_sum)
возвратить I(u)

Вызов get_independent_set(''r'') даст ответ на задачу. Время выполнения алгоритма, очевидно, <tex>O(|V| + |E|)</tex>.