Сторінка
5
m1n =
{m1i+mi+1,n+s0× si× sn} Отже, задача відшукання m1n, тобто задача розміру n, зводиться до 2(n-2) задач меншого розміру. Але головним тут є той факт, що числа m1i та mi+1,n не залежать одне від одного, тобто найменша кількість множень при обчисленні добутку A1´ …´ Ai не залежить від того, як обчислюється добуток Ai+1´ …´ An, і навпаки. Завдяки саме цій незалежності можна застосувати принцип оптимальності. Спочатку обчислимо всі mi,i+1 за i=1, … , n-1. Очевидно, mi,i+1=si-1× si× si+1. Запам'ятавши їх, обчислимо mi,i+2і також запам'ятаємо. Потім обчислимо всі mi,i+3 тощо, збільшуючи різницю d між другим та першим індексами, поки не дійдемо до m1n. При цьому ми обчислюємо mij за формулою
mij =
{mik+mk+1,j+si-1× sk× sj} Наведений алгоритм уточнюється таким чином: for i:=1 to n-1 do m[i, i+1]:=s[i-1]*s[i]*s[i+1]; for d:=1 to n-1 do for i:=1 to n-d do begin j:=i+d; У m[i, j] запам'ятати мінімальне зі значень
m[i,k]+m[k+1,j]+s[i-1]*s[k]*s[j] по всіх k=i+1, …, j-1
end {m[1, n] – шукане значення} Безпосередньо за алгоритмом неважко переконатися, що оцінкою його складності є O(n3).ç Підіб'ємо підсумок. В обох прикладах ми будували послідовності – шляхи на циліндрі або послідовності дужок. Характерним для них є те, що, кажучи неформально, коли зафіксовано якийсь компонент у їх середині, то оптимальний вибір компонентів у початку не впливає на оптимальний вибір у кінці, і навпаки. Саме ця незалежність позбавляє необхідності перебирати всі можливі послідовності і забезпечує складність наведених алгоритмів порядку O(mn) та O(n3) відповідно. У задачі про три станки такої незалежності рішень на початку їх послідовності та в її кінці немає. Саме це змушує перебирати всі можливі послідовності та зумовлює незастосовність принципу оптимальності. Для цієї задачі немає алгоритмів, які б дозволяли будувати розв'язок із незалежних частин подібно до задачі про добуток матриць. Існує величезний клас задач, розв'язки яких є послідовностями заданого вигляду, причому їх початок і кінець взаємозалежні. Для таких задач побудовано алгоритми складності не менше O(2n), де n – це величина, що характеризує розмір вхідних даних задачі. Але для них досі не побудовано алгоритмів, складність яких можна було б оцінити поліноміальною функцією від n. Поки що не доведено, що таких алгоритмів узагалі не можна побудувати, але саме до такої думки схиляються майже всі, хто мав справу з цими задачами. Серед задач, розв'язок яких будується перебиранням варіантів, виділяються так звані NP-складні та NP-повні задачі. Обсяг і характер цієї книжки не дозволяють розпочинати знайомство з ними, тому зацікавлений читач може подивитися в книги [АХУ, РНД, ГД].
Завантажити реферат