РЕАЛИЗАЦИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА C РАЗРЕЖЕННЫМИ МАТРИЦАМИ
Аннотация
Рассматривается способ ускорения процедуры метода ветвей и границ для решения асимметричных задач коммивояжера с разреженными матрицами. Предлагаемый способ использует наследование решений порождающих задач, при котором оценка вариантов порожденных задач о назначении проводится методом коррекции дерева кратчайших путей приращений. Реоптимизация дерева путей приращений на структурах смежности приводит к гарантированному снижению вычислительной сложности задачи на порядок.
Об авторах
М. П. Ревотюк
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
М. К. Кароли
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
П. М. Батура
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Список литературы
1. Miller D., Pekny J. // Science. 1991. Vol. 251. P. 754-761.
2. Mahshid A.F., Rosnah M.Y. // European Journal of Scientific Research. 2009. Vol. 29. № 3. P. 349-359.
3. Ревотюк М.П., Батура П.М., Полоневич А.М. // Докл. БГУИР. 2011. № 3 (57). C. 56-62.
4. Jonker R., Volgenant A. // Computing. 1987. Vol. 38. P. 325-340.
5. Ревотюк М.П., Кароли М.К., Батура П.М. //Докл. БГУИР. 2013. № 5 (75). C. 30-36.
Рецензия
Для цитирования:
Ревотюк М.П., Кароли М.К., Батура П.М. РЕАЛИЗАЦИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА C РАЗРЕЖЕННЫМИ МАТРИЦАМИ. Доклады БГУИР. 2013;(7):25-31.
For citation:
Revotjuk M.P., Qaraleh M.K., Batura P.M. IMPLEMENTATION The branch and bound method for solving The traveling salesman problem with sparse matrix. Doklady BGUIR. 2013;(7):25-31. (In Russ.)
Просмотров: 4255
Послать статью по эл. почте 