[Need]Задача коммивояжёра

[fabulous]

Может у кого-то есть проект, написан на с++ или с# :решение задачи о
коммивояжёре методом динамического программирования.

Вознаграждение гарантирую.

Заранее благодарен.

P.S. У самого нет времени писать прогу.

[['.ZeR0'.access] Eugene K.]

Post by fabulous
Может у кого-то есть проект, написан на с++ или с# :решение задачи о
коммивояжёре методом динамического программирования.

А как это задача про торговца дин прогом решается? )) Есть типа битоническая
задача коммивояжера ... Перефразированная задача была на международной
олимпиаде под названием "Канадские авиалинии"...

и у меня была где-то реализация на Паскале... только дома.

[fabulous]

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

[Koshel S.S.]

Post by fabulous
Да вот в том то и проблема, что задача решается динамическим
программированием, если ты ,конечно, не путаешь понятия. А вот
реализации этого решения я в инете не могу найти.

Неужели уже решается? :)) Года два назад решалась только перебором с
отсечениями...

[fabulous]

По-прежнему нет достаточно эффективного алгоритма решения задачи
коммивояжёра. Решается она либо методом ветвей и границ, либо простым
перебором, либо методом динамического программирования. Я спрашивал у
кого есть прога, а не кто что думает по этому поводу=)

[['.ZeR0'.access] Eugene K.]

Post by fabulous
По-прежнему нет достаточно эффективного алгоритма решения задачи
коммивояжёра.

Та патаму шо эНПэ полная это задача

Post by fabulous
Решается она либо методом ветвей и границ, либо простым перебором,

ну дапустим

Post by fabulous
либо методом динамического программирования.

того, кто сказал тебе этот бред, можешь застрелить

Post by fabulous
Я спрашивал у кого есть прога, а не кто что думает по этому поводу=)

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

[fabulous]

Ну, тогда получается зря авторы книг расписывали решение на n-ое
количество страниц, ведь ты говоришь, что она не решается методом
динамического программирования. Значит, большая часть курса
математические модели исследования операций коту под хвост. Зря ходим на
пары, ведь лектор нагло врёт.

[Aleksey Salow]

ня fabulous

Post by fabulous
Ну, тогда получается зря авторы книг расписывали решение на n-ое
количество страниц, ведь ты говоришь, что она не решается методом
динамического программирования. Значит, большая часть курса
математические модели исследования операций коту под хвост. Зря ходим на
пары, ведь лектор нагло врёт.

Преподы это такой класс людей, которые местами такие вещи говорят, что
ой!

[Oleg Grodzevich]

Post by ['.ZeR0'.access] Eugene K.

Post by fabulous
По-прежнему нет достаточно эффективного алгоритма решения задачи
коммивояжёра.

Та патаму шо эНПэ полная это задача

Ну просто собрались специалисты по computational complexity. Мало знать
умные слова, надо еще понимать, что они означают.

Post by ['.ZeR0'.access] Eugene K.

Post by fabulous
Решается она либо методом ветвей и границ, либо простым перебором,
либо методом динамического программирования.

того, кто сказал тебе этот бред, можешь застрелить

Проще самому застрелиться (или об стену). Задача коммивояжера, таки да,
представьте себе решается методом динамического программирования. Другой
вопрос, что сложность Omega(2^n) (причем и по памяти и по итерациям), но
если n маленькое, то почему бы и нет. Все же лучше чем полный перебор
из n! вариантов.

Post by ['.ZeR0'.access] Eugene K.
еще раз повторяю: есть задача коммивояжера, в которой рассматриваются
только битонические пути... Эта задача проще и решается дин прогом.
и на всемирке была типа "Canadian Airlines"

Ну и причем тут это? Любая задача решается (даже о смысле жизни),
главное иметь правильную аксиоматику и достаточно ресурсов :)

[['.ZeR0'.access] Eugene K.]

Задача коммивояжера, таки да,представьте себе решается методом
динамического программирования. >Другой
вопрос, что сложность Omega(2^n) (причем и по памяти и по итерациям), но
если n маленькое, то почему бы и нет. Все же лучше чем полный перебор
из n! вариантов.

я был не прав...каюсь

Post by ['.ZeR0'.access] Eugene K.
еще раз повторяю: есть задача коммивояжера, в которой рассматриваются
только битонические пути... Эта задача проще и решается дин прогом.
и на всемирке была типа "Canadian Airlines"

Ну и причем тут это? Любая задача решается (даже о смысле жизни),
главное иметь правильную аксиоматику и достаточно ресурсов :)

та при том, что, может, препод имел ввиду ту задачу...

[Oleg Grodzevich]

Post by Koshel S.S.

Post by fabulous
Да вот в том то и проблема, что задача решается динамическим
программированием,

Неужели уже решается? :)) Года два назад решалась только перебором с
отсечениями...

Смотрю на полку, беру первую попавшуюся по тематике книжку (Combinatorial
algorithms: theory and practice), открываю, нахожу решение задачи
методом динамического программирования, закрываю, смотрю год издания - 1977,
ставлю обратно на полку. Комментарии, как говорится, излишни.

PS: года два назад, не смешите мои тапочки...

[Anatoly Borodin]

Shalom!

f> Да вот в том то и проблема, что задача решается динамическим
f> программированием, если ты ,конечно, не путаешь понятия. А вот
f> реализации этого решения я в инете не могу найти.

Это такой секретный метоб Пентагона, потому его и нет в инете.

[Oleg Grodzevich]

Post by fabulous
Да вот в том то и проблема, что задача решается динамическим
программированием, если ты ,конечно, не путаешь понятия. А вот
реализации этого решения я в инете не могу найти.

Ну алгоритмы описаны на каждом углу, я вот нагуглил за 5 секунд
www.cs.aueb.gr/csgrad/algorithms/L17-DP-TSP.pdf
А так чтобы сразу, и готовое и прямо таки на C++ или C# -- это
вы, батенька, губу то раскатали. Уж сесть и закодить простейший
рекурсивный алгоритм можно за пару часов, ну еще денек на какой
никакой интерфейс к нему, коли уж так сильно нужно.