ЕЩЁ ОБ ОДНОМ ПОДХОДЕ К РЕШЕНИЮ ПСЕВДОГЕОМЕТРИЧЕСКОЙ ЗАДАЧИ КОММИВОЯЖЁРА

  • Сергей Борисович Макаркин Тольяттинский государственный университет
Ключевые слова: задача коммивояжёра, псевдогеометрический вариант задачи коммивояжёра, геометрические методы решения, рандомизированные алгоритмы

Аннотация

В настоящей работе изучаются методы восстановления координат городов на основании матрицы расстояний псевдогеометрической задачи коммивояжёра и минимизации отклонения матрицы расстояний, рассчитанной на основе восстановленных координат городов от исходной матрицы расстояний. Также рассмотрены аппроксимационные методы расчёта координат городов в случаях, когда расстояния между ними не удовлетворяют условиям, необходимым для геометрической интерпретации задачи.

Литература

1. Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, 2003.
2. Громкович Ю. Теоретическая информаитка. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. БХВ-Петербург, СПб., 2010.
3. Мельников Б., Романов Н. Ещё раз об эвристиках для задачи коммивояжёра // Теоретические проблемы информатики и её приложений.— 2001.— Т. 4.— С. 81–92.
4. Dorigo M., Gambardella L. M. Ant colonies for travelling salesman problem // TR/IRIDIA/1996-3, Université Libre de Bruxelles, Belgium
5. Dubrin R., Willshaw D. An analogue approach of the travelling salesman problem using an elastic net method // Nature.— 1987.— Vol. 326.— P. 689–691.
6. Крашенинникова К. Об одном подходе к решению псевдогеометрической версии задачи коммивояжёра. // Вектор науки ТГУ.— 2011.— Vol. 2(16).— P. 21–24.
7. Пересечение двух окружностей // MAXimal URL: http://e maxx.ru/algo/circles_intersection (дата обращения: 28.07.2012).
8. Пересечение окружности и прямой // MAXimal URL: http://e maxx.ru/algo/circle_line_intersection (дата обращения: 28.07.2012).
9. Hamming R. Error detecting and error correcting codes // The Bell System Technical Journal.— 1950.— Vol. 2.
Выпуск
Раздел
Естественные науки

Наиболее читаемые статьи этого автора (авторов)