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

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

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

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

Поиск всех маршрутов из одной точки в другую. Нужен алгоритм
Даны все маршруты общественного транспорта города. В качестве узлов графа определены все остановки. Необходимо вывести такие маршруты, которые связывают точки i и j.
С прямыми маршрутами дело обстоит просто.
Но также необходимо вывести все маршруты с пересадками (1 и 2).
Ничего путного ни найти, ни придумать не могу.
Простой пребор тут-дело неблагодарное,ибо работать будит черт-знает-сколько.

Заранее благодарю за помощь.
  #2  
Старый 15.11.2010, 12:17
гость

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

Маршрутов может быть экспоненциально много. Вы точно уверены что вам нужны все? Или только кратчайший?

Цитата:
Но также необходимо вывести все маршруты с пересадками (1 и 2).
А разве обычный алгоритм нахождения путей вам сразу не выдаст кратчайший маршрут с учетом всех пересадок? Как вы строите свой граф?
  #3  
Старый 15.11.2010, 12:20
Новичок

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

Нет, мне не нужен кратчайший путь. Если бы он был нужен, проблемы бы не было.
Думаю, чтобы правильно построить граф для задачи, мне необходимо иметь идею ее решения.
  #4  
Старый 15.11.2010, 12:29
гость

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

Но тогда
Цитата:
Но также необходимо вывести все маршруты с пересадками (1 и 2).
и
Цитата:
Простой пребор тут-дело неблагодарное,ибо работать будит черт-знает-сколько.
-совершенно противоречивые цели. С одной стороны вы хотите все маршруты, с другой стороны вы говорите что т.к. всех маршрутов может быть очень много, вам это вычисление не по карману.
  #5  
Старый 15.11.2010, 12:32
гость

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

Сообщение от гость Посмотреть сообщение
Но тогда

и

-совершенно противоречивые цели. С одной стороны вы хотите все маршруты, с другой стороны вы говорите что т.к. всех маршрутов может быть очень много, вам это вычисление не по карману.
Приведите примерные размеры вашего графа. Число остановок, маршрутов, средняя длина маршрута? Каким бюджетом времени вы располагаете на каждый запрос (т.е. это онлайн - за считанные секунды, или оффлайн)?
  #6  
Старый 15.11.2010, 14:27
Новичок

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

число остановок-около 1000. маршрутов - 140.
все происходт онлайн.
  #7  
Старый 15.11.2010, 15:06
гость

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

Сообщение от straus_kris_28 Посмотреть сообщение
число остановок-около 1000. маршрутов - 140.
все происходт онлайн.
Начальная и конечная остановки так полагаю заданы. 2 пересадки - это две промежуточные остановки перебрать, всего 1000^2 вариантов. Циклом их перебирайте и все. За 0.1 секунды на современных процессорах вполне уложится.
  #8  
Старый 15.11.2010, 15:08
гость

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

Предварительно, только. естественно надо бы вычислить матрицу можно ли из i в j проехать на одном транспортном средстве без пересадки, и за сколько
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Мне нужен поиск кратчайшего пути или нет? Bonus Графы 7 27.10.2010 22:31
Проецирование точки с одной плоскости на другую zaidite Вычислительная геометрия 19 06.08.2009 22:36
Поиск всех путей в графе Eldar Графы 6 21.05.2009 09:53
поиск всех возможных путей из одной вершины, до другой Xavier Teodonius Графы 5 03.05.2009 16:01
Нужен поиск с морфологией jay Работа 0 24.01.2008 11:20