При использовании динамического программирования, фиксируя весь путь для минимальной суммы?

Question

Я пытаюсь использовать алгоритм минимальной суммы Viterbi, который пытается найти путь через кучу узлов, который минимизирует общее расстояние Хэмминга (причудливый термин для «xor two numbers и count the result bits») против некоторого фиксированного ввода.

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

Кажется, что memoizing путь на каждом узле будет действительно интенсивным в памяти. Существует ли стандартный способ решения этих проблем?

Edit:

http://i.imgur.com/EugiEWG.jpg

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

Как вы можете видеть, первый фрагмент моей строки ввода - 01, и я могу пересечь его в столбце 1 решетки. Следующий кусок - 10, и я могу перемещаться туда в колонке 2. Следующий фрагмент - 11. До сих пор. Следующий фрагмент - 10, что является проблемой, потому что я не могу дойти до этого состояния, откуда я сейчас, поэтому я должен перейти к следующей лучшей вещи (00), а остальное можно заполнить отлично.

Но это может усложниться. Мне нужно было бы как-то получить соответствующий путь к минимальному расстоянию Хэмминга.

(Пункт этого упражнения состоит в том, что решетка представляет собой ACTUALLY действительные переходы, тогда как входная строка - это то, что вы получаете через телекоммуникационную связь и можете получить искаженное и иметь неправильные биты здесь и там. Эта программа пытается выяснить, что входная строка ДОЛЖНА быть минимизирована).

Answer 1

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

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

Answer 2

Вы правы, что непосредственный подход к вычислению путей является пространством дорогостоящим.

Эта проблема возникает часто в DNA sequencing, где стоимость является запретительной. Есть несколько способов его преодоления (см больше here):

• Вы можете уменьшить до квадратного корня из пространства, если вы готовы удвоить время выполнения (см 2.1.1 в ссылке выше).

• Используя сжатое дерево, вы можете уменьшить одну из величин логарифмически (см. 2.1.2 в приведенной выше ссылке).