Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 16.11.2010, 22:37
Новичок

Отправить личное сообщение для cat_baxter Посмотреть профиль Найти все сообщения от cat_baxter
 
Регистрация: 16.11.2010
Сообщений: 6

Поиск самого дешевого маршрута через все города.
Уважаемые профы, есть такая задачка:

Есть оринтированный граф, который представляет собой сеть автобанов между N городами. Стоимость налога за проезд по автобану от города A до города B отличается от стоимости налога проезда из города B в город A.
Если водитель оплатил проезд от A до B, то он может использовать его дальше бесплатно. Задача - проложить минимальный по стоимости циклический путь через все города, т.е. начинающийся и заканчивающийся в одном и том же городе. Проезжать по одним и тем же автобанам (повторный проезд уже бесплатный) и городам разрешен.

Подскажите пожалуйста, куда копать

Заранее спасибо!
  #2  
Старый 16.11.2010, 22:55
гость

 
Сообщений: n/a

Задача коммивояжера. NP-сложно.

"повторный проезд уже бесплатный" ничё не меняет. Разве что, ты можешь прогнать Форда-Воршалла, и получить эквивалентный полный граф, в котором веса будут удовлетворять неравенству треугольника (это называетя Euclidian TSP), и соответственно не будет смысла дважды проезжать по одной дороге
  #3  
Старый 17.11.2010, 00:29
Новичок

Отправить личное сообщение для cat_baxter Посмотреть профиль Найти все сообщения от cat_baxter
 
Регистрация: 16.11.2010
Сообщений: 6

Сообщение от гость Посмотреть сообщение
Задача коммивояжера. NP-сложно.
Спасибо за совет. В задаче коммивояжера каждый город можно посетить только один раз, верно? Тут немного другая ситуация, в задаче повторный путь не добавляет стоимости, и каждый город можно посетить несколько раз - для примера. A->B->C->B->A
  #4  
Старый 17.11.2010, 00:39
гость

 
Сообщений: n/a

ок, понятно. да, не TSP получается, ошибся.

получается, вы ищите минимальный по стоимости сильно-связный *подграф* вашего орграфа, так? Т.е. в неориентированном случае это было бы остовное дерево, а тут сложность в том, что ребра ориентированны?
  #5  
Старый 17.11.2010, 00:40
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
минимальный по стоимости сильно-связный *подграф* вашего орграфа
и который покрывает все вершины, разумеется
  #6  
Старый 17.11.2010, 00:42
гость

 
Сообщений: n/a

Всё равно NP-сложная задача - http://books.google.com/books?id=nvcK1HSXmOMC&pg=PA331
  #7  
Старый 17.11.2010, 00:59
Новичок

Отправить личное сообщение для cat_baxter Посмотреть профиль Найти все сообщения от cat_baxter
 
Регистрация: 16.11.2010
Сообщений: 6

Спасибо огромное, пойду читать
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Задача g6_1011: Города armansuleimenov Задачи 2 10.11.2010 20:06
Решение задачи о назначениях и формирование маршрута (Vehicle Routing Problem) enegul Графы 1 26.06.2010 08:19
Города Bit Takeshi Задачи 0 28.11.2009 11:34
Поиск самого длинного пути в ориентированном графе terlan Графы 11 26.11.2009 01:27
Поиск минимального цикла через алгоритм Форда-Фалкерсона Amber66 Графы 6 20.06.2008 17:48