Содержание
- 2. План лекции Понятие динамического программирования Примеры Сумма геометрической прогрессии Суммирование набора Задача о рюкзаке Произведение матриц
- 3. Понятие динамического программирования Ричард Беллман ~1940 Какой алгоритм назван в честь этого ученого? Описание процесса решения
- 4. Понятие динамического программирования Термин «динамическое программирование» происходит от термина «математическое программирование», который является синонимом слова «оптимизация»
- 5. Понятие динамического программирования Последовательность действий в Д.П. имеет вид Разбиение задачи на подзадачи меньшего размера Нахождение
- 6. Понятие динамического программирования Простая рекурсивная реализация будет расходовать время на вычисление решений для задач, которые уже
- 7. Понятие динамического программирования Динамическим программированием называется способ программирования, при котором задача разбивается на подзадачи, вычисление идет
- 8. Понятие динамического программирования Под подзадачей понимается та же постановка задачи, но с меньшим числом параметров или
- 9. Понятие динамического программирования Динамическое программирование может быть применено к задачам оптимизации, в которых решением является последовательность
- 10. Пример -- геометрическая прогрессия Рассмотрим пример. Требуется вычислить сумму s следующего ряда при x ≠ 0:
- 11. Пример – суммирование набора Имеется n неделимых предметов, вес i-го предмета есть wi Найти список предметов,
- 12. Пример – суммирование набора Начальные значения функции T T(0, j) = 0 при j ≥ 1
- 13. Пример – суммирование набора Для оптимального решения из двух возможных вариантов нужно выбрать наилучший i-ый предмет
- 14. Пример – суммирование набора W = 16 w1 = 4, w2 = 5, w3 = 3,
- 15. Пример – суммирование набора Обратный ход Решение нашего примера определяется T[5, 16] = 1 T[5, 16]
- 16. Задача о рюкзаке Определить наиболее ценную выборку из n предметов, подлежащих упаковке в рюкзак, вмещающий W
- 17. Пример -- задача о рюкзаке Если перебирать все возможные подмножества данного набора из n предметов, то
- 18. Пример -- задача о рюкзаке Обозначим через T(n, W) функцию, значение которой соответствует решению нашей задачи.
- 19. Пример -- задача о рюкзаке Для решения подзадачи, соответствующей функции T(i, j), рассмотрим два случая. i-ый
- 20. Пример -- задача о рюкзаке Для оптимального решения из двух возможных вариантов упаковки рюкзака нужно выбрать
- 21. Пример -- задача о рюкзаке W = 16, c1 = 5, w1 = 4; c2 =
- 22. Пример -- задача о рюкзаке Алгоритм обратного хода Требуется определить набор предметов, которые подлежат упаковке в
- 23. Пример -- задача о рюкзаке T[5, 16] = T[4, 16] -- 5-й предмет не кладем в
- 24. Пример -- задача о рюкзаке void print_item(int i, int j) { if (T[i][j]==0) return; // набор
- 25. Пример -- умножение матриц Рассмотрим вычисление произведения n матриц M = M1 x M2 x ...
- 26. Пример – умножение матриц Рассмотрим произведение матриц: М = M1 × М2 × М3 × М4
- 27. Пример -- умножение матриц Перебор с целью минимизировать число операций имеет экспоненциальную сложность. На первом этапе
- 28. M1 × М2 × М3 × М4 [10×20] [20×50] [50×1] [1× 100] Далее перейдем к решению
- 29. Пример -- умножение матриц Обозначим через tij минимальную сложность умножения цепочки матриц Mi × Мi+1 ×
- 30. Упражнение Задана строка, состоящая из вещественных чисел, разделенных арифметическими операциями Требуется расставить в строке скобки таким
- 31. Кратчайшие пути между всеми парами вершин Строим матрицу стоимостей: w(i, j), если ребро (i, j)∈E M[i,
- 32. Алгоритм Флойда-Уоршолла Обозначим через dij(k) стоимость кратчайшего пути из вершины с номером i в вершину с
- 33. Алгоритм Флойда-Уоршолла Floyd-Warshall(M, n) { D(0) ← M; for (k = 0; k for (i =
- 34. Заключение Понятие динамического программирования Примеры Сумма геометрической прогрессии Суммирование набора Задача о рюкзаке Произведение матриц Алгоритм
- 35. На какое минимальное количество квадратов можно разложить число n? 0 1 2 3 4 5 6
- 36. Алгоритм Ахо (редакционное расстояние) Пусть даны две строки S1 и S2. Необходимо за минимальное число допустимых
- 37. Заметим, что для преобразования пустой строки в строку длины j требуется j операций вставки, т.е. M
- 38. II) Пусть S1[i] ≠ S2[j]. Возможны два способа получения строки S2[0..j]. 1. Пусть из строки S1[0..i–1]
- 39. M (0, j) = j; M (i, 0) = i; M (i, j) = min (M
- 40. Пример S1 = ”abc”, S2 = ”aabddc” Построим таблицу M, нумерация строк и столбцов которой начинается
- 41. Обратный ход М[1,3] = 2, означает, что из строки “a” можно получить строку “aab”, используя две
- 42. Последовательность действий для примера Изначально текущим в строке S1 является последний символ –символ c. Так как
- 43. Отметим, что решений в данной задаче может быть несколько. Движение по таблице представлено ниже.
- 44. Итак, tij вычисляются в порядке возрастания разностей нижних индексов. Процесс начинается с вычисления tii для всех
- 45. Алгоритм for (i=0; i for (l=1; l for (i=0; i j = i + l; for
- 46. Задача "Divisibility“ 1999-2000 ACM NEERC (подключена в системе тестирования NSUTS в школьных тренировках) Consider an arbitrary
- 47. Задача "Gangsters" (подключена в системе тестирования NSUTS в школьных тренировках) N gangsters are going to a
- 48. Пример t = 1 2 3 4 5 6 S = 1 2 3 4 5
- 49. КОНЕЦ ЛЕКЦИИ
- 50. Разбиение чисел Разбиением называется представление натурального числа в виде суммы натуральных слагаемых, а сами слагаемые —
- 51. Исследования Эйлера Изучение функции p(n) Эйлер начинает с рассмотрения бесконечного произведения (1 + x + x2
- 52. d(n) = l(n) (теорема Эйлера) Обозначим через d(n) количество разбиений числа n на различные слагаемые, а
- 53. Изучая p(n), Эйлер сосредоточил внимание на произведении (1–x)(1–x2)(1–x3)... Раскрывая в нём скобки, Эйлер получил удивительный результат:
- 54. Пентагональная теорема: Используя ее: ( p(0) + p(1) x + p(2) x2 + ...)(1 – x
- 55. Решение (динамика) 1. 1 1 1 1 //исходный массив 2. 1 1 2 3. 1 3
- 56. const nmax=120; procedure Summ(N:integer); var List : array [0..nmax] of byte;{вспомогательный массив для хранения значений слагаемых}
- 57. x(m) разбиений натурального числа m Для решения исходной задачи перейдем к рассмотрению обобщенной задачи. Подсчитаем количество
- 58. P(m,n) = P(m,n-1) + P(m-n,n) (n Все разбиения m на сумму слагаемых, не превосходящих n, можно
- 59. Задача о телефонном номере (подключена в системе тестирования NSUTS в школьных тренировках) Если вы обратили внимание,
- 61. Скачать презентацию