Аннотация:
В работе рассматривается быстрый эвристический алгоритм для задачи коммивояжера на основе метода ветвей и границ с оценкой качества получаемого решения, т.е. с параметром k, который гарантирует, что получаемое решение хуже оптимального не более чем в 1/k раз. Алгоритм предназначен для вычислительных систем с общей памятью.
Ключевые слова:
задача коммивояжера, точный алгоритм, эвристический алгоритм, параллельный алгоритм, метод ветвей и границ.
Полный текст:
PDF файл (495 kB)