Условие задачи
Решить задачу коммивояжера методом ветвей и границ для сети, заданной матрицей расстояний:
Ответ
Алгоритм Метод ветвей и границ решения задачи коммивояжера
Вход: матрица смежности графа;
Выход: список вершин, пройденных при обходе заданного графа в глубину.
Код программы:
#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++) {
...