ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Алгоритм выбора маршрута на городском транспорте
9 сообщений из 9, страница 1 из 1
Алгоритм выбора маршрута на городском транспорте
    #33352000
KRED
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
KRED
Участник
Есть существующая система хранящая маршруты городского транспорта.

В текущей модификации система может найти (достаточно быстро) маршрут-рейс от точки "А" до точки "Д". Но точка "А" и точка "Д" должны находится в маршруте одного транспортного средства.

Но вот когда нужно искать маршрут с пересадкой ... даже не знаю что сделать.!

сейчас реализовано примерно так

"Таблица маршрут" -> "Таблица точки маршрута"
"Таблица точки маршрута" : есть поле указывающее черех сколько минут транспортное средство будет в этой точке. так можно находить подходящее направление .


Но если два разных маршрута имеют в одной и той же точке пересадку (например "С" ).... то тут я незнаю что сделать .

Например :
1 А Б С Е (пересадка в точке С в маршрут 2)
2 Н О С Д (пересадка в точке С в маршрут 1 )
Тоесть можно доехать из А и Б в точку Д !

Может кто поможет ? Как организовать такое что б оно красиво было ... да ещо и быстро искало ?
...
Рейтинг: 0 / 0
31.10.2005, 02:29
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33352065
mir
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mir
Участник
1. Тема должна иметь название по существу вопроса. Названия "Вопрос к профессионалам", "Помогите!", "А вот у меня есть вопрос" и подобные являются бессмысленными и тупыми.
2. Ваша задача упирается не в вопрос "организации", не в вопрос проектирования БД, а строго в алгоритмы. Это задача на графы. Формулируйте ее в терминах графов, потом ищите (например, в Кнуте) подходящие базовые алгоритмы, но свой все равно придумать надо. Тут ведь у вас и задача оптимизации, а критерий оптимальности не сформулирован.

Удачи.
...
Рейтинг: 0 / 0
31.10.2005, 07:41
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33352869
VoDA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VoDA
Участник
В общем стандартная задача на теорию графов.

Проще найти готовый алгоритм, чем организовывать самому. Если ОЧЕНЬ нужно пость вопросы на SAnalis.ru в форуме.

При ЧЕРЕЗВЫЧАЙНОЙ необходимости (а есть ли она? ), могу найти в своих записях решение на С.

ЗЫ 100 лет этим не занимаюсь.
ЗЗЫ задача коммивояжера из той же оперы.

А вообще опиши задачу более четко

2 модераторы: переименуйте топик ну скажем в "задача коммивояжера". Хоть будет более понятно о чем здусь
----

SAnalis.ru - Just for fun. Еще расту, а так я ДЖИП!
...
Рейтинг: 0 / 0
31.10.2005, 13:25
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33352943
it depends
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
it depends
Гость
VoDA задача коммивояжера из той же оперы.
не совсем :)
ИМХО, скорее - из разряда о кратчайших путях

P.S. Гы, а интересно, на что будет похожа реализация на SQL, скажем, алгоритма Дейкстры?
...
Рейтинг: 0 / 0
31.10.2005, 13:46
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33353304
VoDA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VoDA
Участник
Писать лучше сюда http://sanalis.ru/forum/viewtopic.php?p=141#141
----

SAnalis.ru - Just for fun. Еще расту, а так я ДЖИП!
...
Рейтинг: 0 / 0
31.10.2005, 15:20
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33353311
VoDA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
VoDA
Участник
it depends VoDA задача коммивояжера из той же оперы.
не совсем :)
ИМХО, скорее - из разряда о кратчайших путяхСогласен, но ОБЫЧНО когда ищут путь хотят получить кратчайший (или близкий к этому).

it dependsP.S. Гы, а интересно, на что будет похожа реализация на SQL, скажем, алгоритма Дейкстры?

----

SAnalis.ru - Just for fun. Еще расту, а так я ДЖИП!
...
Рейтинг: 0 / 0
31.10.2005, 15:22
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33353898
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
it dependsP.S. Гы, а интересно, на что будет похожа реализация на SQL, скажем, алгоритма Дейкстры?
Я бы предположил, на пользовательскую агрегатную функцию.
...
Рейтинг: 0 / 0
31.10.2005, 18:06
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33353926
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
KREDМожет кто поможет ? Как организовать такое что б оно красиво было ... да ещо и быстро искало ?
Как Вам сказать... для городского транспорта надо сильно постараться, чтобы оно искало не быстро.

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

Эффективные алгоритмы для предрасчета (рассчитать пути "из всех во все") известны, но в масштабах городского транспорта вряд ли понадобятся; скорее всего, хватит и простых решений, типа того же Дейкстры поочередно для каждой стартовой точки (рассчитать путь "из одной во все остальные" для каждой "одной").
...
Рейтинг: 0 / 0
31.10.2005, 18:16
| Ответить | Цитировать | Написать  
Алгоритм выбора маршрута на городском транспорте
    #33353953
ModelR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ModelR
Участник
Коммивояжер ни причем. При ограничении на число пересадок - чистый поиск. Возможно даже чистый SQL :).
С ровно одной пересадкой что-то типа
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Select 
          m1.route_id, m1.pointcode, m1.pos , m2.pos, m2.poincode,
          m3.route_id, m3.pos, m4.pos, m4.poincode
from 
          routepoint m1, routepoint m2, routepoint m3, routepoint m4
where
         m1.route_id=m2.route_id and m1.pos < m2.pos
         and m3.route_id=m4.route_id and m3.pos < m4.pos
         and m1.pointcode = :start
         and m4.pointcode = :end
         and m2.pointcode =  m3.pointcode
...
Рейтинг: 0 / 0
31.10.2005, 18:28
| Ответить | Цитировать | Написать  
9 сообщений из 9, страница 1 из 1
Форумы / Проектирование БД [игнор отключен] [закрыт для гостей] / Алгоритм выбора маршрута на городском транспорте
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]