Всегда ли DP можно представить в виде DAG?

Question

[floppa322]

Прочитав SO, слегка запутался, хотя до этого всегда думал, что можно, ведь если нельзя, то есть цикл, а значит есть вершины, завясящие от цикла, а значит они не вычислимы и невычислима сама исходная задача

Answer 1

[Wataru]

Тут вопрос определений. Что считать "представить в виде DAG".

В ДП можно составить граф зависимостей: какие состояния участвуют в вычислении каждого. Это будет DAG. Иначе у вас надо вычислять значения через самих себя и у вас уже не рекуррентные соотношения, а система уравнений.
В некоторых задачах эту систему уравнений можно решать иерархически, по частям, отдельно в каждой компоненте сильной связности. Это немного напоминает ДП, но им не является. Суть ДП в том, что у вас рекуррентные формулы. Это некий более общий алгоритм.

Если интерпретировать вопрос как: можно ли сформулировать задачу в виде "дан граф, подсчитать вот такую функцию в каждой вершине", то тут можно натянтуть сову на глобус, придраться к деталям и сказать, что нельзя. Именно это и говорится в SO.

Потому что иногда рекуррентные формулы не симметричные и вам надо, например, одно значение прибавить, другое вычесть. Это не всегда просто определить исключительно в терминах графа. Нельзя сказать что-то вроде "сложить значение во всех вершинах, куда ведут ребра". Но если добавить в этот граф пометки на ребрах или параметры состояний в вершинах, то можно задать нужную функцию (вроде: взять значение для вершины, в которую ведет ребро с пометкой 1 и вычесть значение из вершины, куда ведет ребро с пометкой 2).

Но эти помеченные графы все еще будут DAG.

Comments

[floppa322]

Спасибо за ответ

В ДП можно составить граф зависимостей: какие состояния участвуют в вычислении каждого. Это будет DAG. Иначе у вас надо вычислять значения через самих себя и у вас уже не рекуррентные соотношения, а система уравнений.
В некоторых задачах эту систему уравнений можно решать иерархически, по частям, отдельно в каждой компоненте сильной связности. Это немного напоминает ДП, но им не является. Суть ДП в том, что у вас рекуррентные формулы. Это некий более общий алгоритм.

Как-то сталкивался с задачей, где были циклы, но небольшие, компоненты сильной связности были не больше 10 вершин, решались полным перебором, в итоге сворачивались к одной оптимальной вершине и уже потом запускалось дп

Тут вопрос определений. Что считать "представить в виде DAG".

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

Потому что иногда рекуррентные формулы не симметричные и вам надо, например, одно значение прибавить, другое вычесть. Это не всегда просто определить исключительно в терминах графа. Нельзя сказать что-то вроде "сложить значение во всех вершинах, куда ведут ребра". Но если добавить в этот граф пометки на ребрах или параметры состояний в вершинах, то можно задать нужную функцию (вроде: взять значение для вершины, в которую ведет ребро с пометкой 1 и вычесть значение из вершины, куда ведет ребро с пометкой 2).

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

[Wataru]

floppa322,

Если я правильно понял о чём идёт речь, то можно рассуждать следующим образом

Да, в таком смысле так.

Как-то сталкивался с задачей, где были циклы, но небольшие, компоненты сильной связности были не больше 10

Тут принципиальная разница, ибо какая бы у вас формула не была и каким бы не был граф, пока граф ациклический, у вас работает один и тот же алгоритм. Можно универсальный солвер написать, который принимает граф ифункцию. Он и называется ДП. Если же есть циклы, то там уже в зависимости от конкретной формулы и формы циклов будет свой уникальный алгоритм решения. Поэтому эти решения некороректно считать ДП.

[floppa322]

Wataru, ну если дп называть структуру мемоизации + функцию, то да. Но тут так было названо, просто потому что когда что-то такое решаешь, то контекст в голове именно про дп (хотя и состоящее не только из этапов характерных для дп (вроде вычисления конденсации графа))