Форум
» Назад на решение задач по физике и термеху
Регистрация | Профиль | Войти | Забытый пароль | Присутствующие | Справка | Поиск

» Добро пожаловать, Гость: Войти | Регистрация
    Форум
    Информационные технологии
        Задача коммивояжера, динамическое программирование
Отметить все сообщения как прочитанные   [ Помощь ]
» Добро пожаловать на форум "Информационные технологии" «

Переход к теме
<< Назад Вперед >>
Одна страница
Модераторы: paradise, KMA
  

nuker


Удален

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

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 27 июля 2005 22:30 | IP
Guest



Новичок

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

Всего сообщений: Нет | Присоединился: Never | Отправлено: 12 сен. 2005 18:09 | IP
VF



Administrator

Guest
Задача NP-полная и для перебора большого числа точек действительно требует слишком больших вычислительных ресурсов. Поэтому при решении используются различные оптимизации и упрощения.

А нейронные сети давно научились моделировать на обычных компьютерах.

Всего сообщений: 3109 | Присоединился: май 2002 | Отправлено: 12 сен. 2005 18:16 | IP
bolega


Удален

Есть хорошая книга
Travelling Saleseman Problem and its variations.
840 pages.
Искать в колхозе.

Задача неплохо решается (приближенно естесственно) динамическим программированием.
Исходники на С (также как и исходники еще десятков разных комбинаторно-оптимизационных задач) были когда-то на сайте корейского института operational research. Сайт уже больше года как исчез, не знаю, может быть переименовался. Назывался ORLab. Поищи, может найдешь куда он делся.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 12 сен. 2005 18:29 | IP
Jett


Удален

Посмотри, если найдешь.
Программирование искусственного интеллекта в приложениях
Серия: Внесерийные книги
Автор: М. Тим Джонс
ISBN: 5-94074-275-0
Год выхода: 2004
Кол-во страниц: 312
Цена: 150 руб.
нттп://www.dmk.ru
И посмотри: поиск пути методом муравья.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 19 окт. 2005 11:51 | IP
mnk


Удален

Недавно выложил текст книги Тима Джонса (про муравьев)  на
http://vuz.exponenta.ru в разделы МАМИ и МЭИ.

Всего сообщений: N/A | Присоединился: N/A | Отправлено: 29 окт. 2005 9:32 | IP
Sedjj


Новичок

Здравствуйте!!!!!
Помогите пожалуйста решить задачку))))

Имеется n населенных пунктов, перенумерованные от 1 до n(n-10). Некоторые пары пунктов присоединены к дорогам. Определить, можно ли попасть по этим дорогам из 1-го пункта в n-й. Информация о дорогах задается в виде последовательности пар чисел i и j (i<j), указывающих, что i-й и j-й пункты соединены дорогой; признак конца этой последовательности – пара нулей.

Ее надо решить при помощи РЕКУРСИИ!!!!!!!
За ранее спасибо)))

Всего сообщений: 7 | Присоединился: ноябрь 2009 | Отправлено: 16 нояб. 2009 20:35 | IP
Dmitry74


Новичок

Есть интересная софтина, которая решает эту задачу. причем граф можно нарисовать прямо руками. http://www.susaninlab.com

Всего сообщений: 1 | Присоединился: февраль 2012 | Отправлено: 24 фев. 2012 15:01 | IP

Отправка ответа:
Имя пользователя   Вы зарегистрировались?
Пароль   Забыли пароль?
Сообщение

Использование HTML запрещено

Использование IkonCode разрешено

Смайлики разрешены

Опции отправки

Добавить подпись?
Получать ответы по e-mail?
Разрешить смайлики в этом сообщении?
Просмотреть сообщение перед отправкой? Да   Нет
 

Переход к теме
<< Назад Вперед >>
Одна страница

Форум работает на скрипте © Ikonboard.com