Сторінка
4
C(v(i-1))£ C(v(i)). (19.1) Існує чимало задач, в яких розв'язок-послідовність <a1, a2, … , an> будується шляхом "нарощування" часткових розв'язків <a1, a2, … , ai-1> новими компонентами ai. Умова (19.1) дозволяє відкидати ті часткові розв'язки та всіх їх нащадків, якщо їх вартість не може бути меншою вартості Cmin уже побудованого повного розв'язку. Таким чином, Cmin виступає верхньою межею для вартості розв'язків, які є сенс будувати. Але, як правило, обчислити вартість повного розв'язку можна лише після його побудови. Для запобігання побудови всіх повних розв'язків треба мати можливість оцінювати знизу їх вартість за вартістю побудованих часткових. Чим точнішою буде така оцінка, тим ефективнішим буде скорочення перебору. Отже, алгоритм розв'язання багатьох задач за методом розгалужень і меж має таку загальну структуру: Для кожного можливого a1 занести до черги частковий розв'язок
<a1>; Обчислити нижню оцінку E вартості його нащадків, що є
повними розв'язками; Cmin:=¥ ; while (черга не порожня) and (її перший елемент має оцінку E<Cmin)
do begin Вилучити з черги її перший елемент Node; if синами вузла Node є листки then
Обчислити вартість синів Node та за необхідності
запам'ятати нову поточну мінімальну вартість Cmin
else
Обчислити оцінку вартості синів вузла Node та
додати до черги лише тих із них, чия оцінка не більше Cmin end.
4. Евристичні алгоритми Повернемося до задачі про розподіл завдань по трьох процесорах і спробуємо розв'язати її у зовсім інший спосіб. Нехай ми маємо неповний розподіл (S1, S2, S3) усіх завдань, крім останнього. У цьому випадку найкраще розподілити останнє завдання, додавши його час до найменшого з S1, S2, S3, тобто передати його до найменш завантаженого процесора. Тепер правилом "передати чергове завдання до найменш завантаженого процесора" будемо керуватися при розподілі кожного з завдань. Застосування цього правила виражається алгоритмом, за яким завдання розподіляються без будь-якого перебирання варіантів:
розподілити перші три завдання по одному на процесор;
for i:=4 to n do begin обчислити k – номер найменшого з S[1], S[2], S[3]; додати T[i] до S[k]
end За цим алгоритмом завдання (12, 8, 7, 5, 4) розподіляються як (12, 8+4, 7+5). Очевидно, що краще не може бути. Проте розподіл завдань за цим алгоритмом не завжди є найкращим. Наприклад, завдання (12, 8, 7, 5, 4, 2) розподіляються за ним як (12+2, 8+4, 7+5) з вартістю 14, хоча є кращий розподіл (12, 8+5, 7+4+2) з вартістю 13. Правило "передати чергове завдання до найменш завантаженого процесора", яким ми керувалися при розподілі завдань, є прикладом евристики. Взагалі, значенням цього слова є "мистецтво відшукання істини", а в інформатиці евристика – це правило, метод або прийом, призначений для підвищення ефективності пошуку розв'язку задачі [Сл]. Алгоритм, побудований на основі застосування евристики, називається евристичним. Як правило, евристичні алгоритми дозволяють швидко побудувати розв'язок задачі, але не завжди гарантують, що він дійсно буде найкращим. Приклад 19.1. Розглянемо ще одну задачу та дві евристики для неї. Нехай, як і раніше, задано упорядкований за незростанням список часів виконання завдань T1, T2, … , Tn, але кількість процесорів не фіксовано. Замість цього задано час T0, і треба визначити найменшу кількість процесорів, яка забезпечує виконання всіх завдань у межах T0. Зрозуміло, що T0³ T1. Спочатку переформулюємо цю задачу в інших термінах. Час виконання завдання можна розглядати як об'єм предмету, а час T0 – як об'єм ящиків, по яких розподіляються предмети (форма ящиків та предметів неважлива). Отже, треба обчислити найменшу кількість ящиків, необхідних для розподілу всіх предметів. Тепер сформулюємо дві евристики. Е1. "Перший прийнятний". Перший предмет кладемо в перший ящик. Другий також, якщо він там уміщається. Якщо не уміщається, то кладемо його в другий ящик. Взагалі, черговий предмет кладемо в ящик із найменшим номером, в якому він уміщається. Е2. "Найкращий прийнятний". Черговий предмет кладеться в той ящик, у якому залишається найменший ще допустимий незайнятий об'єм. Якщо таких ящиків кілька, то з них вибираємо ящик із найменшим номером. Запис відповідних евристичних алгоритмів залишаємо вправою.
5. Застосування принципу оптимальності Знайомство з принципом оптимальності почнемо з розв'язання задачі. Приклад 2. Нехай паперовий прямокутник складено з клітин – m по вертикалі та n по горизонталі. У кожній клітині записано натуральне число. Уявімо, що з прямокутника зробили вертикальний циліндр, з'єднавши першу та останню вертикалі. Ми можемо рухатися по клітинах циліндра та підраховувати суму чисел у них. Рух починається з будь-якої клітини першого кільця. Далі, якщо ми перебуваємо в якійсь клітині, то можемо перейти на наступне кільце в одну з тих трьох клітин, що мають спільні точки з поточною. Рух закінчується на останньому, m-му кільці клітин. Треба обчислити найбільшу суму, яку можна набрати на одному з можливих шляхів довжини m. Якщо m=1, то достатньо вибрати клітину з найбільшим числом. Нехай m>1. Занумеруємо клітини кожного кільця числами від 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 за i<k, mii=0. Тоді шукана кількість
Завантажити реферат