Реферат на тему: «ДИНАМІЧНЕ ПРОГРАМУВАННЯ»

Зміст

 

Вступ    3

1.    Загальна характеристика методу    4

2. Знаходження найкоротших шляхів    9

3. Транзитивне замикання бінарного відношення    13

4. Задача обчислення добутку матриць    14

Список використаних джерел    17

 

Вступ

Динамічне програмування – розділ математики, який присвячено теорії і методам розв’язання багатокрокових задач оптимального керування.

У динамічному програмуванні для керованого процесу серед множини усіх допустимих керувань шукають оптимальне у сенсі деякого критерію тобто таке яке призводить до екстремального (найбільшого або найменшого) значення цільової функції – деякої числової характеристики процесу. Під багатоступеневістю розуміють або багатоступеневу структуру процесу, або розподілення керування на ряд послідовних етапів (ступенів, кроків), що відповідають, як правило, різним моментам часу. Таким чином, в назві “Динамічне програмування” під “програмуванням” розуміють “прийняття рішень”, “планування”, а слово “динамічне” вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.

Методи динамічного програмування є складовою частиною методів, які використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв’язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)

Методи динамічного програмування використовуються не лише в дискретних, але і в неперервних керованих процесах, наприклад, в таких процесах, коли в кожен момент певного інтервалу часу необхідно приймати рішення. Динамічне програмування також дало новий підхід до задач варіаційного числення.

Хоча метод динамічного програмування суттєво спрощує вихідні задачі, та безпосереднє його використання, як правило, пов’язане з громіздкими обчисленнями. Для подолання цих труднощів розробляються наближені методи динамічного програмування.

  1. Загальна характеристика методу

Розглянемо метод розв’язання задач, побудований за схемою послідовного аналізу варіантів, тобто з використанням процедур, які на основі побічних оцінок відкидають усі допустимі розв’язання, серед яких не може бути оптимального. З часом відбувається поступове стиснення множини конкурентоспроможних варіантів. Наприкінці залишаються один або два варіанти, які й порівнюють.

Перетворити цей загальний підхід у систему формальних процедур дуже важко. Нині багато зроблено в цьому напрямі. Перші ідеї належать А. А. Маркову, їх розвивали американці Д. Вальд, Р. Айзекс, Р. Беллман. Значний внесок у створення загального формалізму послідовного аналізу варіантів (схема формалізації Михалевича, метод «київський віник») належить київській школі математиків на чолі з В. С. Михалевичем.

Методи динамічної оптимізації значною мірою використовують глибоке знання сутностей задач розв’язання. Аналогічно методу РП задачу розбивають на підзадачі. Останні розв’язують, а з отриманих підрозв’язків будують загальний розв’язок. Підзадачі залежні між собою, тобто у них є загальні підпідзадачі. Алгоритми динамічного програмування розв’язуватимуть кожну із підзадач тільки один раз, запам’ятовуючи отримані розв’язки у вигляді спеціальних таблиць. Тому тут ми звернемо увагу не на загальну методологію підходу, а обмежимося розглядом декількох задач, які досить повно ілюструють загальні концепції підходу.

Динамічне програмування
це алгоритмічний метод, який використовують, коли шуканий розв’язок задачі можна зобразити як об’єднання деяких результатів оптимальних розв’язків певних підзадач, що трапляються в різних гілках побудови загального розв’язання і обраховуватимуться тільки один раз.

Наприклад, розв’язання задачі про збирання туристичного рюкзака можна розглядати так. Для знаходження значення xi, 1 i n, потрібно знайти розв’язки x1, x2, x3 і т. д. Оптимальна послідовність цих розв’язків має максимізувати цільову функцію
та задовольняти умовам
i 0
xi
1.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Dynamichne Programuv (148.0 KiB, Завантажень: 23)

Сторінка: 1 2 3 4 5
завантаження...
WordPress: 23.31MB | MySQL:26 | 0,350sec