Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
eugrita
5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 557
1

Хранение маршрутов (путей графа) в БД

20.04.2013, 10:13. Просмотров 2212. Ответов 6
Метки нет (Все метки)

Что-то без поллитры не соображу как хранить маршруты в базе данных. Маршрут -динамическая структура,
имеет переменное число промежуточных пунктов.
Можно конечно закодировать все пункты и представить маршрут как последовательность кодов пунктов
Вижу 2 альтернативы
1)Хранение маршрута каждый узел в своем поле БД
Недостатки - число полей БД фиксировано и можно лишь зарезервировать, например 30 или 50. Длину маршрута хранить в 1 поле. SQL запросы будут страшно длинными, неудобно, нужно каждый раз формировать в программном цикле.
Достоинства. Каждое поле-узел табл.reis можно связать каскадной связью с табл. узлов Node - т.е автоматич поддержка ссылочной целостности.

2)Хранение маршрута в строковом (или веществ)поле.
резервируется мах число узлов например N=100 Каждый узел кодируется тогда 2 символами
Недостатки - сложность раскодирования. Писать программу разбивающая строку на пары соседн символов и преобразующие их в NN узлов. Никакой поддержки ссылочной целостности.
Если тип поля вещественный - доп.проблема БД обрезает ведущие нули скажем цепочка узлов 0 -2 -10
представленная как 000110 обрежется в БД до 110
Единственное достоинство - удобное хранение в длинном текстовом поле (длина 200 и выше)

Добавлено через 38 минут
Отдельной проблемой является хранение сопутствующих маршруту данных. Например расписания и стоимости проезда Их уже так не закодируешь как в 1 случае. Если скажем стоимость проезда между 2 пунктами аддитивно зависит от стоимости проезда по каждому ребру, то можно скажем хранить атрибуты стоимости и
время движения в табл ребер . Но в жизни это не всегда так. Кроме того можно учитывать особенности расписания - например некоторые пункты проезжают без остановки, тогда сумм время будет меньше суммы времен
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2013, 10:13
Ответы с готовыми решениями:

Поиск всех маршрутов
Добрый день. Нужна теоретическая помощь по следующей задаче. Дано квадратное...

Алгоритм нахождения маршрутов общественного транспорта
Идея следующая: есть город, у города есть дороги, на которых стоят остановки. В...

Волновой алгоритм для нескольких маршрутов
Задача самая рядовая: допустим, есть стратегическая игра, нужно организовать...

Переход от идеальных маршрутов к реальным при реализации алгоритма Дейкстры
Здравствуйте , есть программа для транспортной компаний где маршрут будет...

хранение путей.
Вопрос такой нужно хранить пути к файлом, прикрепленные к одной записи. Далее...

6
canopen
420 / 421 / 93
Регистрация: 16.07.2012
Сообщений: 886
20.04.2013, 13:53 2
Как насчет таблицы
"Идентификатор маршрута" "Порядковый номер пункта в маршруте" "Идентификатор очередного пункта"?

Или такой
"Идентификатор маршрута" "Порядковый номер отрезка" "Идентификатор начального пункта отрезка" "Идентификатор конечного пункта отрезка"?
0
eugrita
5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 557
27.04.2013, 10:00  [ТС] 3
Да, именно такая структура табл удобна
Id_route -идентификатор маршрута
Nach - идентификатор узла начального пункта текущей ветви
Fin - идентификатор узла конечного пункта текущей ветви
При этом после SQL запроса выборки всех записей по данному маршруту, необходимо восстановить список
т.е найти Nach без входящих узлов и Fin без исходящих узлов и т.д. Правда такое не годится для кольцевых маршрутов, так как непонятно где будет начальная (она же и конечная)остановка
-------------------------------------------------------------
А дальше можно составить подчиненную к табл маршрутов табл расписаний с ключами
Id_route
Tstart - время выезда
0
canopen
420 / 421 / 93
Регистрация: 16.07.2012
Сообщений: 886
27.04.2013, 10:56 4
Ага, только обратите внимание - я не зря указал дополнительное поле для порядкового номера отрезка - в общем случае порядок в котором СУБД будет возвращать отрезки для заданного маршрута не определен (может быть любым).
0
iifat
2378 / 1530 / 135
Регистрация: 05.06.2011
Сообщений: 4,262
27.04.2013, 14:34 5
Цитата Сообщение от eugrita Посмотреть сообщение
При этом после SQL запроса выборки всех записей по данному маршруту, необходимо восстановить список т.е найти Nach без входящих узлов и Fin без исходящих узлов и т.д. Правда такое не годится для кольцевых маршрутов, так как непонятно где будет начальная (она же и конечная)остановка
Это-то как раз не проблема: начало/конец можно и отдельными полями хранить.
В общем, имхо, в любом варианте будь готов много дописывать. Задача достаточно сложная, и в SQL красиво не укладывается.
0
korvin_
2307 / 1806 / 337
Регистрация: 28.04.2012
Сообщений: 6,289
27.04.2013, 15:16 6
А почему бы в таком случае не посмотреть на NoSQL базы данных? В частности на хранилища графов.
0
eugrita
5 / 6 / 4
Регистрация: 18.11.2009
Сообщений: 557
12.05.2013, 00:17  [ТС] 7
Вот в результате раздумий остановился на схеме

Какая-то ссылочная целостность (неполная)поддерживается. Так нельзя вставить
в маршрут не вершину графа. Но контроль на существование ребра возложен не на СУБД а на программиста.т.е. ребро между соседними остановками это поля Routes.N между каждыми соседними Routes.nost (nost - порядковы1 N остановки от начала маршрута)
Достоинства- минимум полей
0
12.05.2013, 00:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.05.2013, 00:17

Хранение нескольких путей к файлам
Добрый вечер, интересует есть ли на ВФ клас который позволят взять адрес файла....

Как организовать хранение списка путей?
Задача заключается в том чтобы по нажатию кнопки сделать бэкап родных файлов, и...

Нахождение всех путей ориетированного графа
Есть вектор с ребрами vector< vector<int> > g; Как найти все пути методом...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru