Эффективная реализация алгоритма решения задачи коммивояжёра методом ветвей и границ

Для известного алгоритма точного решения задачи коммивояжёра методом ветвей и границ (алгоритма Литтла) предлагается следующая модификация. На каждой промежуточной стадии выполнения алгоритма вычисляется более точная оценка снизу для всех альтернативных маршрутов, которые можно построить на основе текущего частичного решения. Благодаря этому, отсечение бесперспективных вариантов выполняется, как правило, намного эффективнее, особенно для случайной несимметричной матрицы расстояний. Рассмотрены реализации модифицированного алгоритма с поиском вглубь и вширь, а также с поиском вглубь, когда ищется приближенный маршрут с произвольно задаваемой погрешностью. Для функции трудоёмкости $U(n)=a\cdot c^n$, измеряющей количество обрабатываемых матриц расстояний (узлов дерева решений) в графе с $n$ вершинами, с помощью вычислительного эксперимента получены оценки констант $a$ и $c$ для различных реализаций алгоритма. При этом время обработки каждого узла увеличивается в 1,5–2 раза при существенном уменьшении общего времени выполнения алгоритма.