Перебирання варіантів в програмуванні, Детальна інформація
Перебирання варіантів в програмуванні
Уточнимо організацію даних для обробки вузлів у зазначеному порядку. Оскільки нас цікавлять не самі розподіли, а лише їх вартість, у вузлах дерева будемо зберігати тільки трійку часів та номер завдання, розподіленого останнім. Маючи список часів T[1], … , T[n] обробки завдань, неважко за цими даними обчислити оцінку вартості для неповних розподілів та саму вартість для повних. Для наочності цю величину також зберігатимемо у вузлі. Отже, вузол дерева подається трійкою часів S[1], S[2], S[3], номером завдання i та оцінкою вартості E, яка за i
max{ S[1], S[2], S[3], min{ S[1], S[2], S[3]}+T[i+1]}.
Очевидно, що за i=n-1 ця величина є вартістю повного розподілу, який подається "кращим із синів" цього вузла дерева.
Проміжні вузли записуються не в магазин, а в чергу, елементи якої упорядковано за зростанням оцінок вартості. Таким чином, для подання черги зручно скористатися лінійним списком (п.16.3.3). Вузли, відповідні повним розподілам, в чергу не записуються, оскільки оцінка вартості є власне їх вартістю.
Очевидно, що спочатку з трьох розподілів <(1;1)>, <(1;2)>, <(1;3)> в чергу достатньо записати лише один, для визначеності <(1; 1)>. Очевидно також, що коли обробляється вузол із однаковими часами S[1], S[2], S[3], то з трьох його синів до черги достатньо додати лише одного. Якщо ж два з трьох часів у вузлі рівні, то до черги не додається один із двох синів, що відрізняються лише порядком часів.
Опишемо обробку вузлів дерева таким алгоритмом.
Занести до черги розподіл (T[1], 0, 0; 1; T[1]);
Cmin:=\xF0A5 ;
while (черга не порожня) and (її перший елемент має оцінку E
do
begin
Вилучити з черги її перший елемент Node=(S[1], S[2], S[3]; i; E);
if i=n-1 then {синами вузла є листки}
Обчислити вартість синів вузла Node та за необхідності
запам'ятати нову поточну мінімальну вартість Cmin
else
Обчислити оцінку вартості синів вузла Node та
додати до черги лише тих із них, чия оцінка не більше Cmin
end
Уточнення цього алгоритму залишаємо вправою.
Розглянемо приклад обчислення мінімальної вартості розподілу за наведеним алгоритмом. Нехай задано час виконання п'яти завдань 9, 8, 7, 5, 4. Очевидно, що найкращий розподіл (9, 8+4, 7+5) має вартість 12. Значення Cmin та зміст черги, що виникають за наведеним алгоритмом, подамо таблицею:
Cmin Черга
\xF0A5 <9,0,0; 1; 9>
\xF0A5 <9,8,0; 2; 9> <17,0,0; 2; 17>
\xF0A5 <9,8,7; 3; 12> <9,15,0; 3; 15> <16,8,0; 3; 16> <17,0,0; 2; 17>
\xF0A5 <9,8,12; 4; 12> <9,13,7; 4; 13> <9,8,11; 4; 13> <9,15,0; 3; 15>
<16,8,0; 3; 16> <17,0,0; 2; 17>
12 <9,13,7; 4; 13> <9,8,11; 4; 13> <9,15,0; 3; 15> <16,8,0; 3; 16>
<17,0,0; 2; 17>
Як бачимо, перший елемент черги має оцінку вартості, гіршу за Cmin, тому подальше дослідження дерева варіантів не відбувається. За виконання алгоритму до черги додається 9 проміжних вузлів, а вилучається 4. Між тим, неважко підрахувати, що з урахуванням симетричних варіантів дерево містить 19 проміжних вузлів. Фактично, ми одержали потрібний розподіл взагалі без перебирання варіантів.
max{ S[1], S[2], S[3], min{ S[1], S[2], S[3]}+T[i+1]}.
Очевидно, що за i=n-1 ця величина є вартістю повного розподілу, який подається "кращим із синів" цього вузла дерева.
Проміжні вузли записуються не в магазин, а в чергу, елементи якої упорядковано за зростанням оцінок вартості. Таким чином, для подання черги зручно скористатися лінійним списком (п.16.3.3). Вузли, відповідні повним розподілам, в чергу не записуються, оскільки оцінка вартості є власне їх вартістю.
Очевидно, що спочатку з трьох розподілів <(1;1)>, <(1;2)>, <(1;3)> в чергу достатньо записати лише один, для визначеності <(1; 1)>. Очевидно також, що коли обробляється вузол із однаковими часами S[1], S[2], S[3], то з трьох його синів до черги достатньо додати лише одного. Якщо ж два з трьох часів у вузлі рівні, то до черги не додається один із двох синів, що відрізняються лише порядком часів.
Опишемо обробку вузлів дерева таким алгоритмом.
Занести до черги розподіл (T[1], 0, 0; 1; T[1]);
Cmin:=\xF0A5 ;
while (черга не порожня) and (її перший елемент має оцінку E
do
begin
Вилучити з черги її перший елемент Node=(S[1], S[2], S[3]; i; E);
if i=n-1 then {синами вузла є листки}
Обчислити вартість синів вузла Node та за необхідності
запам'ятати нову поточну мінімальну вартість Cmin
else
Обчислити оцінку вартості синів вузла Node та
додати до черги лише тих із них, чия оцінка не більше Cmin
end
Уточнення цього алгоритму залишаємо вправою.
Розглянемо приклад обчислення мінімальної вартості розподілу за наведеним алгоритмом. Нехай задано час виконання п'яти завдань 9, 8, 7, 5, 4. Очевидно, що найкращий розподіл (9, 8+4, 7+5) має вартість 12. Значення Cmin та зміст черги, що виникають за наведеним алгоритмом, подамо таблицею:
Cmin Черга
\xF0A5 <9,0,0; 1; 9>
\xF0A5 <9,8,0; 2; 9> <17,0,0; 2; 17>
\xF0A5 <9,8,7; 3; 12> <9,15,0; 3; 15> <16,8,0; 3; 16> <17,0,0; 2; 17>
\xF0A5 <9,8,12; 4; 12> <9,13,7; 4; 13> <9,8,11; 4; 13> <9,15,0; 3; 15>
<16,8,0; 3; 16> <17,0,0; 2; 17>
12 <9,13,7; 4; 13> <9,8,11; 4; 13> <9,15,0; 3; 15> <16,8,0; 3; 16>
<17,0,0; 2; 17>
Як бачимо, перший елемент черги має оцінку вартості, гіршу за Cmin, тому подальше дослідження дерева варіантів не відбувається. За виконання алгоритму до черги додається 9 проміжних вузлів, а вилучається 4. Між тим, неважко підрахувати, що з урахуванням симетричних варіантів дерево містить 19 проміжних вузлів. Фактично, ми одержали потрібний розподіл взагалі без перебирання варіантів.
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021