Существует ли софт решающий "Задачу Коммивояжера"? - Public forum of MSU united student networks

Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.fds-net.ru/showflat.php?Number=1299225&src=arc&showlite=
Дата изменения: Unknown
Дата индексирования: Wed Apr 13 05:57:45 2016
Кодировка: Windows-1251

Root \| Google \| Yandex \| Mail.ru \| Kommersant \| Afisha \| LAN Support

Technical >> Hard&Soft (Archive)

Страницы: 0 | 20 | показать все | след. страница

Lenin

enthusiast

Рег.: 05.02.2003

Сообщений: 251

Рейтинг: 0

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

Если существует, то где и как можно его достать?

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

Я слышал, что вроде бы кто-то разрабатывал софтину применительно для грузоперевозок по Москве. Этот вариант был бы для меня наилучшим.

Rialto

Кораблик в плавании

Рег.: 07.11.2003

Сообщений: 6388

Рейтинг: 6305

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 11:59

Ботай графы

Каждый хомяк в жизни должен сделать 3 вещи:пожрать, поспать и сдохнуть...

Lenin

enthusiast

Рег.: 05.02.2003

Сообщений: 251

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Rialto]
23.06.2004 12:11

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

В ответ на:

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

Rialto

Кораблик в плавании

Рег.: 07.11.2003

Сообщений: 6388

Рейтинг: 6305

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 12:18

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

Каждый хомяк в жизни должен сделать 3 вещи:пожрать, поспать и сдохнуть...

TAS

Carpal Tunnel

Рег.: 28.10.2003

Сообщений: 2858

Из: solovei.local

Рейтинг: 389

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 12:24

> Алгоритмы решающие эту хрень я знаю

Надеюсь приближенное решение ?

Счастье есть, его не может не быть!

Dio

Дятел

Рег.: 18.09.2002

Сообщений: 5639

Из: Москва, не в ГЗ

Рейтинг: 10

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: TAS]
23.06.2004 12:25

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

Куплюклавиатурусработающимпробелом

Nik

addict

Рег.: 31.12.2002

Сообщений: 616

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 12:33

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

Редактировал Nik (23.06.2004 12:34)

Lenin

enthusiast

Рег.: 05.02.2003

Сообщений: 251

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Nik]
23.06.2004 12:38

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

Kaby

Pooh-Bah

Рег.: 02.01.2003

Сообщений: 2337

Из: Kazakhstan

Рейтинг: 19

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 12:47

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

Nik

addict

Рег.: 31.12.2002

Сообщений: 616

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 12:47

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

Kaby

Pooh-Bah

Рег.: 02.01.2003

Сообщений: 2337

Из: Kazakhstan

Рейтинг: 19

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Nik]
23.06.2004 12:49

В ответ на:

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

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

Nik

addict

Рег.: 31.12.2002

Сообщений: 616

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Kaby]
23.06.2004 12:52

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

Dio

Дятел

Рег.: 18.09.2002

Сообщений: 5639

Из: Москва, не в ГЗ

Рейтинг: 10

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Nik]
23.06.2004 12:53

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

Куплюклавиатурусработающимпробелом

Lenin

enthusiast

Рег.: 05.02.2003

Сообщений: 251

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Nik]
23.06.2004 12:57

А точное и не требуется.

Я получу наиболее выгодное с заданной погрешностью.

...Эхх ...неужели программить придется?...

Kaby

Pooh-Bah

Рег.: 02.01.2003

Сообщений: 2337

Из: Kazakhstan

Рейтинг: 19

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 13:03

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

Kaby

Pooh-Bah

Рег.: 02.01.2003

Сообщений: 2337

Из: Kazakhstan

Рейтинг: 19

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 13:03

А зачем тебе?

Nik

addict

Рег.: 31.12.2002

Сообщений: 616

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 13:06

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

Lenin

enthusiast

Рег.: 05.02.2003

Сообщений: 251

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Kaby]
23.06.2004 13:09

В ответ на:

А зачем тебе?

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

...А что случится если будет, например 15 мест погрузки?...

Lenin

enthusiast

Рег.: 05.02.2003

Сообщений: 251

Рейтинг: 0

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Nik]
23.06.2004 13:11

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

Shurick

Bad Man

Рег.: 30.08.2002

Сообщений: 6379

Рейтинг: 303

Re: Существует ли софт решающий "Задачу Коммивояжера"? [re: Lenin]
23.06.2004 13:12

> Так вот наши менеджеры себе головы поломали пока придумали
> хоть какой-то выгодный вариант (на весь этот расчет они потратили несколько часов)

Вован, подумай только, сколько народа ты оставишь без работы.

PS: А 8 - это ж совсем не много, тут и полного перебора не жалко.

Страницы: 0 | 20 | показать все | след. страница

Technical >> Hard&Soft (Archive)

Дополнительная информация
0 зарегистрированных и 1 анонимных пользователей просматривают этот форум. Модераторы: exc, muse, Riamella, KAA Печать темы >>	Права Вы можете создавать новые темы Вы можете отвечать на сообщения HTML отключен UBBCode включен	Рейтинг: Просмотров темы:
		Переход в