7.7: Динамічне програмування

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

Почнемо з істотного поняття. Припустимо, що ми їдемо з точки А в точку С, і запитуємо, який найкоротший шлях в милі. Якщо A і C представляють Лос-Анджелес і Бостон, наприклад, є багато шляхів на вибір! Припустимо, що так чи інакше ми знайшли найкращий шлях, і що точка Б лежить вздовж цього шляху, скажімо, Лас-Вегас. \(X\)Дозволяти бути довільною точкою на схід від Лас-Вегаса. Якби ми зараз вирішили нову проблему оптимізації для того, щоб дістатися тільки з Лас-Вегаса до Бостона, ця ж довільна точка\(X\) була б уздовж нового оптимального шляху, а також.

Справа тонка: проблема оптимізації від Лас-Вегаса до Бостона простіше, ніж від Лос-Анджелеса до Бостона, і ідея полягає в тому, щоб використовувати цю властивість назад через час, щоб розвивати оптимальний шлях, починаючи з Бостона.

Малюнок\(\PageIndex{1}\): візуалізація прикладної задачі безпосередньо нижче. \(s=2\), Тобто є два шари вузлів (Скелясті гори і річка Міссісіпі)\(n=3\), і, тобто є три вузли або локації, де можна перетнути кожну з цих перешкод.

Приклад: Вузлові подорожі. Тепер ми додаємо деяку структуру до вищевказаного експерименту. Розглянемо тепер подорож з точки А (Лос-Анджелес) до точки D (Бостон). Припустимо, є лише три місця, щоб перетнути Скелясті гори\(B_1, \, B_2, \, B_3\), і три місця, щоб перетнути річку Міссісіпі,\(C_1, \, C_2, \, C_3\). За способом позначення ми говоримо, що шлях від\(A\) до\(B_1\) є\(AB_1\). Припустимо, що всі шляхи (і відстані) від\(A\) до\(B\) -вузлів відомі, як і ті, від\(B\) -nodes до\(C\) -nodes, і\(C\) -nodes до кінцевої точки\(D\). Є дев'ять унікальних шляхів від\(A\) до\(D\).

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

Підхід до динамічного програмування має два етапи. Спочатку з кожного\(B\) -вузла виберіть найкращий шлях до\(D\). Існує три можливі шляхи від\(B_1\) до\(D\), наприклад, і дев'ять шляхів загалом від\(B\) -рівня до\(D\). Зберігайте найкращі шляхи як\(B_1 D|_{opt}, \, B_2 D|_{opt}, \, B_3 D|_{opt}\). Ця операція передбачає дев'ять складання двох чисел. По-друге, обчислити відстань для кожного з можливих шляхів від\(A\) до\(D\), обмежених оптимальними шляхами від\(B\) -вузлів далі:\(A B_1 + B_1 D|_{opt}, \, A B_2 + B_2 D|_{opt},\) або\(A B_3 + B_3 D|_{opt}\). Комбінований шлях з найкоротшою відстанню є загальним рішенням; цей другий крок включає три суми двох чисел, а загальна оптимізація проводиться у дванадцяти складаннях двох чисел.

Зайве говорити, що цей приклад дає лише м'яку перевагу динамічному підходу до програмування над грубою силою. Однак зазор значно розширюється, оскільки збільшується розміри простору розчину. Загалом, якщо є\(s\) шари вузлів (наприклад, річки або гірські хребти), і кожен має ширину\(n\) (наприклад, точки перетину\(n\) річок), підхід грубої сили буде приймати\(s n^s\) доповнення, тоді як процедура динамічного програмування включає лише\(n^2(s-1)+n)\) доповнення. У разі\(n=5, \, s=5\), груба сила вимагає\(15625\) доповнень; динамічне програмування потрібно тільки\(105\)!