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

Розглянемо найпростіший спосіб такого оцінювання. Очевидно, що за неповного розподілу v перших i завдань із трійкою часів (S1, S2, S3) всі розподіли, що є його нащадками, мають вартість не меншу, ніж

E(v)=max{S1, S2, S3, min{S1, S2, S3}+Ti+1}.

Отже, оцінка E(v) є нижньою межею для вартості нащадків розподілу v.

Організуємо обхід дерева розподілів таким чином, що:

1.для кожного з вузлів обчислюється зазначена оцінка вартості,

2.вузли розглядаються у порядку зростання їх оцінок,

3.вузли з оцінкою, більшою від вартості вже одержаного повного розподілу, взагалі не розглядаються.

Ці міркування складають суть методу розгалужень і меж. Упорядкування вузлів робить обхід цілеспрямованим, а відкидання явно неперспективних піддерев скорочує його.Уточнимо організацію даних для обробки вузлів у зазначеному порядку. Оскільки нас цікавлять не самі розподіли, а лише їх вартість, у вузлах дерева будемо зберігати тільки трійку часів та номер завдання, розподіленого останнім. Маючи список часів 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:= ;

while (черга не порожня) and (її перший елемент має оцінку E
do

begin

Вилучити з черги її перший елемент Node=(S[1], S[2], S[3]; i; E);

if i=n-1 then {синами вузла є листки}