Здравствуйте, Divosoft, Вы писали:

D>Здравствуйте, ilnar, Вы писали:

I>>вот и моя лепта на задачах atsp
I>>задачи решались на компьютере Core2Duo E6750(2.66GHz), FSB 1333MHz, 2Gb PC-8500 5-5-5-15

I>>результаты здесь
D>Результаты неожиданные честно говоря. Очень впечатляет как для точного алгоритма.

D>У меня вопросы:
D>1) а почему результаты за 1 мин совпадают с результатами за 15 мин в 100% случаев?
D>Там где Е=0 ответ понятен. Но там где точное решение не найдено, должно же быть улучшение за 14 мин работы?!

метод типа ветвей и границ, он даже может найти оптимальное решение в первые минуты, а потом сутками ходить по оставшенму дереву перебора решений доказывая оптимальность (это и есть проблема точных методов. оптимальное решение найдет, но не будет знать что это оптимальное). Там где Е=0, не во всех случаях алгоритм указывал, что найденное решение -- оптимальное (просто, видимо, задачи попались такие что в большинстве случаев доходил быстро до оптимального решения, но только в части из них смог сказать что найденный рекорд оптимален).
т.е. в большинстве случаев, особенно на больших задачах очередные рекорды (я так называю очередное улучшение решения, не путать с оптимальным решением) чем дальше в лес, тем реже появляются.
могу показать лог появления рекордов (улучшения решения) для разных задач, будет видно что они появляются очень неравномерно (((

D>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
не вопрос, на какое время пускать? 1 и 15 минут? сразу скажу, что как уже писал, разница результатов на 15 мин и 6 часов может не отличаться, т.к. алгоритм агрессивно идет в "хороших" направлениях, а потом смотрит и остальное.