Решение задачи коммивояжера методом ветвей и границ

Автор: Пользователь скрыл имя, 03 Ноября 2012 в 01:24, лабораторная работа

Описание работы

На плоскости указаны N городов, при этом местоположение каждого города определяется парой координат. Необходимо найти оптимальный (относительно длины пути) простой цикл, позволяющий коммивояжеру посетить все города и вернуться в исходную точку отправления. Задача должна быть решена алгоритмом поиска с возвратом (backtracking) с оптимизацией перебора при помощи метода ветвей и границ. Дополнительно выводится информация о количестве рекурсивных вызовов. Тестирование выполнять для N<10. Провести сравнение выигрыша по времени, получаемого за счет сокращения вариантов перебора