Початкова матриця

Знаходження повністю

зведеної матриці

Будування віток згідно з

вибраною -дугою

Знаходження нижньої оцінки

а- множини з - дугою

Знаходження нижньої оцінки

- множини без - дуги:

без

( ij )-дуги

ні

ні

так

Вибір з матриці - дуг

з та включення до

з

( ij )-дугою

так

Формування кільцевого

маршруту

Рис.7.5

знаходиться його оцінка

,

не враховуючи елемент , для якого знаходиться оцінка; величина цієї оцінки дорівнює сумі мінімального елемента з і-го рядка та мінімального елемента з -ї колонки. З усіх знайдених вибирається максимальне, яке вказує на -дугу, що повинна подалі розглядатися у процесі побудови послідовності кільцевого маршруту.

Вибрана -дуга включається до дерева-графа за двома напрямками (рис.7.6).

• входить до послідовності ;

• не повинна входити до послідовності (позначається як ).

Рис.7.6

3. Знаходження оцінки межі усіх допустимих кільцевих маршрутів з включенням - дуги наступним чином.

У повністю зведеній матриці виключається і–й рядок та -а колонка, потім в одержаній таким чином матриці один з елементів прирівнюється до М: цей елемент має виключати локальні цикли при подальшому конструюванні послідовності . Наприклад, при т = 5 та частковій послідовності треба виключити дугу (31), тобто .

Одержана матриця знову перетворюється на повністю зведену матрицю, потім знаходиться оцінка -дуги:

Нижня межа оцінки цільової функції для всіх послідовностей з включенням -дуги дорівнює

.

Величина а записується до вершини -дуги дерева-графа послідовності. Матриця , яка одержана після цих перетворень знову готова для подальшого розвитку послідовності з -тою дугою, починаючи з п.2.

3. Знаходження оцінки нижньої межі усіх допустимих кільцевих маршрутів без включення -ї дуги виконується наступним чином.

У повністю зведеній матриці , знайденої за п.2, проводиться заборона елемента для вибраної -дуги. Потім така матриця перетворюється на повністю зведену і знаходиться оцінка

.

Нижня межа оцінки цільової функції для усіх послідовностей без -ї дуги дорівнює

.

Величина записується до вершини -дуги дерева-графа послідовності. Матриця після таких перетворень знову готова для подальшого розвитку послідовності без -дуги, починаючи з п.2.

3. Знаходження подальшого розвитку знайдених послідовностей . Якщо , то подальший розвиток ведеться з матриці , одержаної у п.3. Якщо , - то з матриці з п.4.

Процес побудови напрямків ведеться до моменту, коли матриця стане розміром (2х2).

3. Складання усіх -дуг у неперервну послідовність, яка відображує кільцевий маршрут.

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

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

Загальний вид дерева-графа зображений на рис.7.7.

а а а

( ), ( )

Рис. 7.7