Задание 3. Решение задачи коммивояжёра методом полного перебора и методом ветвей и границ.

Тестовый набор данных – файл TSP1.txt.

Формат входного файла: аналогичен формату для задания 2, но для каждого ребра в строке указано: начало, конец, стоимость.

Оптимальное решение: 25.


Напоминание: по условию, каждую задачу надо решить 3 способами:

  1. Перебором обобщённых строк.
  2. Перебором перестановок.
  3. Методом ветвей и границ.

 

Программа получает на вход 4 параметров – пути к текстовым файлам:

  1. [Вход] Файл входными данными, описанного выше формата.
  2. [Выход] Файл с результатами –циклами, найденными каждым методом. Содержит три строку, по одной на каждый метод. Порядок – такой же, в котором они перечислены в задании. В каждой строке через пробел указаны номера вершин в том порядке, как они входят в цикл. Нумерация вершин - от 1. Первой в каждом списке должна стоять вершина с номером 1.
  3. [Выход] Файл с результатам – стоимостями оптимального цикла. Содержит 3 строки (по одной на каждый метод, в том же порядке), в каждой – одно вещественное число (стоимость цикла). Поскольку все методы точные, эти значения должны совпадать. Если не совпадают – проверьте свои решения!
  4. [Выход] Файл с замером временной сложности. Файл с тремя строками, по одной на каждый метод, в том же порядке. В каждой строке – два числе:

·Время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд).

·Количество операций. Операциями считаем операции присваивания и сравнения элементов массивов (массива A и вспомогательных массивов/других структур), а также арифметические операции и операции сравнения с вещественными числами (стоимостями дуг и циклов).