BC/NW 2011; №1 (18):8.4

О ВЫЧИСЛИТЕЛЬНОМ ЭКСПЕРИМЕНТЕ ПО СРАВНЕНИЮ ЭВРИСТИК ДЛЯ ЗАДАЧИ КОММИВОЯЖЕРА

 

Я.В. Ахремцев, В.Н. Фальк

Московский энергетический институт (Технический университет)

 

Задача коммивояжера относится к классу NP. В работе описан вычислительный эксперимент по сравнению следующих эвристик: алгоритм “ближайшего соседа” [1, 2], алгоритм Lin – Kernighan (2-opt) [1, 3], алгоритм декомпозиции (разработан автором), алгоритм на основе построения минимального остовного дерева методом Прима (Prim) [1, 2], алгоритм на основе построения минимального остовного дерева методом Борувки (Boruvka) [1, 4], “Жадный” алгоритм [1, 2]. Для построения базовых точных решений применялся переборный алгоритм на основе метода ветвей и границ [1, 3, 5, 6, 7]. Для каждого алгоритма приведено типовое описание: поэтапное выполнение, вычислительная сложность, обсуждение возможностей практического применения и вычислительный эксперимент. Результаты сравнительных вычислений представлены в итоговых таблицах и на графиках (сравнение времени выполнения, характеристик точности и др.). Алгоритмы и программы их сравнения реализованы в среде MatLab (C++) на PC. Исходные данные для вычислений базировались на генераторе случайных чисел. Предполагается расширение вычислительного эксперимента: (а) анализ других алгоритмов, (б) рассмотрение более сложных версий задачи (например, многокритериальные постановки), (в) применение типовых исходных данных, (г) рассмотрение приложений в компьютерных/ коммуникационных сетях. Исследование  выполняется под руководством к.т.н. М.Ш. Левина (ИППИ РАН).

 

Литература

1. David L. Applegate, Robert E. Bixby, Vasek Chvátal & William J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2007.

2. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.
- М.: Издательство “Вильямс”, 2007.

3. А. Ахо, Дж. Хопкрофт, Д. Ульман. Структуры данных и алгоритмы.
- М.: Издательство “Вильямс”, 2007.

4. Роберт Седжвик. Фундаментальные алгоритмы на C++. Часть 5. Алгоритмы на графах. - М.: Издательство “ДиаСофтЮП”, 2002.

5. Kreher D.L., Stinson D.R.  Combinatorial Algorithms: Generation, Enumeration and Search. CRC Press, 1999.

6. Кристофидес Н. Теория графов. Алгоритмический подход.  - М.: Издательство “Мир”, 1978.

7. Christine L. Valenzuela, Antonia J. Jones. Estimating the Held-Karp lower bound for the geometric TSP. Univesity of Teeside, 2001.