Решить задачу коммивояжера методом ветвей и границ для сети, заданной матрицей расстояний. Построить дерево, вычислить длину оптимального тура.

Дана матрица стоимостей S:

Каждый ее элемент sij имеет, например, смысл стоимости проезда из города i в город j. В рассматриваемом примере матрица симметрична, то есть стоимость проезда из города i в город j равна стоимости обратного пути. Но могут встретиться и другие задачи. Прочерки по диагонали означают, что из города i в город i ходить нельзя.

Оценим, например, значение этой суммы для маршрута ...