Существует ли софт решающий "Задачу Коммивояжера"?

dchumach

Если существует, то где и как можно его достать?
Суть задачи (в широком смысле):
Есть несколько городов, между которыми есть маршруты определенной длины. Задача заключается в том, чтобы найти оптимальный путь обхода этих городов.
Я слышал, что вроде бы кто-то разрабатывал софтину применительно для грузоперевозок по Москве. Этот вариант был бы для меня наилучшим.

Impils

Ботай графы

dchumach

Алгоритмы решающие эту хрень я знаю, и прогу написать я тоже могу. Вопрос в другом:

Существует ли софт ...

Impils

Когда ты напишешь прогу, это и будет софт

Varvara2002

> Алгоритмы решающие эту хрень я знаю
Надеюсь приближенное решение ?

sergei1969

конечно точное!
полный перебор рулит

teonazoi

А задачка не является NPC?
Полиномиального алгоритма нет(пока он не известен).

dchumach

Она достаточно хорошо решается "Генетическим Алгоритмом"

rid2000

А что ты подразумеваешь под "софтом"?
Решение задачи Коммивояжера - является алгоритмом. А алгоритмы не есть софт.
А где применяются такие алгоритмы ? Наверно, в Microfoft-е...

teonazoi

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

rid2000

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

Полиномиальность решения не говорит о неразрешимости задачи

teonazoi

Нет, ты не понял. Применяя генетические алгоритмы он может получить не оптимальное решение!

sergei1969

а может даже далеко не оптимальное
но о неразрешимости речи не идёт

dchumach

А точное и не требуется.
Я получу наиболее выгодное с заданной погрешностью.
...Эхх ...неужели программить придется?...

rid2000

Да лана...
Одно дело софт, а другое дело исходники искать... Задача общеизвестна, сорсы надо искать в нете

rid2000

А зачем тебе?

teonazoi

Мне интересно, как ты определишь погрешность не зная оптимального решения.
Разница между итерациями не есть погрешность

dchumach

А зачем тебе?

Да я в транспортной конторе работаю... Так вот в прошлую пятницу надо было из 8 мест в москве забрать грузы и погрузить все это в вагон. Имелось несколько разных транспортных средств, с разной стоимостью и грузоподъемностью.
Так вот наши менеджеры себе головы поломали пока придумали хоть какой-то выгодный вариант (на весь этот расчет они потратили несколько часов)
...А что случится если будет, например 15 мест погрузки?...

dchumach

Для начала ограничу по времени, а потом по финансам

Chupa

> Так вот наши менеджеры себе головы поломали пока придумали
> хоть какой-то выгодный вариант (на весь этот расчет они потратили несколько часов)
Вован, подумай только, сколько народа ты оставишь без работы.
PS: А 8 - это ж совсем не много, тут и полного перебора не жалко.

dchumach

>Вован, подумай только, сколько народа ты оставишь без работы.
Зато я заработаю (или ты! )
Контора ведь будет гораздо меньше ресурсов тратить на расчет!
P>PS: А 8 - это ж совсем не много, тут и полного перебора не жалко.
Сегодня - 8, завтра 10, через полгода 100,...
А контор в Москве, нуждающихся в в подобных расчетах - до жопы!
А если еще решить и "Задачу упаковки рюкзака"!...

ahiles27

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

dchumach

А криптографию как сюда прицепить?

Patun

дядя, бери genehunter (примочка для excela) и считай за пару минут
если влом - почитай про сеть хопфилда, обычно рядом всегда этот пример приводится - там все очень понятно и просто, рюхнешь за полчаса

irinkina

Можешь пообщаться к Кибой на эту тему, это как-раз была темя его диссера...

ahiles27

тогда P = NP