Лекция 7

1. Динамическое программирование: расстояние редактирования

Алгоритмы и структуры данных (с примерами на языках Python и R)

2. Постановка задачи

3. Выравнивание

4. Выравнивание

5. Выравнивание

Рассмотрим последний столбец оптимального выравнивания строк
A[1 … n] и B [1 … m]:

6. Выравнивание

Рассмотрим последний столбец оптимального выравнивания строк
A[1 … n] и B [1 … m]:

7. Выравнивание

Рассмотрим последний столбец оптимального выравнивания строк
A[1 … n] и B [1 … m]:

8. Выравнивание

Рассмотрим последний столбец оптимального выравнивания строк
A[1 … n] и B [1 … m]:

9. Подзадача и рекуррентное соотношение

10. Динамическое программирование сверху вниз

11. Динамическое программирование сверху вниз

12. Время работы

13. Время работы

14. Заполнение таблицы

15. Заполнение таблицы

16. Динамическое программирование снизу вверх

17. Динамическое программирование снизу вверх

18. Пример

19. Пример

20. Восстановление решения

21. Восстановление решения (пример)

22. Восстановление решения (пример)

23. Уменьшение используемой памяти

24. Взвешенное расстояние редактирования

25. Обобщенное рекуррентное соотношение