Метод розгалужень і меж. Евристичні алгоритми. Застосування принципу оптимальності, Детальна інформація

За традиційним алгоритмом множення матриць розмірами a\xF0B4 b та b\xF0B4 c відбувається abc множень їх елементів. Наприклад, множення матриць A1\xF0B4 A2\xF0B4 A3 розмірами 100\xF0B4 1, 1\xF0B4 100, 100\xF0B4 1 відповідно у порядку (A1\xF0B4 A2)\xF0B4 A3 вимагає 100\xF0D7 1\xF0D7 100+100\xF0D7 100\xF0D7 1=20000 множень, тоді як у порядку A1\xF0B4 (A2\xF0B4 A3) – лише 1\xF0D7 100\xF0D7 1+100\xF0D7 1\xF0D7 1=200, тобто в 100 разів менше.

Отже, за послідовністю розмірів матриць s0, s1, s2, … , sn треба обчислити найменшу кількість множень їх елементів, необхідних для обчислення добутку матриць A = A1 \xF0B4 A2 \xF0B4 … \xF0B4 An.

Очевидно, що при обчисленні добутку останнім виконується одне з множень, тобто A=(A1\xF0B4 …\xF0B4 Ai)\xF0B4 (Ai+1\xF0B4 …\xF0B4 An), де 1\xF0A3 i\xF0A3 n-1. Якщо добутки A1\xF0B4 …\xF0B4 Ai та Ai+1\xF0B4 …\xF0B4 An обчислено, то виконання останнього множення вимагає s0\xF0D7 si\xF0D7 sn множень. Позначимо mik мінімальну кількість множень, необхідних для обчислення Ai\xF0B4 Ai+1\xF0B4 …\xF0B4 Ak за i
{m1i+mi+1,n+s0\xF0D7 si\xF0D7 sn}

Отже, задача відшукання m1n, тобто задача розміру n, зводиться до 2(n-2) задач меншого розміру. Але головним тут є той факт, що числа m1i та mi+1,n

не залежать одне від одного, тобто найменша кількість множень при обчисленні добутку A1\xF0B4 …\xF0B4 Ai не залежить від того, як обчислюється добуток Ai+1\xF0B4 …\xF0B4 An, і навпаки. Завдяки саме цій незалежності можна застосувати принцип оптимальності.

Спочатку обчислимо всі mi,i+1 за i=1, … , n-1. Очевидно, mi,i+1=si-1\xF0D7 si\xF0D7 si+1. Запам'ятавши їх, обчислимо mi,i+2 і також запам'ятаємо. Потім обчислимо всі mi,i+3 тощо, збільшуючи різницю d між другим та першим індексами, поки не дійдемо до m1n. При цьому ми обчислюємо mij за формулою

{mik+mk+1,j+si-1\xF0D7 sk\xF0D7 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).\xF0E7

Підіб'ємо підсумок. В обох прикладах ми будували послідовності – шляхи на циліндрі або послідовності дужок. Характерним для них є те, що, кажучи неформально, коли зафіксовано якийсь компонент у їх середині, то оптимальний вибір компонентів у початку не впливає на оптимальний вибір у кінці, і навпаки. Саме ця незалежність позбавляє необхідності перебирати всі можливі послідовності і забезпечує складність наведених алгоритмів порядку O(mn) та O(n3) відповідно.

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

Існує величезний клас задач, розв'язки яких є послідовностями заданого вигляду, причому їх початок і кінець взаємозалежні. Для таких задач побудовано алгоритми складності не менше O(2n), де n – це величина, що характеризує розмір вхідних даних задачі. Але для них досі не побудовано алгоритмів, складність яких можна було б оцінити поліноміальною функцією від n. Поки що не доведено, що таких алгоритмів узагалі не можна побудувати, але саме до такої думки схиляються майже всі, хто мав справу з цими задачами.

Серед задач, розв'язок яких будується перебиранням варіантів, виділяються так звані NP-складні та NP-повні задачі. Обсяг і характер цієї книжки не дозволяють розпочинати знайомство з ними, тому зацікавлений читач може подивитися в книги [АХУ, РНД, ГД].