Перекрывающиеся подзадачи в динамическом программировании с битовой маской

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

Гамильтоново блуждание — это место, где мы посещаем each and every node на графике exactly once.

Эту проблему можно решить, используя DP Bitmasks для небольшого количества узлов. Итак, что мы делаем, так это сохраняем Bitmask, чтобы отслеживать, какие узлы мы посетили в текущем состоянии, а затем мы можем перебирать все непосещенные узлы, используя mask, мы можем переходить в разные состояния.

Теперь предположим, что подзадача, скажем, из k узлов не вычислена, это решение из k узлов состоит из меньших подзадач, которые образуют большее решение из k узлов, т.е. первоначальное решение имело только 2 узла, затем 3 и так далее, когда мы достигли kth узел.

Теперь давайте возьмем еще одну подзадачу, состоящую, скажем, из m узлов, которые также существуют.

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

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

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

Я не совсем уверен, что это то, о чем вы спрашиваете. Но пример, который, к сожалению, не относится к области проблем маскирования битов, может быть фактическим примером для новичков в DP: последовательность Фибоначчи.

Как вы, наверное, знаете, последовательность Фибоначчи определяется примерно следующим образом.

F(n) = F(n-1) + F(n-2)
F(0) = F(1) = 1

Теперь предположим, что вы хотели найти F(8). Тогда вы на самом деле ищете F (7) + F (6). Чтобы найти F(7), вам нужны F(6) и F(5). А чтобы найти F(6), нужны F(5) и F(4).

Как видите, и F(6), и F(7) требуют решения F(5), что означает, что они перекрываются. Между прочим, F(7) также требует решения всей задачи F(6), но это не обязательно всегда так для каждой задачи DP. По сути, иногда ваши подзадачи A и B могут зависеть от подзадачи более низкого уровня C, и в этом случае они считаются перекрывающимися.