Задание 5. Параметризованный алгоритм для вершинного покрытия
Реализовать для задачи о вершинном покрытии один из параметризованных алгоритмов.
В состав предоставляемых файлов должен входить файл Описание.txt, в котором указано, какой из методов реализован.
1) граф - формат аналогичен заданию 2
2) параметр k (ограничение на размер покрытия).
Тестовый файл: VC2.txt
Эталонные результаты:
- k=7: {1,2,6,8,11,12,14}
- k=5: нет решения
Программа получает на вход 5 параметров:
1.[Вход] Файл входными данными, описанного выше формата.
2.[Вход] Число. Параметр k - требуемый размер вершинного покрытия.
3.[Выход] Файл с результатом – оптимальным покрытием. Содержит одну строку, в которой через пробел указаны номера вершин, входящих в покрытие. Нумерация – от 1.
4.[Выход] Файл с результатом – стоимостью оптимального решения (мощность минимального покрытия). Содержит 1 строку с натуральным числом.
5.[Выход] Файл с замером временной сложности. Файл с двумя строками. В первой строке – время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд). Во второй строке – количество операций. Операциями считаем операции присваивания и сравнения элементов массивов (массива A и вспомогательных массивов/других структур). Начиная с 3-й строки - трассировочные сообщения о выполняемых преобразованиях. Для каждого преобразования сообщение должно располагаться в отдельной строке файла. Формат сообщения зависит от применяемого метода и выполняемого преобразования (вместо многоточий надо вставлять фактические значения).
а) для древовидного перебора ограниченной глубины:
- "Помещаем в покрытие вершину ... степени 1; k=..."
- "Для вершины ... степени 2; помещаем в покрытие всех соседей обоих соседей: ..., ...; k=..."
- "Для вершины ... степени 3; помещаем в покрытие саму вершину; k=..."
- "Для вершины ... степени 3; помещаем в покрытие всех её соседей: ....; k=..."
б) Для параметрической редукции:
- "Удаляем изолированные вершины: ..."
- "Для вершины ... степени 1 помещаем в покрытие её соседа ...; k=..."
- "Помещаем в покрытие вершину ... степени > ...; k= ..."
- "Обрабатываем ядро из ... вершин".
в) Для итерационного сжатия:
- "Для графа, порождённого вершинами ... преобразуем покрытие ... в покрытие ..." // сообщение при выходе из процедуры Сжатие
- "Проверка разбиения: Y=..., S=..., новые вершины покрытия: ..."