Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, 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 мин работы?!
I>метод типа ветвей и границ, он даже может найти оптимальное решение в первые минуты, а потом сутками ходить по оставшенму дереву перебора решений доказывая оптимальность (это и есть проблема точных методов. оптимальное решение найдет, но не будет знать что это оптимальное). Там где Е=0, не во всех случаях алгоритм указывал, что найденное решение -- оптимальное (просто, видимо, задачи попались такие что в большинстве случаев доходил быстро до оптимального решения, но только в части из них смог сказать что найденный рекорд оптимален).
I>т.е. в большинстве случаев, особенно на больших задачах очередные рекорды (я так называю очередное улучшение решения, не путать с оптимальным решением) чем дальше в лес, тем реже появляются.
I>могу показать лог появления рекордов (улучшения решения) для разных задач, будет видно что они появляются очень неравномерно (((
D>>2) Вы не против если мы сгенерируем свою задачу и дадим ее вам для решения? И сами ее тоже решим заодно.
I>не вопрос, на какое время пускать? 1 и 15 минут? сразу скажу, что как уже писал, разница результатов на 15 мин и 6 часов может не отличаться, т.к. алгоритм агрессивно идет в "хороших" направлениях, а потом смотрит и остальное.
Мы недооценили метод ветвей и границ. Действительно, если подобрать хорошие евристики, то можно получать хорошие результаты и очень быстро.
Мы будем исследовать и улучшать наш метод ветвей и границ тоже как только появится свободное время, поскольку пока основными нашими доходами являются доходы от аутсорсинга, поэтому пока все на энтузиазме и в свободное время.
А вы занимаетесь комбинаторной оптимизацией профессионально?
Учились и работаете в этом направлении?
