Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, Decker, Вы писали:
D>>Здравствуйте, ilnar, Вы писали:
I>>>Здравствуйте, Decker, Вы писали:
D>>>>Собственно нужен алгоритм литла, известный так же как алгоритм ветвей и границ приминительно к задаче коммивояжера.
I>>>кстати, почему этой задачей занялся? I>>>ты студент, аспирант, рабочий? т.е. где будет применяться и все такое D>>студент я, это курсовик... вот и занимаюсь...
I>ну и угораздило же тебя этим заняться
эт точно это меня препод надоумил , а я блин и согласился... I>что так поздно спохватился?
да не поздно, я давно им уже занимаюсь, просто мне не только этот алгоритм для курсовика нужен, пообещал преподу что напишу и этот алгоритм , а взялся
и все оказалось значительно хуже чем я предполагал... I>вот отсканил, держи: здесь
спасибо ща буду разбираться
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Steb by Step пока от монитора не ослеп :shuffle: ...
Здравствуйте, Decker, Вы писали:
D>Так вот какая картина для меня пока вырисовывается...
D>Просмотр(размер,матрица, сумма текущих приведений СТП)
D>{
D> 1. Проверяем не достигли ли размера == 2
D> если достигли, то добавляем последнее
D> ребро в результирующии набор. считаем длину.
D> если лучше рекорда взять как новый рекорд. выходим.
D> 2. Приводим матрицу, получаем нули, выбираем нуль с максимальной оценкой
D> сохраняем результат суммы приведения с оценкой выбранного нуля(СП + НОУ)
D> 3. if (СТП+СП < рекорд)
D> {
D> берем выше выбранное ребро, исключаем в матрице соответственно ему строку и столбец;
D> вычисляем дугу, приводящий к короткому циклу, и запрещаем его;
D> ПРОСМОТР(размер-1,матрица, СТП + СП);
D> восстанавливаем в матрице дугу короткого цикла, а также строку и столбец
D> if(СТП+СП+оценка дуги < рекорда)
D> {
D> в матрице блокируем толко 1 узел.
D> ПРОСМОТР(размер,матрица, СТП + СП);
D> раз блокируем толко 1 узел.
D> }
D> }
D>}
вот так.
а) размер проще уменьшенный просто рекурсивно подавать, а то у тебя обратного увеличения не было
б) не было восстанавления матрицы
в) не было запрета короткого цикла и его восстановление
г) не было восстановление запрета дуги
д) просмотр после запрета имеет нижнюю оценку Ноу + СП + оценка дуги, но там надо передавать сумму констант приведения, т.е. вместо Просмотр(размер,матрица, Ноу) точнее нужно написать Просмотр(размер,матрица,сумма текущих приведений). это связано с тем, что матрица узла представляет задачу, которая по сотимости отличается от начальной на эту сумму. эта самая сумма м.б. взята как нижняя оценка, но иногда удается найти более высокую, большую нижнюю оценку как СТП + СП + оценка дуги
D>неполная картина, где-то я что-то упустил. D>было бы здорово посмотреть как написано в оригинале D>буду надеяться увидеть отсканеный материал
уже выложил
Здравствуйте, Decker, Вы писали:
I>>ну и угораздило же тебя этим заняться D>эт точно это меня препод надоумил , а я блин и согласился...
где учишься?
I>>что так поздно спохватился? D>да не поздно, я давно им уже занимаюсь, просто мне не только этот алгоритм для курсовика нужен, пообещал преподу что напишу и этот алгоритм , а взялся D>и все оказалось значительно хуже чем я предполагал...
все проще. я начал с того что в руки попал на английском книжка где было все на пальцах показано и прога на паскале хитрая реализация, его перенес и так началось
I>>вот отсканил, держи: здесь D>спасибо ща буду разбираться
в общем, там больше словесного описания, без ярко выраженных алгоритмов
Здравствуйте, ilnar, Вы писали:
I>Здравствуйте, Decker, Вы писали:
I>>>ну и угораздило же тебя этим заняться D>>эт точно это меня препод надоумил , а я блин и согласился... I>где учишься?
Ярослвский Государственный Универ, математ факультет. 4 курс
I>>>что так поздно спохватился? D>>да не поздно, я давно им уже занимаюсь, просто мне не только этот алгоритм для курсовика нужен, пообещал преподу что напишу и этот алгоритм , а взялся D>>и все оказалось значительно хуже чем я предполагал... I>все проще. я начал с того что в руки попал на английском книжка где было все на пальцах показано и прога на паскале хитрая реализация, его перенес и так началось
а на паскаль реализацию можно посмотреть ???
I>>>вот отсканил, держи: здесь D>>спасибо ща буду разбираться I>в общем, там больше словесного описания, без ярко выраженных алгоритмов
да, я прочитал все, картина вырисовалась полностью, ща писать буду
кстати ты на чем пишешь, какая у тя скорострельность алгоритма получилась ??
на что ориентироваться ???
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Steb by Step пока от монитора не ослеп :shuffle: ...
Здравствуйте, Decker, Вы писали:
D>а на паскаль реализацию можно посмотреть ???
с этим также надо сканировать. но отличительная особенность — эти бумажки еще найти надо )))
D>да, я прочитал все, картина вырисовалась полностью, ща писать буду
D>кстати ты на чем пишешь, какая у тя скорострельность алгоритма получилась ?? D>на что ориентироваться ???
пишу на си плюсах
не заню даже как тебе описать скорость, на пне 3 ГГц за секунду просматривает в среднем 30000+-5000 узлов размера матрицы до 100х100
совсем случайные задачи 100х100 решаются в среднем за 15 минут, редко переваливают за час. но это случайные, т.к. есть тесты в интернете такие что даже 40х40 с трудом решаются. ветвлений много, отсечения мало
на что ориентриваться? во первых, минизируй выделения/удаления памяти, иначе для сравнения, реализация руководителя с созданием новых матриц при ветвлении откровенно отстает, как-то показал ему анализ запуска его программы под AQTime, так там 70-95% времени на malloc/free ушло
D>>Так вот какая картина пока вырисовывается...
I>
D>>Просмотр(размер,матрица, сумма текущих приведений СТП)
D>>{
D>> 1. Проверяем не достигли ли размера == 2
D>> если достигли, то добавляем последнее
D>> ребро в результирующии набор. считаем длину.
D>> если лучше рекорда взять как новый рекорд. выходим.
D>> 2. Приводим матрицу, получаем нули, выбираем нуль с максимальной оценкой
D>> сохраняем результат суммы приведения с оценкой выбранного нуля(СП + НОУ)
D>> 3. if (СТП+СП < рекорд)
D>> {
D>> берем выше выбранное ребро, исключаем в матрице соответственно ему строку и столбец;
D>> вычисляем дугу, приводящий к короткому циклу, и запрещаем его;
D>> ПРОСМОТР(размер-1,матрица, СТП + СП);
D>> восстанавливаем в матрице дугу короткого цикла, а также строку и столбец
D>> if(СТП+СП+оценка дуги < рекорда)
D>> {
D>> в матрице блокируем толко 1 узел.
D>> ПРОСМОТР(размер,матрица, СТП + СП);
D>> раз блокируем толко 1 узел.
D>> }
D>> }
D>>}
I>
угу, разобрался... написал первый вариант
вроде работает, правда иногда рекурсия зацикливается
и стэк оверфлоуится, ща ищу где накосячил
а так если не эксепшен, то результат правильный
ща отыщу ошибку, и буду скорострельность шлейфовать
пока что не впечатляет
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Steb by Step пока от монитора не ослеп :shuffle: ...
I>пишу на си плюсах I>не заню даже как тебе описать скорость, на пне 3 ГГц за секунду просматривает в среднем 30000+-5000 узлов размера матрицы до 100х100
впринципе недурно I>совсем случайные задачи 100х100 решаются в среднем за 15 минут, редко переваливают за час. но это случайные, т.к. есть тесты в интернете такие что даже 40х40 с трудом решаются. ветвлений много, отсечения мало
а где на эти тесты посмотреть можно ????
как отшлейфую алгоритм сообщу о результатах.
да и еще, ты какие еще алгоритмы пробовал ???
кто самый скорострельный ???
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Steb by Step пока от монитора не ослеп :shuffle: ...
Здравствуйте, Decker, Вы писали:
D>угу, разобрался... написал первый вариант D>вроде работает, правда иногда рекурсия зацикливается
это как? тут же дерево решений, оно не имеет цикла!!!
D>и стэк оверфлоуится, ща ищу где накосячил
ну, если много переменных как локальные переменные делаешь, то конечно вылет удет. 1мб по умолчанию в виндах, так кажется. выделяй массивы в памяти, например, для приведений
D>а так если не эксепшен, то результат правильный
еще есть момент, когда в строке или столбце останется единственный не запрещенный элемент, его надо взять в первую очередь, и правой ветки в этом случае не будет. но если реализация нормальная, она автоматом так происходит.
если попадешь в узел со строкой или столбцом без элемента для выбора — не рассматривается — просто некуда
D>ща отыщу ошибку, и буду скорострельность шлейфовать D>пока что не впечатляет
Здравствуйте, Decker, Вы писали:
D>Здравствуйте, ilnar, Вы писали:
I>>пишу на си плюсах I>>не заню даже как тебе описать скорость, на пне 3 ГГц за секунду просматривает в среднем 30000+-5000 узлов размера матрицы до 100х100 D>впринципе недурно I>>совсем случайные задачи 100х100 решаются в среднем за 15 минут, редко переваливают за час. но это случайные, т.к. есть тесты в интернете такие что даже 40х40 с трудом решаются. ветвлений много, отсечения мало D>а где на эти тесты посмотреть можно ????
а поищи, tests atsp tsp
D>как отшлейфую алгоритм сообщу о результатах.
D>да и еще, ты какие еще алгоритмы пробовал ??? D>кто самый скорострельный ???
вот, разные алгоритмы, проги для симметричных задач можно поглядеть тут www.tsp.gatech.edu
в общем, метод Литтла хорош для несимметричных случайных задач.
симметричность и "плохая структура" довольно серьезно сбивает с толку, т.к. в дереве решений появляются зеркальные просмотры
пробую линейное программирование — обычную модель целочисленного ЛП
