Рассмотрим евклидову версию задачи 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.
Явно не самое лучшее решение, но чтобы подогреть интерес, выложу:
9,47153439264957
50 25 7 79 4 20 58 49 84 63 70 80 98 75 39 22 59 69 31 65 64 52 29 81 1 97 12 66 88 82 15 94 74 73 6 27 78 92 2 36 8 18 33 55 9 37 45 44 17 28 85 43 62 91 83 19 10 38 46 48 26 54 0 42 60 95 68 86 34 30 41 77 90 13 61 35 72 24 87 96 71 5 56 53 89 21 40 16 93 14 32 57 99 76 51 11 47 23 67 3
Код:
http://pastebin.com/nzkBnfRe
9,15606758132600
50 65 64 52 29 81 1 97 12 66 88 82 15 94 74 73 6 27 78 92 2 36 8 18 33 55 9 37 45 44 17 28 85 43 62 91 83 19 10 38 46 48 26 54 0 42 60 95 68 86 34 7 4 79 20 58 25 49 84 80 70 63 75 98 39 22 59 69 31 41 30 77 90 13 61 35 72 24 87 96 71 5 56 53 89 21 40 16 93 14 32 57 99 76 51 11 47 23 67 3
Код:
http://pastebin.com/d4eWA7z6
Совсем тупое решение получило 9.00594 (само решение: 32 57 11 47 51 23 76 99 67 3 98 75 39 22 80 84 49 58 25 7 20 4 79 14 93 16 48 26 21 89 53 0 54 56 5 87 24 42 60 68 72 35 61 13 34 90 77 69 31 65 50 64 52 29 81 1 97 66 12 88 82 94 74 18 33 15 8 36 2 6 92 78 27 73 86 95 85 43 62 91 83 19 10 46 38 40 96 71 28 17 44 45 37 55 9 30 41 59 70 63). До оптимума похоже далеко.
8.44558
33 18 74 94 82 15 8 36 2 6 92 78 27 73 86 61 13 34 90 77 69 31 65 50 64 52 29 81 66 12 88 97 1 30 41 59 22 80 84 49 58 25 7 20 4 79 32 57 11 47 51 23 76 99 67 3 98 75 39 70 63 14 93 16 48 26 21 89 53 0 54 56 42 60 68 72 35 95 24 87 5 71 96 40 46 38 10 19 83 91 62 43 85 28 17 44 45 37 55 9
7.83176
52 29 81 1 97 12 66 88 82 94 74 15 33 18 8 36 2 6 73 92 78 27 55 9 37 45 44 17 28 85 43 62 91 83 19 10 38 46 48 16 93 14 32 57 11 47 51 99 76 23 67 3 98 75 39 22 80 70 63 84 49 58 25 7 20 4 79 96 40 26 21 89 54 0 53 56 71 5 87 24 42 60 68 95 72 35 86 61 13 34 90 77 41 30 31 69 59 65 50 64
13 61 86 35 72 95 68 60 42 24 87 5 71 56 53 0 54 89 21 26 40 96 79 4 20 7 25 58 49 84 63 70 80 22 59 65 69 31 1 97 88 66 12 81 29 52 64 50 39 75 98 3 67 76 99 23 51 47 11 57 32 14 93 16 48 46 38 10 19 83 91 62 43 85 28 17 44 45 37 55 9 33 15 18 74 82 94 8 36 2 27 78 92 6 73 30 41 77 90 34
75 39 22 80 70 63 84 49 58 25 7 20 4 79 40 26 21 89 54 0 53 56 71 96 5 87 24 42 60 68 95 78 27 92 8 36 2 6 73 86 35 72 61 13 34 90 77 41 30 31 69 59 65 50 64 52 29 81 1 97 12 66 88 82 94 74 18 15 33 9 55 37 45 44 17 28 85 43 62 91 83 19 10 38 46 48 16 93 14 32 57 11 47 51 99 76 23 67 3 98
Для сложных инстансов такие методы бесполезны, нужен полный перебор (с отсечениями; используются хитрые оценки снизу, чтобы всё быстро отсекалось).
Так что интересно, рандомные ли были входные данные на беларуской олимпиаде. И если нет - что tourist такое крутое придумал, что смог эффективно их решать :)