Собственно нужен алгоритм литла, известный так же как алгоритм ветвей и границ приминительно к задаче коммивояжера.

Прошу в поиск не слать, я там был и более менее для себя выбрал кое что.

Проблема заключается в том что большинство линков ведет на словесное описание алгоритма
очень часто — неполное, в том плане, что при реализации алгоритма возникают тонкие моменты, в частности, при ветвлении, которые у разных авторов, описаны по разному, а еще хуже, вообще не описаны.

Было бы здорово, если б, кто-нибудь более четко описал алгоритм,
либо поделился реализацией. Спасибо.

Если кто то занимался данной проблемой и имеет какойнибудь стоящии материал, приму в дар спасибо.

А я думал что метод ветвей и границ это метод Гомори...

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

D>Если кто то занимался данной проблемой и имеет какойнибудь стоящии материал, приму в дар спасибо.

я занимался и занимаюсь. могу прокомментировать отдельные места, можешь задать вопросы.
описывать будет долго, извини, времени нет.
полное доступное описание можно найти в "Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. — Наука, 1975, 360с", стр 78-86

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

I>я занимался и занимаюсь. могу прокомментировать отдельные места, можешь задать вопросы.
во здорово...

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


I>полное доступное описание можно найти в "Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. — Наука, 1975, 360с", стр 78-86
было бы здорово посмотреть на это описание, но боюсь мои поиски электронного варианта в инете закончились неудачно

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

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

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

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

1. узел представляется текущей матрицей, где фиксации дуг (ребер) скрывают соотв. строку и столбец, а запрет — установка в бесконечность
2. выбирается для ветвления дуга с наибольшей оценкой, по описанию Литтла — это дуга с нулевой текущей стоимостью (в приведенной матрице)
3. выбор (фиксация) дуги удлиняет известную часть маршрута и уменьшает на 1 размерность матрицы
4. запрет дуги не изменяет известную часть маршрута, не меняет размерность матрицы, меняет 1 элемент матрицы.

I>>полное доступное описание можно найти в "Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. — Наука, 1975, 360с", стр 78-86
D>было бы здорово посмотреть на это описание, но боюсь мои поиски электронного варианта в инете закончились неудачно

подумаю как дать почитать, у меня бумажная копия страниц

в общем, схематично просмотр текущего узла.

процедура ПРОСМОТР(размер,матрица узла,НОУ)
0. если размер = 2, маршрут определяется однозначно, посчитать стоимость, если лучше текущего рекорда, взять как новый рекорд
1. сделать приведение матрицы суммой СП, посчитать нижнюю оценку узла (НОУ+СП)
2. если НОУ+СП не лучше текущего рекорда, выйти из процедуры
3. выбрать дугу для ветвления r->c
4. ПРОСМОТР(размер-1,приведенная матрица за исключением строки r и столбца c,НОУ+СП)
5. если (НОУ+СП+оценка дуги) лучше текущего рекорда, ПРОСМОТР(размер,приведенная матрица с запретом дуги r->c,НОУ+СП)
6. выйти

Здравствуйте, ilnar,
я так писал , все равно местами алгоритм выбирает неверный путь и получается
хорошии но не оптимальный маршрут может накосячил где...

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

D>Здравствуйте, ilnar,
D>я так писал , все равно местами алгоритм выбирает неверный путь и получается
D>хорошии но не оптимальный маршрут может накосячил где...

попробуй выложить исходники, или отправить на ilnarb на gmail.com
или опиши как делал.
у меня есть свои исходники, но они содержат много пока не опубликованные исследования, показывать не могу

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


I>1. узел представляется текущей матрицей, где фиксации дуг (ребер) скрывают соотв. строку и столбец, а запрет — установка в бесконечность
I>2. выбирается для ветвления дуга с наибольшей оценкой, по описанию Литтла — это дуга с нулевой текущей стоимостью (в приведенной матрице)
I>3. выбор (фиксация) дуги удлиняет известную часть маршрута и уменьшает на 1 размерность матрицы
I>4. запрет дуги не изменяет известную часть маршрута, не меняет размерность матрицы, меняет 1 элемент матрицы.
так тут все понятно


I>подумаю как дать почитать, у меня бумажная копия страниц
было бы здорово

I>в общем, схематично просмотр текущего узла.

I>процедура ПРОСМОТР(размер,матрица узла,НОУ)
так тут поподробнее НОУ--это что ???
I>0. если размер = 2, маршрут определяется однозначно, посчитать стоимость, если лучше текущего рекорда, взять как новый рекорд
I>1. сделать приведение матрицы суммой СП, посчитать нижнюю оценку узла (НОУ+СП)
что значит СП, в моем представлениии приведение это поиск минимального в каждой строке,вычтание этого минимального из каждого элемента строки
и добавление его в сумму приведения, затем то же самое для каждого столбца...
I>2. если НОУ+СП не лучше текущего рекорда, выйти из процедуры
так а где и как формируется текущии рекорд
I>3. выбрать дугу для ветвления r->c
I>4. ПРОСМОТР(размер-1,приведенная матрица за исключением строки r и столбца c,НОУ+СП)
I>5. если (НОУ+СП+оценка дуги) лучше текущего рекорда, ПРОСМОТР(размер,приведенная матрица с запретом дуги r->c,НОУ+СП)
I>6. выйти

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

вот и получается так что иногда при равенстве текущих обходов каждой из копии, следует не в тупую выбирать первую копию а просчитать на уровень вниз
как собственно и написано в описании, но как это реализовать что то не придумаю...

ваш вариант с рекурсией, выглядит многообещающе, щас я его обмозгую получше и посмотрю, что из этого может получиться...
если не сложно опишите эту схему несколько подробно...

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

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


I>>1. узел представляется текущей матрицей, где фиксации дуг (ребер) скрывают соотв. строку и столбец, а запрет — установка в бесконечность
I>>2. выбирается для ветвления дуга с наибольшей оценкой, по описанию Литтла — это дуга с нулевой текущей стоимостью (в приведенной матрице)
I>>3. выбор (фиксация) дуги удлиняет известную часть маршрута и уменьшает на 1 размерность матрицы
I>>4. запрет дуги не изменяет известную часть маршрута, не меняет размерность матрицы, меняет 1 элемент матрицы.
D>так тут все понятно


I>>подумаю как дать почитать, у меня бумажная копия страниц
D>было бы здорово

I>>в общем, схематично просмотр текущего узла.

I>>процедура ПРОСМОТР(размер,матрица узла,НОУ)
D>так тут поподробнее НОУ--это что ???
нижняя оценка узла
I>>0. если размер = 2, маршрут определяется однозначно, посчитать стоимость, если лучше текущего рекорда, взять как новый рекорд
I>>1. сделать приведение матрицы суммой СП, посчитать нижнюю оценку узла (НОУ+СП)
D>что значит СП, в моем представлениии приведение это поиск минимального в каждой строке,вычтание этого минимального из каждого элемента строки
D>и добавление его в сумму приведения, затем то же самое для каждого столбца...
I>>2. если НОУ+СП не лучше текущего рекорда, выйти из процедуры
D>так а где и как формируется текущии рекорд
в пункте 0, изначально равно бесконечности
I>>3. выбрать дугу для ветвления r->c
I>>4. ПРОСМОТР(размер-1,приведенная матрица за исключением строки r и столбца c,НОУ+СП)
I>>5. если (НОУ+СП+оценка дуги) лучше текущего рекорда, ПРОСМОТР(размер,приведенная матрица с запретом дуги r->c,НОУ+СП)
I>>6. выйти

D>я делал так(самый распространненное описание что удалось найти)
D>берется начальная матрица расстояний, делается приведение, затем оценка, затем выбирается узел , с максимальной оценкой,
D>делаем копии предыдущего узла, (узел хранит матрицу расстоянии , матрицу оценок, длину, теущее расстояние (изначально сумма приведения))
D>для первой копии блокируем ребро(строку столбец), для второй копии ставим запрет только в один элемент матрицы(ну запрет на одно ребро)
D>полученные матрицы обоих узлов приводятся, результат приведения добавляется к текущему обходу каждого из узлов(для каждой свой), затем если
D>теущии обход первой копии не больше текущего обхода второй копии , то новым "главным "узлом становится первая копия, в противном случае вторая
D>копия...
D>все это дело повторяется до тех пор пока не будут заблокированы все элементы матрицы...

D>вот и получается так что иногда при равенстве текущих обходов каждой из копии, следует не в тупую выбирать первую копию а просчитать на уровень вниз
D>как собственно и написано в описании, но как это реализовать что то не придумаю...

D>ваш вариант с рекурсией, выглядит многообещающе, щас я его обмозгую получше и посмотрю, что из этого может получиться...
D>если не сложно опишите эту схему несколько подробно...

1. матрицу не обязательно копировать, можно менять текущую и потом откатывать изменения — это быстрее.
2. есть 2 варианта выбора следующего узла:
а) выбор узла с фиксацией, потом с запретом
б) выбор того у которого нижняя оценка меньше. тогда сравнивать ли и с теми которые раньше появлялись? много памяти понадобится.
практика показывает что а) предпочтительно, причем очень заметно.
3. хороший просчет вперед требует много сложности, я пробовал О(куб) и О(четвертая) методы, затраты не оправдываются

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

I>1. матрицу не обязательно копировать, можно менять текущую и потом откатывать изменения — это быстрее.
ну насчет оптимизации это понятно, я про это думал, и уже прикинул где и как лучше будет сделать,
но только после того как заставлю этот алгоритм работать...
I>2. есть 2 варианта выбора следующего узла:
I>а) выбор узла с фиксацией, потом с запретом
так а выбирать то кого если результат раный ???
I>б) выбор того у которого нижняя оценка меньше. тогда сравнивать ли и с теми которые раньше появлялись? много памяти понадобится.
I>практика показывает что а) предпочтительно, причем очень заметно.
хорошо я учту это, но скорее всего попробую оба варианта, так сказать для себя...
I>3. хороший просчет вперед требует много сложности, я пробовал О(куб) и О(четвертая) методы, затраты не оправдываются
так все таки если не просчитывать вперед, мы ведь тогда не можем быдь уверены что получим точный результат ???

вот и еще вопрос, ведь мы новые ребра получаем не последовательно, значит нужно избежать замыкания отдельных обходов раньше времени
вот интересно как тут следует грамотнее сделать...

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

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

I>>1. матрицу не обязательно копировать, можно менять текущую и потом откатывать изменения — это быстрее.
D>ну насчет оптимизации это понятно, я про это думал, и уже прикинул где и как лучше будет сделать,
D>но только после того как заставлю этот алгоритм работать...
I>>2. есть 2 варианта выбора следующего узла:
I>>а) выбор узла с фиксацией, потом с запретом
D>так а выбирать то кого если результат раный ???
в смысле равный? в узле с фиксацией размер матрицы меньше на 1, а на оценку не смотри, выбор узла с нулем дает нулевой прирост стоимости, это потом оценка уточняется, а для узла с запретом оценка увеличивается на величину ...
I>>б) выбор того у которого нижняя оценка меньше. тогда сравнивать ли и с теми которые раньше появлялись? много памяти понадобится.
I>>практика показывает что а) предпочтительно, причем очень заметно.
D>хорошо я учту это, но скорее всего попробую оба варианта, так сказать для себя...
у Конвей это описано.
I>>3. хороший просчет вперед требует много сложности, я пробовал О(куб) и О(четвертая) методы, затраты не оправдываются
D>так все таки если не просчитывать вперед, мы ведь тогда не можем быдь уверены что получим точный результат ???
алгоритм дает точный результат, если правильно считать нижнюю оценку узла и правильно фиксировать стоимость рекордов.

D>вот и еще вопрос, ведь мы новые ребра получаем не последовательно, значит нужно избежать замыкания отдельных обходов раньше времени
D>вот интересно как тут следует грамотнее сделать...
да, это возникает при фиксации дуги и называется запретом короткого цикла.
как вычислить какую дугу запретить, зависит как фиксации хранишь.
если фиксация чистого i->j, то запрет обратной дуги, если какой-то связанный, в самом широком случае s->..->i->j->..->t, то запрет t->s
я делаю так: храню дуги вперед и назад, иду вперед начиная с j, назад начиная с i, и потом запрет

// это фиксация дуги, убрать фиксацию путем обнуления соотв.
fwdptr[i] = j;
backptr[j] = i;
// поиск дуги приводящего к короткому циклу
last = fwdptr[i];
while(fwdptr[last]!=0) last = fwdptr[last];
first = backptr[j];
while(backptr[back]!=0) first = backptr[first];

и запрещаю last->first

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

I>в общем, схематично просмотр текущего узла.

I>процедура ПРОСМОТР(размер,матрица узла,НОУ)
I>0. если размер = 2, маршрут определяется однозначно, посчитать стоимость, если лучше текущего рекорда, взять как новый рекорд
так а стоимость откуда берется ????
I>1. сделать приведение матрицы суммой СП, посчитать нижнюю оценку узла (НОУ+СП)
так , считаем нижнюю оценку узла для предварительно найденого ребра(т.е 0 с максимальной оценкой) ????
I>2. если НОУ+СП не лучше текущего рекорда, выйти из процедуры
I>3. выбрать дугу для ветвления r->c
те ту что выбрали в п.1 ???
выбор -- т.е. добавление в результирующии набор ???
I>4. ПРОСМОТР(размер-1,приведенная матрица за исключением строки r и столбца c,НОУ+СП)
тут вроде понятно...
I>5. если (НОУ+СП+оценка дуги) лучше текущего рекорда, ПРОСМОТР(размер,приведенная матрица с запретом дуги r->c,НОУ+СП)
тут тоже...
I>6. выйти

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

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

I>>в общем, схематично просмотр текущего узла.

I>>процедура ПРОСМОТР(размер,матрица узла,НОУ)
I>>0. если размер = 2, маршрут определяется однозначно, посчитать стоимость, если лучше текущего рекорда, взять как новый рекорд
D>так а стоимость откуда берется ????
или нижняя оценка + последнее приведение, если нижняя оценка корректна для определения стоимости, у Литтла это так (по теореме о константном изменении стоимости при приведении матрицы на эту константу), а в общем случае может не быть так, если успользуются другие схемы определения нижней оценки.
или посчитать стоиомть маршрута по матрице задачи (не приведенной, не измененной)

I>>1. сделать приведение матрицы суммой СП, посчитать нижнюю оценку узла (НОУ+СП)
D>так , считаем нижнюю оценку узла для предварительно найденого ребра(т.е 0 с максимальной оценкой) ????
нет. узел м.б. как после фиксации ребра, так и после запрета. в этой матрице если удается сделать дополнительное приведение, делаем это, прибавляем сумму констант приведения к предыдущей нижней оценке, получаем новую нижнюю оценку для приведенной матрицы узла

I>>2. если НОУ+СП не лучше текущего рекорда, выйти из процедуры
I>>3. выбрать дугу для ветвления r->c
D>те ту что выбрали в п.1 ???
D>выбор -- т.е. добавление в результирующии набор ???
нет. в п.1. нет выбора. выбор делается среди нулей, которые образовались после приведения матрицы в п.1.

I>>4. ПРОСМОТР(размер-1,приведенная матрица за исключением строки r и столбца c,НОУ+СП)
D>тут вроде понятно...
I>>5. если (НОУ+СП+оценка дуги) лучше текущего рекорда, ПРОСМОТР(размер,приведенная матрица с запретом дуги r->c,НОУ+СП)
D>тут тоже...
I>>6. выйти

Здравствуйте, Аноним, Вы писали:

А>А я думал что метод ветвей и границ это метод Гомори...

нет. метод ветвей и границ — это схема решения путем ветвления задачи на подзадачи и отсечения заведомо плохих подзадач
в частности, для задачи коммивояжера — это метод Литтла,
для целочисленного линейного программирования — метод Ланд и Дойга

а метод гомори — последовательное уточнение задачи новыми ограничениями

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

D>Собственно нужен алгоритм литла, известный так же как алгоритм ветвей и границ приминительно к задаче коммивояжера.

кстати, почему этой задачей занялся?
ты студент, аспирант, рабочий? т.е. где будет применяться и все такое

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

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

D>>Собственно нужен алгоритм литла, известный так же как алгоритм ветвей и границ приминительно к задаче коммивояжера.

I>кстати, почему этой задачей занялся?
I>ты студент, аспирант, рабочий? т.е. где будет применяться и все такое
студент я, это курсовик... вот и занимаюсь...

Здравствуйте, ilnar,
ща обдумаю все и буду снова вопросы задавать...
жалко, что оригинал не посмотреть... меньше вопросов было бы

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

D>Здравствуйте, ilnar,
D>ща обдумаю все и буду снова вопросы задавать...
D>жалко, что оригинал не посмотреть... меньше вопросов было бы

да я постоянно домой под ночь прихожу, моюсь и спать.
нужно нормально прийти, и тогда на сканере отсканить и увидишь заветную бумажку

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

I>>>в общем, схематично просмотр текущего узла.

I>>>процедура ПРОСМОТР(размер,матрица узла,НОУ)
I>>>0. если размер = 2, маршрут определяется однозначно, посчитать стоимость, если лучше текущего рекорда, взять как новый рекорд
D>>так а стоимость откуда берется ????
I>или нижняя оценка + последнее приведение, если нижняя оценка корректна для определения стоимости, у Литтла это так (по теореме о константном изменении стоимости при приведении матрицы на эту константу), а в общем случае может не быть так, если успользуются другие схемы определения нижней оценки.
I>или посчитать стоиомть маршрута по матрице задачи (не приведенной, не измененной)
так а как у Литла определяется НОУ ??? и Что значит нижняя оценка корректна для определения стоимости...

I>>>1. сделать приведение матрицы суммой СП, посчитать нижнюю оценку узла (НОУ+СП)
D>>так , считаем нижнюю оценку узла для предварительно найденого ребра(т.е 0 с максимальной оценкой) ????
I>нет. узел м.б. как после фиксации ребра, так и после запрета. в этой матрице если удается сделать дополнительное приведение, делаем это, прибавляем сумму констант приведения к предыдущей нижней оценке, получаем новую нижнюю оценку для приведенной матрицы узла

I>>>2. если НОУ+СП не лучше текущего рекорда, выйти из процедуры
I>>>3. выбрать дугу для ветвления r->c
D>>те ту что выбрали в п.1 ???
D>>выбор -- т.е. добавление в результирующии набор ???
I>нет. в п.1. нет выбора. выбор делается среди нулей, которые образовались после приведения матрицы в п.1.
что-то не поиму на какой стадии выбирается новая дуга...
я думал, что это один из нулей, полученный после очередного приведения, имеющии максимальную оценку...
и более того не поиму, когда она добавляется в результирующии набор...

Так вот какая картина для меня пока вырисовывается...
Просмотр(размер,матрица, Ноу)
{
1. Проверяем не достигли ли размера == 2
если достигли, то добавляем последнее
ребро в результирующии набор. считаем длину.
если лучше рекорда взять как новый рекорд. выходим.

2. Приводим матрицу, получаем нули, выбираем нуль с максимальной оценкой
сохраняем результат суммы приведения с оценкой выбранного нуля(СП + НОУ)

3. if (НОУ+СП >= рекорд)
выход.
else
{
берем выше выбранное ребро, исключаем в матрице соответственно ему
строку и столбец, уменьшаем размер на 1;
ПРОСМОТР(размер,матрица, Ноу + СП);

если вышли из ПРОСМОТР(размер,матрица, Ноу)

if(НОУ+СП+оценка дуги < рекорда)
{
в матрице блокируем толко 1 узел.
ПРОСМОТР(размер,матрица, Ноу + СП+оценка);
}
если нет выходим.
}
}
неполная картина, где-то я что-то упустил.
было бы здорово посмотреть как написано в оригинале
буду надеяться увидеть отсканеный материал

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

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

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

D>>>Собственно нужен алгоритм литла, известный так же как алгоритм ветвей и границ приминительно к задаче коммивояжера.

I>>кстати, почему этой задачей занялся?
I>>ты студент, аспирант, рабочий? т.е. где будет применяться и все такое
D>студент я, это курсовик... вот и занимаюсь...

ну и угораздило же тебя этим заняться
что так поздно спохватился?
вот отсканил, держи: здесь

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

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

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

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

D>>>>Собственно нужен алгоритм литла, известный так же как алгоритм ветвей и границ приминительно к задаче коммивояжера.

I>>>кстати, почему этой задачей занялся?
I>>>ты студент, аспирант, рабочий? т.е. где будет применяться и все такое
D>>студент я, это курсовик... вот и занимаюсь...

I>ну и угораздило же тебя этим заняться
эт точно это меня препод надоумил , а я блин и согласился...
I>что так поздно спохватился?
да не поздно, я давно им уже занимаюсь, просто мне не только этот алгоритм для курсовика нужен, пообещал преподу что напишу и этот алгоритм , а взялся
и все оказалось значительно хуже чем я предполагал...
I>вот отсканил, держи: здесь
спасибо ща буду разбираться

Здравствуйте, 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>в общем, там больше словесного описания, без ярко выраженных алгоритмов
да, я прочитал все, картина вырисовалась полностью, ща писать буду

кстати ты на чем пишешь, какая у тя скорострельность алгоритма получилась ??
на что ориентироваться ???

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

D>а на паскаль реализацию можно посмотреть ???
с этим также надо сканировать. но отличительная особенность — эти бумажки еще найти надо )))

D>да, я прочитал все, картина вырисовалась полностью, ща писать буду

D>кстати ты на чем пишешь, какая у тя скорострельность алгоритма получилась ??
D>на что ориентироваться ???
пишу на си плюсах
не заню даже как тебе описать скорость, на пне 3 ГГц за секунду просматривает в среднем 30000+-5000 узлов размера матрицы до 100х100
совсем случайные задачи 100х100 решаются в среднем за 15 минут, редко переваливают за час. но это случайные, т.к. есть тесты в интернете такие что даже 40х40 с трудом решаются. ветвлений много, отсечения мало
на что ориентриваться? во первых, минизируй выделения/удаления памяти, иначе для сравнения, реализация руководителя с созданием новых матриц при ветвлении откровенно отстает, как-то показал ему анализ запуска его программы под AQTime, так там 70-95% времени на malloc/free ушло

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



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>

угу, разобрался... написал первый вариант
вроде работает, правда иногда рекурсия зацикливается
и стэк оверфлоуится, ща ищу где накосячил
а так если не эксепшен, то результат правильный

ща отыщу ошибку, и буду скорострельность шлейфовать
пока что не впечатляет

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


I>пишу на си плюсах
I>не заню даже как тебе описать скорость, на пне 3 ГГц за секунду просматривает в среднем 30000+-5000 узлов размера матрицы до 100х100
впринципе недурно
I>совсем случайные задачи 100х100 решаются в среднем за 15 минут, редко переваливают за час. но это случайные, т.к. есть тесты в интернете такие что даже 40х40 с трудом решаются. ветвлений много, отсечения мало
а где на эти тесты посмотреть можно ????

как отшлейфую алгоритм сообщу о результатах.

да и еще, ты какие еще алгоритмы пробовал ???
кто самый скорострельный ???

Здравствуйте, 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

в общем, метод Литтла хорош для несимметричных случайных задач.
симметричность и "плохая структура" довольно серьезно сбивает с толку, т.к. в дереве решений появляются зеркальные просмотры
пробую линейное программирование — обычную модель целочисленного ЛП