Page 73 - 4336

k
складається з N векторів, що належать R . Отже, необхідно
визначити Nk величин і Nk шляхів, що мають відповідні довжини.

Алгоритм подвійного пошуку дозволяє ефективно

знаходити зазначені Nk шляхів. При цьому, вимагається, щоб у

вхідному графі були відсутні контури від'ємної довжини. Робота

алгоритму подвійного пошуку починається з формування деякого

рядка ( , , …, , ), що поелементно оцінює зверху
,
,
∗
∗
∗
оптимальний рядок ( , , …, , ). Це означає, що кожний
,
,
елемент будь-якого вектора не менший відповідного елемента
∗
вектора . При цьому, в початковій точці повинно бути
,

, , 0. Зокрема, всі елементи оцінюючого рядка (за винятком

елемента , , , рівного нулю) могли б бути прийняті рівними ∞.
Потім в алгоритмі обчислюються нові (менші) оцінки для
∗
кожного вектора . Це здійснюється шляхом багаторазового
,

коректування вхідного оцінюючого вектора . Коректування
,
полягає в переході до нового вектора, що одержується в

результаті виконання узагальненої операції порівняння над

“старим” вектором та вектором  . Коректування
,
,
,
проводиться для всіх цілих j від 1 до N. По закінченню процесу
∗

коректування одержується нова оцінка вектора – вектор .
,
,
Таким чином, може бути одержаний увесь новий оцінюючий

рядок ( , , …, ). Далі процес триває аналогічним
,
,
,
чином. Робота алгоритму закінчується при співпаданні двох

послідовно держаних оцінюючих рядків – ( , , …, , ) та
,
,

( , , , , …, ) для i≥1. При цьому, можна довести, що
,
останній з отриманих оцінюючих рядків збігається з
∗
∗
оптимальним рядком ( , , …, ∗ ).
,
,
,
73