Задание 7. Локальный поиск (имитация отжига) для задачи «Вершинное покрытие».
Требуемые условия завершения
Реализовать алгоритм имитации отжига для задачи «Вершинное покрытие».
Параметры — как для задания 2, плюс — параметры метода. Параметры метода задаются в виде текстового файла с 3 строками:
- Начальная температура T (вещественное число).
- Коэффициент alpha (вещественное число).
- Количество итераций (целое число).
Параметр k положить равным 1.
Программа получает на вход 5 параметрами - пути к файлам:
1.[Вход] Файл с описанием графа.
2.[Вход] Файл с параметрами метода.
3.[Выход] Файл с результатом – результирующим (наилучшим найденным) покрытием. Содержит одну строку, в которой через пробел указаны номера вершин, входящих в покрытие. Нумерация – от 1.
4.[Выход] Файл с результатом – стоимостью полученного решения (мощность покрытия). Содержит 1 строку с натуральным числом.
5.[Выход] Файл с замером временной сложности. Файл с двумя строками. В первой строке – время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд). Во второй строке – количество операций. Операциями считаем операции присваивания и сравнения элементов массивов.
Программа должна выдавать в консоль трассировочные сообщения: каждые 100 итераций — номер итерации и стоимость текущего (не обязательно рекордного) значения.
Пример для тестирования - взят из
https://github.com/tomrunia/Advanced-Algorithms/tree/master/Minimum%20Vertex%20Cover/MinimumVertexCover/datasets/generated/final/200_10.0_138.0
Но преобразован в формат, который указал я во 2 задании.
В тестовом графе 200 вершин, мощность минимального вершинного покрытия равна 138.
Получить оценку
Открыто с: среда, 5 декабря 2018, 00:00
Срок сдачи: четверг, 31 марта 2022, 23:55
Срок: до 26.12.19
Реализовать алгоритм имитации отжига для задачи «Вершинное покрытие».
Параметры — как для задания 2, плюс — параметры метода. Параметры метода задаются в виде текстового файла с 3 строками:
- Начальная температура T (вещественное число).
- Коэффициент alpha (вещественное число).
- Количество итераций (целое число).
Параметр k положить равным 1.
Программа получает на вход 5 параметрами - пути к файлам:
1.[Вход] Файл с описанием графа.
2.[Вход] Файл с параметрами метода.
3.[Выход] Файл с результатом – результирующим (наилучшим найденным) покрытием. Содержит одну строку, в которой через пробел указаны номера вершин, входящих в покрытие. Нумерация – от 1.
4.[Выход] Файл с результатом – стоимостью полученного решения (мощность покрытия). Содержит 1 строку с натуральным числом.
5.[Выход] Файл с замером временной сложности. Файл с двумя строками. В первой строке – время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд). Во второй строке – количество операций. Операциями считаем операции присваивания и сравнения элементов массивов.
Программа должна выдавать в консоль трассировочные сообщения: каждые 100 итераций — номер итерации и стоимость текущего (не обязательно рекордного) значения.
Пример для тестирования - взят из
https://github.com/tomrunia/Advanced-Algorithms/tree/master/Minimum%20Vertex%20Cover/MinimumVertexCover/datasets/generated/final/200_10.0_138.0
Но преобразован в формат, который указал я во 2 задании.
В тестовом графе 200 вершин, мощность минимального вершинного покрытия равна 138.
- 29 ноября 2017, 17:05