Метод динамічного програмування

Лекція 16

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

Будемо вважати що система може знаходитись у одному з множини станів S. Множина S = { s₁, s₂, … , s_m, …) - не обов’язково скінчена або злічена. З кожного стану система може переходити у новий стан під впливом деякої зовнішньої дії, що будемо називати керуванням. Позначимо множину можливих керувань у кожному стані s_i через N_i. Кожному керуванню u Î N_i відповідає стан g(u) Î S, у який система переходить під впливом керування u.

Нехай, i₀ - початковий стан системи. Вибір керування u₀ Î N₀ переводить систему у стан i₁ = g(u₀), вибір u₁ Î N₁ – у стан i₂ = g(u₁) і так далі. В результаті отримуємо послідовність

(i₀, u₀), (i₁, u₁), (i₂, u₂), … ,

де для усіх k u_k Î N_k і i_k+1 = g(u_k). Така послідовність називається траекторією процесу.

Позначимо через Т множину усіх можливих траекторій. Задача, що розглядається у динамічному програмуванні, формулюється таким чином.

На множині Т визначена функція F(t). Треба знайти траекторію t Î Т, на якій функція F досягає екстремуму.

Розглянемо припущення, які робляться у динамічному програмуванні, відносно функції F та множини траекторій Т. Якщо від траекторії t = ((i₀, u₀), (i₁, u₁), … , (i_k, u_k)) відокремити початкову пару (i₀, u₀), що позначається як head(t) і називається головою траекторії, то залишок траекторії tail(t), що називається хвостом траекторії, згідно з припущенням, можна розглядати як траекторію з початком у стані i₁ = g(u₀).

Якщо від траекторії tail(t) відокремити голову, то знов отримаємо траекторію. Оскільки таку операцію можна здійснювати довільну кількість разів, то можна зробити висновок, що будь-яка зв’язна частина траекторії, що містить останню пару, є траекторією.

Відносно початкової частини траекторії (зв’язної частини, що містить початкову пару (i₀, u₀)), також робиться припущення, що вона є траекторією. Таким чином, будь-яка зв’язна частина траекторії є траекторією.

Будемо вважати, що функція F задовольняє умові:

Якщо траекторія t Î Т має вигляд t = (head(t), tail(t)) = ( (i, u), t^’ ), то

F(t) = c (u) + b (u) x F( t^’ ). (16.1)

Функція, задовольняюча умові (16.1), називається рекурентною. Надалі будемо вважати, що b(u) ³ 0 для будь-якого u.