RUS  ENG
Полная версия
ЖУРНАЛЫ // Автоматика и телемеханика // Архив

Автомат. и телемех., 1988, выпуск 11, страницы 153–160 (Mi at6802)

Развивающиеся системы

Об эффективности одного локального алгоритма решения задачи коммивояжера

Г. М. Гутин

Гомель

Аннотация: Приводится теоретическое сравнение известных локальных алгоритмов наискорейшего спуска решения задачи коммивояжера с алгоритмом, предложенным Сарвановым и Дорошко [1]. Показано, что при случайном выборе исходного гамильтонова контура алгоритм Сарванова — Дорошко находит в окрестности этого контура гамильтонов контур меньшей длины, нежели известные локальные алгоритмы наискорейшего спуска для почти всех полных симметрических орграфов с некоторыми дискретными весами дуг.

УДК: 519.854.2


Поступила в редакцию: 21.09.1987


 Англоязычная версия: Automation and Remote Control, 1988, 49:11, 1514–1519

Реферативные базы данных:


© МИАН, 2024