48
правок
Изменения
Нет описания правки
== Принцип оптимальности на подотрезках==
Пусть нужно посчитать функцию f(i, j). Принцип состоит в том, что мы пересчитываем f(i, j) через такие f(i1, j1), что i <= i1 <= j1 <= j. Для примера рассмотрим следующую задачу: пусть дан ориентированный взвешенный ациклический граф без кратных ребер, где вес ребер <math> \in Z </math>. Требуется найти кратчайший путь от каждой вершины до каждой. Пусть вершины пронумерованы в порядке топологической сортировки и d(i, j) - ответ на задачу. Ясно, что d(i, i) = 0 и d(i, j) = infinity, если не существует путь от i до j. Пусть нам требуется посчитать путь от вершины i до j, при чем чем для любого k (k = [i..j]), d(i, k) и d(k, j) посчитаны, тогда: <br />
: <tex> d(i, j) = \min\limits_{\mathop{k:i \rightsquigarrow k \rightsquigarrow j}} (d(i, k) + d(k, j)) </tex>
=== Примеры задач ===
:* [[Задача о расстановке знаков в выражении ]]
==Ссылки==
