Задание 3. Решение задачи коммивояжёра методом полного перебора и методом ветвей и границ.
Требуемые условия завершения
Получить оценку
Тестовый набор данных – файл TSP1.txt.
Формат входного файла: аналогичен формату для задания 2, но для каждого ребра в строке указано: начало, конец, стоимость.
Оптимальное решение: 25.
Напоминание: по условию, каждую задачу надо решить 3 способами:
- Перебором обобщённых строк.
- Перебором перестановок.
- Методом ветвей и границ.
Программа получает на вход 4 параметров – пути к текстовым файлам:
- [Вход] Файл входными данными, описанного выше формата.
- [Выход] Файл с результатами –циклами, найденными каждым методом. Содержит три строку, по одной на каждый метод. Порядок – такой же, в котором они перечислены в задании. В каждой строке через пробел указаны номера вершин в том порядке, как они входят в цикл. Нумерация вершин - от 1. Первой в каждом списке должна стоять вершина с номером 1.
- [Выход] Файл с результатам – стоимостями оптимального цикла. Содержит 3 строки (по одной на каждый метод, в том же порядке), в каждой – одно вещественное число (стоимость цикла). Поскольку все методы точные, эти значения должны совпадать. Если не совпадают – проверьте свои решения!
- [Выход] Файл с замером временной сложности. Файл с тремя строками, по одной на каждый метод, в том же порядке. В каждой строке – два числе:
·Время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд).
·Количество операций. Операциями считаем операции присваивания и сравнения элементов массивов (массива A и вспомогательных массивов/других структур), а также арифметические операции и операции сравнения с вещественными числами (стоимостями дуг и циклов).
- 25 февраля 2021, 17:39
- 29 сентября 2016, 15:21