| ||||||||
| ||||||||
|
|
|||||||||||||||||
05.10.2011, 21:21
|
|
||||
|
Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
|
Задача коммивояжера
Не получается придумать алгоритм для решения задачи коммивояжера.
Если кратко, то есть N городов, путь в каждый из низ из какого-либо города занимает определенную стоимость пути. Необходимо выйти из первого города и вернутся в первый, обойдя по одному разу все города. Необходимо найти самую меньшую стоимость пути (общую).
__________________
Humanity.push(new Man()); |
|
05.10.2011, 21:28
|
|
||||
 |
Википедия знает. Такое умное название знаешь, а найти алгоритмы решения не можешь.
__________________
if (love is true) break my.heart; |
|
05.10.2011, 21:30
|
|
||||
 Регистрация: Mar 2010
Адрес: 54.713862552265084 = 20.442724227905273
Сообщений: 449
|
Если я правильно понял, при каждом запросе на обход, путь должен быть рандомный вне зависимости от пункта "х" место запроса?
__________________
Спросишь, дурак на минуту. Если не спросишь, дурак на всю жизнь! |
|
05.10.2011, 21:42
|
|
||||
|
Регистрация: Aug 2011
Сообщений: 53
|
графы?
|
|
05.10.2011, 21:48
|
|
||||
 блогер
Регистрация: Oct 2005
Адрес: Днепродзержинск - город Брежнева и других логопедов
Сообщений: 1,421
Записей в блоге: 4
|
А теорему Ферма (большую) вам не доказать? =)
__________________
Бобры отвечают на вопросы не потому, что знают на них ответы; они отвечают потому, что их спрашивают. |
|
05.10.2011, 22:03
|
|
||||
|
Регистрация: Jul 2008
Сообщений: 80
|
Графы) на втором курсе такая задача была в расчетке.. сейчас сходу не помню решение, а тогда на листике за вечерок под пивко сделал
 ничего сложного если знать алгоритм |
|
06.10.2011, 05:01
|
|
||||
|
Регистрация: Sep 2010
Адрес: Красноярск
Сообщений: 217
|
Я не умею работать с графами) В википедии нет явного решения, там только способы решений.
__________________
Humanity.push(new Man()); |
|
06.10.2011, 11:03
|
|
||||
 |
Что-то мне подсказывает что можно использовать А* , но только с середины т.к. стоимости уже сть
__________________
Gamedev != Gaming (http://twitter.com/#!/GenzoDev). Don't forget to [+] if it works. |
 |
 |
Часовой пояс GMT +4, время: 05:30. |
|
|
« Предыдущая тема | Следующая тема » |
|
|
Линейный вид
