1. Главная
  2. Библиотека
  3. Информатика
  4. Решить задачу коммивояжера методом ветвей и границ для сети, заданной матрицей расстояний: ... Решить задачу коммивояжера...
  • 👋 Решение задач

  • 📚 Информатика

решение задачи на тему:

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

Дата добавления: 18.01.2024

Условие задачи

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

Ответ

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

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

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

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


#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++) {

...

Потяни

Сводка по ответу

  • Загружено студентом
  • Проверено экспертом
  • Использовано для обучения AI
  • Доступно по подписке Кампус+

Купи подписку Кампус+ и изучай ответы

Кампус Библиотека

  • Материалы со всех ВУЗов страны

  • 1 000 000+ полезных материалов

  • Это примеры на которых можно разобраться

  • Учись на отлично с библиотекой