Рассмотрим евклидову версию задачи TSP: на плоскости есть n точек, нужно построить цикл минимальной длины, который проходит через все точки ровно по одному разу.
Объявляется простой мини-конкурс: найти как можно лучшее решение для одного конкретного теста (в нем нет ничего особенного, это просто случайный тест из 100 точек).
Тест лежит здесь: http://pastebin.com/zYHSXXwE . В первой строке записано число точек, дальше записаны координаты самих точек.
Чужим кодом для решения TSP пользоваться запрещается. Ваши результаты и ссылки на найденные циклы (перестановка чисел от 0 до n - 1) пишите в комментариях.
Оптимальное решение: 7.83176. Первый нашедший -- ilyakor (с помощью http://pastebin.com/DiYcmPcw). Поздравляю! И спасибо всем, кто принял участие.
Предыдущие рекорды: 7.83935 by cmd, 7.88385 by cmd, 7.93560 by I_love_Nastya, 7.94123 by I_love_Nastya, 7.95026 by cmd, 8.10851 by cmd, 8.44558 by ilyakor, 9.00594 by ilyakor, 9.15607 by Jokser, 9.47153 by Jokser.
Comments (0)
