|
|
Главный принцип ДП - принцип оптимальности. Сформулированный Р. Беллманом принцип оптимальности гласит: отрезок оптимального процесса от любой его точки до конца процесса сам является оптимальным процессом с началом в данной точке. Это означает - что неважно каким образом система пришла в данное состояние, что упрощает поиск оптимального пути.
Витерби - это поиск кратчайшего пути по однонаправленному графу специального вида (поиск правильной битовой последовательности с наименьшим хемминговым или эвклидовым расстоянием к полученной "подпорченной" последовательности). Задача решается за два прогона, как большинство задач ДП - прямая прогонка - поиск оптимальных решений для всех возможных стартовых состояний и обратная прогонка - поиск оптимального пути при известном конечном состоянии.
Вообще декодирование сверточных кодов элементарно решается методом перебора всех вариантов (что легко но ОЧЕНЬ ресурсоемко). ДП это метод отсечения неоптимальных решений на ранних стадиях решения.
Если хотите углубить знания по ДП, то читать надо любой учебник по исследованию операций (Таха, Вентцель и т.д.) Если интересует Витерби - от есть простой туториал "для чайников", правда на англицком http://www.complextoreal.com/tutorial.htm
E-mail: 
info@telesys.ru
