Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, ilnar, Вы писали:
I>>>таких не пробовал. с вас ссылки на задачи, и попробую, но уже вечером. пишите на сколько минут пускать.
А>>Так это TSPLIbовские аналоги CVRP E76 и E101. Пускать до упора — пока не докажет (если это не долго).
I>все же, ссылки в студию! а про пускать до упора, спонсором будете? ресурсов не хватет ))
здесь
Там в списках задача — eil76
Решается она
там за 0.3 сек, если я ничего не путаю (плохо с английским), а вообще по поводу оптимальных решений — почти для всех задач из TSPLIB они найдены очень быстро см выше.
Вот цитата автора TSPLIB:
"When I published TSPLIB more than 10 years ago, I expected that at least solving the large problem instances to proven optimality would pose a challange for the years to come.
However, due to enormous algorithmic progress all problems are now solved to optimality!!"
I>не понял про нижнюю границу. проясните термин плиз.
Нижняя граница — оценка оптимального решения снизу (те она меньше оптимума).
Чем ближе эта оценка к оптимуму тем лучше.
Если мы доказываем оптимальность методом ветвей и границ, то там используется нижняя граница для отсечения подмножеств решений.
А>>Ну в среднем там 8% превышения это много 
I>какие есть, на то и точные методы. не ставлю цели всех обскакать, за это не платят, я не фанатик.
Есть дела поважнее и поинтереснее.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, ilnar, Вы писали:
I>>Здравствуйте, Аноним, Вы писали:
А>>>Здравствуйте, ilnar, Вы писали:
А>здесь
А>Там в списках задача — eil76
А>Решается она там за 0.3 сек, если я ничего не путаю (плохо с английским), а вообще по поводу оптимальных решений — почти для всех задач из TSPLIB они найдены очень быстро см выше.
А>Вот цитата автора TSPLIB:
А>"When I published TSPLIB more than 10 years ago, I expected that at least solving the large problem instances to proven optimality would pose a challange for the years to come.
А>However, due to enormous algorithmic progress all problems are now solved to optimality!!"
это я читал, я тож плох в английском, но его достаточно для понимания статей в этой сфере.
но за 0.3 секунды они решали не методом ветвей и границ, а чем-то, что приблизвается сверху и снизу, за счет чего доказывается оптимальность. и к тому же там наверно отбор самого лучшего. метод лучший для одного типа задач може пасовать перед другими: доказательство, для конкретной задачи ожно даже вшить решение в программу
I>>не понял про нижнюю границу. проясните термин плиз.
А>Нижняя граница — оценка оптимального решения снизу (те она меньше оптимума).
А>Чем ближе эта оценка к оптимуму тем лучше.
А>Если мы доказываем оптимальность методом ветвей и границ, то там используется нижняя граница для отсечения подмножеств решений.
теперь понял. не сразу понял о чем речь. над этим работаю. казалось сделал один алгоритм, только он начал уходить в себя (там был неконтролируемый перебор)
Здравствуйте, Аноним, Вы писали:
А>А доказывает точное решение STSP eil101, eil76 за склько мин?
eil76 доказывается за 42 сек.
ei101 (при оптимальном решении 629) через 1 мин дает 748/571(второе число -- нижняя граница), через 15 мин -- 723/571
вот более подробный лог появления рекордов (улучшний):
формат <прошло времени>: <очередной рекорд>, <доказанная точность>,
где <доказанная точность> = (<очередной рекорд> — <текущая известная нижняя граница>)/<очередной рекорд>
сначала время в миллисекундах:
15: 759, 0.247694,
15: 757, 0.245707,
421: 754, 0.242706,
421: 752, 0.240691,
3562: 750, 0.238667,
3562: 748, 0.236631,
очередной рекорд появился в 525 секунде.
поэтому дальше сразу в минутах:
8.76: 731, 0.218878,
8.76: 726, 0.213499,
13.28: 725, 0.212414,
13.28: 724, 0.211326,
13.28: 723, 0.210235,
19.93: 720, 0.206944,
19.93: 719, 0.205841,
19.93: 718, 0.204735,
26.22: 715, 0.201399,
26.22: 714, 0.200280,
26.22: 710, 0.195775,
26.22: 709, 0.194640,
26.22: 708, 0.193503,
27.53: 703, 0.187767,
27.53: 698, 0.181948,
27.53: 697, 0.180775,
48.67: 694, 0.177233,
48.7: 692, 0.174855,
48.73: 689, 0.171263,
48.73: 684, 0.165205,
49.44: 683, 0.163982,
49.44: 682, 0.162757,
49.44: 681, 0.161527,
49.44: 680, 0.160294,
245.98: 678, 0.157817,
245.98: 675, 0.154074,
294.25: 673, 0.151560,
294.25: 672, 0.150298,
294.27: 671, 0.149031,
294.27: 670, 0.147761,
297.94: 668, 0.145210,
297.94: 667, 0.143928,
297.96: 666, 0.142643,
297.96: 665, 0.141353,
318.2: 664, 0.140060,
341.72: 663, 0.138763,
355.95: 662, 0.137462,
363.02: 661, 0.136157,
364.56: 660, 0.134848,
398.17: 659, 0.133536,
413.79: 658, 0.132219,
413.79: 657, 0.130898,
422.05: 656, 0.129573,
422.05: 655, 0.128244,
530.43: 654, 0.126911,
дальше пошел на работу
