ПЕРЕБИРАННЯ ВАРІАНТІВ В ПРОГРАМУВАННІ

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 {синами вузла є листки}

Обчислити вартість синів вузла Node та за необхідності

запам'ятати нову поточну мінімальну вартість Cmin

else

Обчислити оцінку вартості синів вузла Node та