Page 74 - 4336

З врахуванням вищенаведеного, алгоритм подвійного

пошуку є наступним.

Крок 1. Сформувати початковий оцінюючий рядок =( ,

,
∗

, …, , ), для оптимального рядка з елементів, не менших

,
∗
по величині за відповідні елементи рядка . При цьому,

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

рядок , визначити оцінюючі рядки та наступним

чином:
Зворотній пошук:

d 2 ( r ) 1  d 2 ( r ) 1  L  d 2 ( ) r (4.14)
1 1 1

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

d 1 2 ( r  ) 2  d 1 2 ( r  ) 2 U  d 1 2 ( r ) 1  (4.15)

Крок 2, що є основним кроком алгоритму, проводиться

послідовно для r=0, 1, 2, ... і т.д. Якщо на деякому кроці, в

результаті послідовного виконання операцій (4.14) та (4.15),

будуть отримані однакові вектори оцінок, то знайдений розв'язок

є оптимальним. Операції, що визначаються співвідношеннями

(4.14) та (4.15), називаються операціями зворотного та прямого
пошуку відповідно. У кожному із цих співвідношень у першу

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

зворотного та прямого пошуку. Що стосується співвідношення

(4.14), то спочатку в рядку визначається вектор (це
,
можливо тому, що N-й стовпець матриці L складається з векторів,

усі елементи яких збігаються з ∞, а отже, враховуючи

74