Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 29 стр.

UptoLike

Составители:

Рубрика:

Для вычисления одного элемента (3.1) требуются две операции

(сложение, вычитание) и операция сравнения с предыдущим элементом.

Примечание. Наиболее простой алгоритм (на каждом шаге идти

к ближайшей вершине [12]) требует всего 0,5n

операций сравнения,

однако возможная погрешность при этом не поддается оценке.

Сравнение с оценками, приводимыми в [12] для наилучших из

приближенных алгоритмов (алгоритм Линна ~3,5n

(n–4)!), позволяет

рассчитывать на более высокую вычислительную эффективность

метода расширения цикла.

Блок-схема алгоритма метода расширения цикла приведена на

рис. 3.

Работу алгоритма проиллюстрируем на числовом примере, матрица

расстояний для которого представлена в табл. 11.

Ниже приведены вычисления для случая отправления коммивояжера

из пункта A

(1=

Согласно пункту 2º (рис. 3) начальный цикл и необходимые данные

записаны для шага t = 1 в (3.2).

Таблица 11.

1 2 3 4 5 6

6 13

27 18 25

2 10 20 1 9 23

3 22

15 8 3

4 19 2 30 12 17

5 14 11 26 29 5

6 24 7 16 4 21

c=с