Page 54 - 4387

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

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

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

1,1

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

∗
∗
оптимальним рядком ( , , …, ∗ ).
1,1 1,2 1,
З врахуванням вищенаведеного, алгоритм подвійного
пошуку є наступним.

Крок 1. Сформувати початковий оцінюючий рядок =( ,
0
0
1
1,1
0 0 ), для оптимального рядка з елементів, не менших
∗
, …,
1,2 1, 1
по величині за відповідні елементи рядка . При цьому,
∗
1
0 = 0 (по припущенню у вершині 1 є петля
присвоїти
1,1,1
нульової довжини).
Крок 2. За умови, що для рядка визначений оцінюючий
∗
1
2 2+1 2+2 наступним
рядок , визначити оцінюючі рядки 1 та 1
1
чином:
Зворотній пошук:

d 1 2 ( r+ ) 1 = d 1 2 ( r+ ) 1 ⊗ L ⊕ d 1 2 ( ) r (7.6)

Прямий пошук:

d 1 2 ( r + ) 2 = d 1 2 ( r + ) 2 ⊗U ⊕ d 1 2 ( r ) 1 + (7.7)

53