Отчёт по графам. 12 вариант Бердников ИТС. Отчёт о выполнении Индивидуального задания 1 " Решение задачи коммивояжера приближенно с помощью жадного алгоритма" По дисциплине "Дискретная математика"
 Скачать 0.62 Mb.
|
|
Министерство науки и высшего образования Российской Федерации Государственное образовательное учреждение высшего профессионального образования ГОУ ВПО “Пермский государственный научно-исследовательский университет” Кафедра математического обеспечения вычислительных систем Отчёт О выполнении Индивидуального задания №1 “ Решение задачи коммивояжера приближенно с помощью «жадного» алгоритма” По дисциплине “Дискретная математика”
Пермь 2022 Постановка задачи Задание: Решение задачи коммивояжера приближенно с помощью «жадного» алгоритма. Входные данные: В первой строке записано одно число n – количество вершин в графе. Далее располагается матрица расстояний графа (n строк по n чисел в каждой). Граф полный, все расстояния – натуральные числа. Выходные данные: в первой строке – длина найденного цикла, во второй строке – сам гамильтонов цикл, найденный «жадным» алгоритмом (в виде последовательности номеров вершин). Язык программирования: С++. Алгоритм решения задачи Считываем данные из файла input.txt. Динамически выделяем память для массивов. Заполняем матрицу смежности и массив со степенями вершин заполняет нулями. Из неотмеченных ребер выбрать ребро минимальной длины проверить что выбранное ребро вместе с ранее отмеченным не образует циклов не образует вершины степени больше 2 если оба условия выполнены отметить ребро иначе удалить если отмеченные ребра еще не образуют Гамильтонов цикл, то переходим в начало алгоритма. Выводим длину кратчайшего пути в файл. Выводим кратчайший путь в файл. Удаляем все массивы. Тестирование программы
Полный текст исходного кода #include #include #include #include struct edge { int v1, v2, d; }; bool edgeComp(edge e1, edge e2) { return e1.d > e2.d; } int findNextVert(std::vector { for (edge e : cycle) { if (e.v1 == cur && e.v2 != prev) return e.v2; if (e.v2 == cur && e.v1 != prev) return e.v1; } return -1; } int main() { int n; std::ifstream f("input.txt", std::ios_base::in); f >> n; std::cout << n; int** a = new int* [n]; for (int i = 0; i < n; ++i) a[i] = new int[n]; int* colors = new int[n]; for (int i = 0; i < n; ++i) colors[i] = i; int* deg = new int[n]; for (int i = 0; i < n; ++i) deg[i] = 0; std::vector for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { f >> a[i][j]; if (j > i) { edge e{ i, j, a[i][j] }; edges.push_back(e); } } f.close(); std::sort(edges.begin(), edges.end(), edgeComp); int len = 0; std::vector while (cycle.size() < n) { edge e = edges.back(); edges.pop_back(); if (deg[e.v1] < 2 && deg[e.v2] < 2 && (cycle.size() == n - 1 || colors[e.v1] != colors[e.v2])) { cycle.push_back(e); len += e.d; ++deg[e.v1]; ++deg[e.v2]; int colorToChange = colors[e.v2]; for (int i = 0; i < n; ++i) if (colors[i] == colorToChange) colors[i] = colors[e.v1]; } } std::ofstream z("output.txt", std::fstream::out); z << len << std::endl; int prev = -1; int cur = 0; z << 1; for (int i = 1; i < n; ++i) { int next = findNextVert(cycle, cur, prev); z << ' ' << (next + 1); prev = cur; cur = next; } z.close(); for (int i = 0; i < n; ++i) delete[] a[i]; delete[] a; delete[] colors; delete[] deg; return 0; } |
