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

m[i,k]+m[k+1,j]+s[i-1]*s[k]*s[j] по всіх k=i+1, …, j-1

end

{m[1, n] – шукане значення }

Безпосередньо за алгоритмом неважко переконатися, що оцінкою його складності є O (n ³ ).-

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

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

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

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