Решение задачи коммивояжера методом ветвей и границ. Валечка. Лабораторная работа 1 Решение задачи коммивояжера методом ветвей и границ Куликова Валентина Романовна, 19пм 1 Задача
 Скачать 163.35 Kb.
|
|
Лабораторная работа №1 Решение задачи коммивояжера методом ветвей и границ Куликова Валентина Романовна, 19ПМ 1) Задача: Создать программу решающую задачу коммивояжера. 2) Выбранные методы: Метод ветвей и границ 3) Формат входных данный Размерность матрицы, матрица весов (длин путей) 4) Формат выходных данных Путь 5) Краткое описание методов Задача коммивояжёра (коммивояжёр — бродячий торговец) заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз - в таком случае выбор осуществляется среди гамильтоновых циклов. Общая идея тривиальна: нужно разделить огромное число перебираемых вариантов на классы и получить оценки (снизу – в задаче минимизации, сверху – в задаче максимизации) для этих классов, чтобы иметь возможность отбрасывать варианты не по одному, а целыми классами. Трудность состоит в том, чтобы найти такое разделение на классы (ветви) и такие оценки (границы), чтобы процедура была эффективной. 6) Используемые структуры данных const int nm = 5; - размерность матрицы int a[nm][nm]; - матрица длин int n; - размерность матрицы int i,j –счетчики в программе а также переменные типа int для вычета по строке и столбцу, оценки нулей. 7) Реализованные функции  Функция для зачеркивания строк и столбцов, постановки запретов. (-1 это вычеркнутые эл-ты, -2 это запрет)  Вывод матрицы на каждом шаге  Поиск по строке и столбцу    8)Стандартные функции и библиотеки #include #include using namespace std; сообщает компилятору, что мы хотим использовать всё, что находится в пространстве имен std. 9) результаты   10) Приложение #include #include using namespace std; const int nm = 5; int a[nm][nm]; int n; void makebase(int ik, int jk) { int i, j; for (i = 0; i < n; i++) if (a[i][jk] >= 0) a[i][jk] = -1; for (j = 0; j < n; j++) if (a[ik][j] >= 0) a[ik][j] = -1; a[ik][jk] = -2; if (a[jk][ik] >= 0) a[jk][ik] = -1; } void main() { int i, j, c, i2, j2, i3, j3; int cnt; int minv, miniv, minjv, maxv; int flag; ifstream f("in.txt"); f >> n; for (i = 0; i < n; i++) for (j = 0; j < n; j++) f >> a[i][j]; f.close(); for (i = 0; i < n; i++) a[i][i] = -1; for (c = 0; c < n; c++) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << a[i][j] << ' '; } cout << "\n"; } cout << "---------------\n"; // Ищем элемент сроки или столбца flag = 0; for (i = 0; (i < n) && (flag == 0); i++) { cnt = 0; for (j = 0; j < n; j++) if (a[i][j] >= 0) { i2 = i; j2 = j; cnt++; } if (cnt == 1) flag = 1; } for (j = 0; (j < n) && (flag == 0); j++) { cnt = 0; for (i = 0; i < n; i++) if (a[i][j] >= 0) { i2 = i; j2 = j; cnt++; } if (cnt == 1) flag = 1; } if (flag == 1) { makebase(i2, j2); continue; } // Вычетание по строкам и столбцам for (i = 0; i < n; i++) { minv = 30000; for (j = 0; j < n; j++) if ((a[i][j] >= 0) && (a[i][j] < minv)) minv = a[i][j]; for (j = 0; j < n; j++) if (a[i][j] >= 0) a[i][j] -= minv; } for (j = 0; j < n; j++) { minv = 30000; for (i = 0; i < n; i++) if ((a[i][j] >= 0) && (a[i][j] < minv)) minv = a[i][j]; for (i = 0; i < n; i++) if (a[i][j] >= 0) a[i][j] -= minv; } // Оценка нулей maxv = -1; for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (a[i][j] == 0) { miniv = 30000; minjv = 30000; for (i2 = 0; i2 < n; i2++) if ((a[i2][j] >= 0) && (i2 != i) && (a[i2][j] < miniv)) miniv = a[i2][j]; for (j2 = 0; j2 < n; j2++) if ((a[i][j2] >= 0) && (j2 != j) && (a[i][j2] < minjv)) minjv = a[i][j2]; if (miniv + minjv > maxv) { maxv = miniv + minjv; i3 = i; j3 = j; } } makebase(i3, j3); } // Вывод пути i2 = 0; cout << i2 + 1; for (c = 0; c < n; c++) { for (j = 0; j < n; j++) if (a[i2][j] == -2) { cout << "->" << j + 1; i2 = j; break; } } } |