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

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

Вход: матрица смежности графа;

Выход: список вершин, пройденных при обходе заданного графа в глубину.

Код программы:

#include iostream

#include vector

#include algorithm

using namespace std;

const int INF = 1e9;

int n; // число вершин в графе

vectorvectorint matrix; // матрица смежности графа

vectorint tour; // список вершин, пройденных при обходе графа

// Этап 1: Приведение матрицы по строкам и столбцам

void reduceRowsAndColumns(vectorvectorint m) {

for (int i = 0; i n; i++) {//приведение по строкам

int minVal = INF;

for (int j = 0; j n; j++) {

...