WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Метод розгалужень і меж. Евристичні алгоритми. Застосування принципу оптимальності - Реферат

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

чималу групу задач, які розв'язуються методом розгалужень і меж. Подивимося на цю задачу більш узагальнено. Розподіл (повний чи частковий) v(i)= подамо як послідовність , де aj позначає пару (j; kj). Очевидно, що v(i) одержується з v(i-1) додаванням компонента ai. Вартість розподілу при цьому не зменшується, тобто
C(v(i-1)) C(v(i)). (19.1)
Існує чимало задач, в яких розв'язок-послідовність будується шляхом "нарощування" часткових розв'язків новими компонентами ai. Умова (19.1) дозволяє відкидати ті часткові розв'язки та всіх їх нащадків, якщо їх вартість не може бути меншою вартості Cmin уже побудованого повного розв'язку. Таким чином, Cmin виступає верхньою межею для вартості розв'язків, які є сенс будувати. Але, як правило, обчислити вартість повного розв'язку можна лише після його побудови. Для запобігання побудови всіх повних розв'язків треба мати можливість оцінювати знизу їх вартість за вартістю побудованих часткових. Чим точнішою буде така оцінка, тим ефективнішим буде скорочення перебору.
Отже, алгоритм розв'язання багатьох задач за методом розгалужень і меж має таку загальну структуру:
Для кожного можливого a1 занести до черги частковий розв'язок
;
Обчислити нижню оцінку E вартості його нащадків, що є
повними розв'язками;
Cmin:= ;
while (черга не порожня) and (її перший елемент має оцінку E1. Занумеруємо клітини кожного кільця числами від 0 до n-1. Позначимо через Cki число, записане в клітині з номером i у кільці k, а через Ski - найбільшу суму, яку можна набрати на шляху, що веде в цю клітину. Очевидно, що S1i =C1i. Для початку обчислимо для кожної клітини другого кільця найбільшу суму S2i на шляху довжини 2. За умовою задачі очевидно, що
S2i=C2i+max{S1, i-1, S1i, S1, i+1} за i=1, … , n-2,
S20=C20+max{S1, n-1, S10, S11}, S2,n-1=C2, n-1+max{S1, n-2, S1, n-1, S10}.
За цими сумами можна аналогічно підрахувати суми для клітин третього кільця. Так само при переході до четвертого кільця достатньо знати лише найбільші суми для клітин третього кільця тощо. Діставши суми для клітин останнього кільця, вибираємо найбільшу з них, і задачу розв'язано.
Уточнення алгоритму залишаємо вправою. Скажемо лише, що суми Ski, k=2, … , m, i=0, … , n-1, обчислюються за єдиною формулою
Ski=Cki+max{Sk-1, (i-1+n) mod n, Sk-1, i, Sk-1, (i+1) mod n}.
Оцінимо складність наведеного алгоритму. Очевидно, що при переході на наступне кільце обчислюються n сум за сталу кількість дій кожна. Таких переходів відбувається m-1, тому загальна кількість дій оцінюється як O(nm).Р
У наведених обчисленнях сум ми керувалися правилом: при переході на наступне кільце неважливо, якими були шляхи до клітин попереднього кільця. Аби вони давали найбільші суми, можливі для їх кінцевих клітин. Ішими словами, вибір шляхів від клітин попереднього кільця в клітини наступного не залежить від того, як саме ми вибирали клітини раніше.
Наведене правило є окремим конкретним випадком принципу оптимальності, одного з головних у теорії динамічного програмування. Її автор, Р.Беллман, сформулював цей принцип так:
"Оптимальна поведінка має таку властивість, що, якими б не були початковий стан і рішення в початковий момент, наступні рішення повинні складати оптимальну поведінку відносно стану, який одержується в результаті першого рішення."
Обсяг книжки не дозволяє викладати тут теорію динамічного програмування. Вона велика й серйозна. Наведемо натомість ще один приклад застосування принципу оптимальності.
Приклад 3. Розглянемо обчислення добутку n матриць
A = A1 A2 … An,
де кожна Ai - матриця з si-1 рядками та si стовпцями. Як відомо, операція множення матриць є асоціативною, і результат не залежить від порядку її застосування. Але від нього залежить кількість множень їх елементів.
За традиційним алгоритмом множення матриць розмірами a b та b c відбувається abc множень їх елементів. Наприклад, множення матриць A1 A2 A3 розмірами 100 1, 1 100, 100 1 відповідно у порядку (A1 A2) A3 вимагає 100 1 100+100 100 1=20000 множень, тоді як у порядку A1 (A2 A3) - лише 1 100 1+100 1 1=200, тобто в 100 разів менше.
Отже, за послідовністю розмірів матриць s0, s1, s2, … , sn треба обчислити найменшу кількість множень їх елементів, необхідних для обчислення добутку матриць A = A1 A2 … An.
Очевидно, що при обчисленні добутку останнім виконується одне з множень, тобто A=(A1 … Ai) (Ai+1 … An), де 1 i n-1. Якщо добутки A1 … Ai та Ai+1 … An обчислено, то виконання останнього множення вимагає s0 si sn множень. Позначимо mik мінімальну кількість множень, необхідних для обчислення Ai Ai+1 … Ak за im1n = {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-повні задачі. Обсяг і характер цієї книжки не дозволяють розпочинати знайомство з ними, тому зацікавлений читач може подивитися в книги [АХУ, РНД, ГД].
Loading...

 
 

Цікаве