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

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

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

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

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

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

Здравствуйте, 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>студент я, это курсовик... вот и занимаюсь...

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