Задача поиска кратчайшего пути в сети

Одним из конкретных примеров применения задачи выбора траектории является задача определения кратчайшего пути в сети. В ней необходимо выбрать траекторию движения из одного пункта в другой таким образом, чтобы сумма значений на отрезках траектории между узлами была минимальна. Значения могут соответствовать времени движения по отрезку или длине отрезка. Такая задача решается в алгоритмах автомобильной компьютерной навигации, когда компьютер выбирает наиболее рациональный маршрут при движении, например, по городу из точки A в точку B в условиях его загруженности.

Рис. 15. Выбор траектории движения автомобиля в городе

Задача распознавания речи

Метод динамического программирования может использоваться для распознавания речи или голосовых команд, которые могут быть применены:

- при голосовом наборе номера в некоторых моделях мобильных телефонов;

- для восстановления речевых сообщений и команд, передаваемых по каналам голосовой связи с помехами, когда помехи могут сильно искажать команды;

- для идентификации человека по голосу;

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

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

В.В. Сычев (кафедра теории интеллектуальных систем МГУ им. Ломоносова, 1997 г., дипломная работа, представлена автором на сайте http://impb.psn.ru/~sychyov/) объясняет применение метода необходимостью внутреннего нелинейного выравнивания реализаций слов по времени. Действительно, темп, способ произнесения одного и того же слова могут различаться в реализациях (Рис. 16). Для выравнивания и используется метод динамического программирования – ищется наилучшее сопоставление из возможных.

Рис. 16. Выравнивание темпа слов методом динамического программирования

На рисунке показана оптимальная траектория, дающая наименьшую сумму расхождений между двумя произнесениями слова «метод». При этом в каждой клетке представлено расстояние между соответствующими звуками реализации. Одинаковые по звучанию звуки дают небольшие расхождения, разные – большие.

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

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