Preview

Доклады БГУИР

Расширенный поиск

РЕАЛИЗАЦИЯ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА 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.)

Просмотров: 1475


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)