Комментарии 9
эх, помню курсовую писал по данной задаче. «Исследование задачи комивояджера методом брутфорса». 15 городов, 8 часов перебора…
Хах)
Ну, это ещё ништяк. Мне знакомый рассказывал, как, занимаясь доработкой скрипта для одной фирмы, они обнаружили там огромный запрос в БД. Оказалось, он возвращал набор простых чисел для вычисления НОДа. Про Евклида писавшие, видать, не знали. Причём числа немаленькие, больше нескольких тысяч.
Ну, это ещё ништяк. Мне знакомый рассказывал, как, занимаясь доработкой скрипта для одной фирмы, они обнаружили там огромный запрос в БД. Оказалось, он возвращал набор простых чисел для вычисления НОДа. Про Евклида писавшие, видать, не знали. Причём числа немаленькие, больше нескольких тысяч.
НЛО прилетело и опубликовало эту надпись здесь
8% погрешности от ПРИБЛИЖЕННОГО алгоритма — это очень много. Приемлемым отклонением от оптимума является не более 7%.
Похоже на MinMax стратегию из Теории Принятия Решений.
Не совсем понимаю ваши выводы. Из описания кажется, будто алгоритм не более чем квадратный и рекурсивен в той же мере что и цикл.
Так решение приближенное?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задачи коммивояжёра на плоскости рекурсивным жадным алгоритмом