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

Приклад 2. Нехай паперовий прямокутник складено з клітин – m по вертикалі та n по горизонталі. У кожній клітині записано натуральне число. Уявімо, що з прямокутника зробили вертикальний циліндр, з'єднавши першу та останню вертикалі. Ми можемо рухатися по клітинах циліндра та підраховувати суму чисел у них. Рух починається з будь-якої клітини першого кільця. Далі, якщо ми перебуваємо в якійсь клітині, то можемо перейти на наступне кільце в одну з тих трьох клітин, що мають спільні точки з поточною. Рух закінчується на останньому, m -му кільці клітин. Треба обчислити найбільшу суму, яку можна набрати на одному з можливих шляхів довжини m .

Якщо m =1, то достатньо вибрати клітину з найбільшим числом. Нехай m >1. Занумеруємо клітини кожного кільця числами від 0 до n -1. Позначимо через C_ki число, записане в клітині з номером i у кільці k , а через S_ki – найбільшу суму, яку можна набрати на шляху, що веде в цю клітину. Очевидно, що S _1i =C _1i . Для початку обчислимо для кожної клітини другого кільця найбільшу суму S _2i на шляху довжини 2. За умовою задачі очевидно, що

S _2i =C_2i +max{S _{1, i -1} , S _1i , S _{1, i +1} } за i =1, … , n -2,

S ₂₀ =C ₂₀ +max{S _{1, n -1} , S ₁₀ , S ₁₁ }, S _{2,n -1} =C _{2, n -1} +max{S _{1, n -2} , S _{1, n -1} , S ₁₀ }.

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

Уточнення алгоритму залишаємо вправою. Скажемо лише, що суми S_ki , k =2, … , m , i =0, … , n -1, обчислюються за єдиною формулою

S_ki =C_ki +max{S_{k -1, (i -1+n ) mod n} , S_{k -1, i} , S_{k -1, (i +1) mod n} }.

Оцінимо складність наведеного алгоритму. Очевидно, що при переході на наступне кільце обчислюються n сум за сталу кількість дій кожна. Таких переходів відбувається m -1, тому загальна кількість дій оцінюється як O (nm ).-

У наведених обчисленнях сум ми керувалися правилом: при переході на наступне кільце неважливо, якими були шляхи до клітин попереднього кільця . Аби вони давали найбільші суми, можливі для їх кінцевих клітин . Ішими словами, вибір шляхів від клітин попереднього кільця в клітини наступного не залежить від того, як саме ми вибирали клітини раніше .

Наведене правило є окремим конкретним випадком принципу оптимальності , одного з головних у теорії динамічного програмування . Її автор, Р.Беллман, сформулював цей принцип так:

"Оптимальна поведінка має таку властивість, що, якими б не були початковий стан і рішення в початковий момент, наступні рішення повинні складати оптимальну поведінку відносно стану, який одержується в результаті першого рішення ."

Обсяг книжки не дозволяє викладати тут теорію динамічного програмування. Вона велика й серйозна. Наведемо натомість ще один приклад застосування принципу оптимальності.

Приклад 3. Розглянемо обчислення добутку n матриць

A = A _{1 ´} A _{2 ´} … ´A_n ,

де кожна A_i – матриця з s_{i -1} рядками та s_i стовпцями. Як відомо, операція множення матриць є асоціативною, і результат не залежить від порядку її застосування. Але від нього залежить кількість множень їх елементів.

За традиційним алгоритмом множення матриць розмірами a ´ b та b ´ c відбувається abc множень їх елементів. Наприклад, множення матриць A _{1 ´} A _{2 ´} A ₃ розмірами 100´ 1, 1´ 100, 100´ 1 відповідно у порядку (A _{1 ´} A ₂ )´A ₃ вимагає 100× 1× 100+100× 100× 1=20000 множень, тоді як у порядку A _{1 ´} (A _{2 ´} A ₃ ) – лише 1× 100× 1+100× 1× 1=200, тобто в 100 разів менше.

Отже, за послідовністю розмірів матриць s ₀ , s ₁ , s ₂ , … , s_n треба обчислити найменшу кількість множень їх елементів, необхідних для обчислення добутку матриць A = A _{1 ´} A _{2 ´} … ´A_n .

Очевидно, що при обчисленні добутку останнім виконується одне з множень, тобто A =(A _{1 ´} …´A_i )´ (A_{i +1 ´} …´A_n ), де 1£i £ n -1. Якщо добутки A _{1 ´} …´A_i та A_{i +1 ´} …´A_n обчислено, то виконання останнього множення вимагає s _{0 ×} s_{i ×} s_n множень. Позначимо m_ik мінімальну кількість множень, необхідних для обчислення A_{i ´} A_{i +1 ´} …´A_k за i <k , m_ii =0. Тоді шукана кількість

m _1n ={m _1i +m_{i +1,n} +s _{0 ×} s_{i ×} s_n }

Отже, задача відшукання m _1n , тобто задача розміру n , зводиться до 2(n -2) задач меншого розміру. Але головним тут є той факт, що числа m _1i та m_{i +1,n}

не залежать одне від одного, тобто найменша кількість множень при обчисленні добутку A _{1 ´} …´A_i не залежить від того, як обчислюється добуток A_{i +1 ´} …´A_n , і навпаки. Завдяки саме цій незалежності можна застосувати принцип оптимальності .

Спочатку обчислимо всі m_{i ,i +1} за i =1, … , n -1. Очевидно, m_{i ,i +1} =s_{i -1 ×} s_{i ×} s_{i +1} . Запам'ятавши їх, обчислимо m_{i ,i +2} і також запам'ятаємо. Потім обчислимо всі m_{i ,i +3} тощо, збільшуючи різницю d між другим та першим індексами, поки не дійдемо до m _1n . При цьому ми обчислюємо m_ij за формулою

m_ij ={m_ik +m_{k +1,j} +s_{i -1 ×} s_{k ×} s_j }

Наведений алгоритм уточнюється таким чином:

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;