Задание 2. Решение задачи «Вершинное покрытие» методом перебора сочетаний
Уточнение: в алгоритме перебора сочетаний отразить оптимизацию перебора для k>n/2, как было обсуждено на лекции.
Тестовый файл: VC1.txt
Формат файла:
1-я строка:
n m
где n - количество вершин, m - количество дуг
Потом - m строк, в каждой строке номера вершин-концов ребра, через пробел.
Вершины нумеруются от 1 до n.
Программа получает на вход 4 параметра – пути к текстовым файлам:
1.[Вход] Файл входными данными, описанного выше формата.
2.[Выход] Файл с результатом – оптимальным покрытием. Содержит одну строку, в которой через пробел указаны номера вершин, входящих в покрытие. Нумерация – от 1.
3.[Выход] Файл с результатом – стоимостью оптимального решения (мощность минимального покрытия). Содержит 1 строку с натуральным числом.
4.[Выход] Файл с замером временной сложности. Файл с двумя строками. В первой строке – время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд). Во второй строке – количество операций. Операциями считаем операции присваивания и сравнения элементов массивов (массива A и вспомогательных массивов/других структур).
- 22 сентября 2016, 23:23