#база_данных #структуры_данных
Добрый день, есть задача разработать БД таким образом, чтобы можно было определить
расстояние между двумя станциями. Но проблема в том, что все тарифное расстояние РЖД
находится на бумаге так сказать, либо в электронном виде, вот пример(http://lawrussia.ru/2001_legislation_of_russia_documents/russian_laws_1547.htm).
В принципе, я немного имею идею, как сделать алгоритм расчета от станции А до станции
Б, ноя не могу никак придумать, как лучше организовать структуру БД. Есть Страна,
Есть дорога, есть участок, на это участке набор остановочных пунктов, вот как можно
лучше всего сделать это, ведь не буду я для каждого узла делать отдельные таблицы,
может кто понимает в этом, подскажите плиз. Пока идея, все станции запихнуть в одну
таблицу, и сделать ссылки на узлы, узлы на дороги, а дороги на страны, но это как-то
не очень получается.
Я в этом не особо силен, поэтому мог некорректно вопрос составить.
Ответы
Ответ 1
Для ответа на этот вопрос необходимо вспомнить немого теории. Для поиска Вам идеально подходит структура данных - матрица растояний. Фактически, это квадартная матрица, в которой по осях находятся идексы станций, а значения по этому индексу и есть искомое растояние. Это именно та структура к которой нужно стремится при работе в программном коде. Но у неё есть небостатки. Она обладает высокой избыточностью. Фактически вы дублируете растояние из узла А в узел Б и наоборот т.е. Вам это придётся дублировать. Кроме того, добавление новых станций будет требовать изменения структуры БД, для расширения на добавляемые станции. Если посмотреть внимательно - то в этой задаче данные о растояниях будут сильно "прорежены". Т.к. почти у всех станций растояний м.б. только два - к предыдущей и последующей станции. И только у узлов их будет больше. Наиболее подходящим в этом случае будет хранить информацию о растояних отдельно от станций. CREATE TABLE STATION ( STATION_ID INT PRIMARY KEY ); CREATE TABLE STATION_DISTANCE ( STATION1_ID INT, STATION2_ID INT, DISTANCE NUMERIC NOT NULL, PRIMARY KEY (STATION1_ID, DISTANCE, STATION2_ID), FOREIGN KEY (STATION1_ID) REFERENCES STATION (STATION_ID), FOREIGN KEY (STATION2_ID) REFERENCES STATION (STATION_ID) ); Такая структура БД предоставит достаточно удобное хранение записи о растоянии, но совершить поиск оптимального пути на уровне базы данных при указанных условиях, не предоставляется возможным. Поиск в этом случае можно будет совершить двумя способами: Способ с предварительной подготовкой и подниманием всей информации о путях из БД. Способ требующий уточняющих запросов. Первый - потребует подготовки которая заключается в постороении из этой таблицы матрицы растояний к примеру при помощи алгоритма Флойда - Уоршелла. И хотя этот алгоритм достаточно тяжёлый его результат, можно сохранить сериализовав матрицу растояний в файл и далее работать с ним, при этом его модификацию потребуется выполнять только при изменении структуры ЖД, что не так и часто. При таком подходе можно быстро находить нужное растояние по матрице растояний. Второй - базируется на алгоритме Дейкстры для разреженных графов. У Вас есть возможность оптимизировать решение отталкиваясь от информации является ли станция узловой, и относится ли она к одной и той-же линии. При этом критерием сложности я бы назвал количество обращений к базе данных. Надеюсь здесь, в нескольких строках, мне удалось немного приблизить Вас к нужному варианту ответа по этой достаточно сложной задаче.Ответ 2
Возможно, я не совсем правильно понял задачу, но по идее, должна быть БД примерно такого вида: В таблице "Дистанция" - расстояние между 2-мя соседними узлами. В таблице "дороги" будет информации о движении по узлам. Так как от станции А до станции Б можно проложить путь несколькими способами, выходит, что дорога должна включать все узлы, даже те, где нет остановки. Там, где нет остановки, поле "код_станции" будет пустым. Примерно такая получится заполненная таблица с 2-мя дорогами: Теперь, при выводе дороги можно получить все необходимые данные: Порядок движения. 1. Узлы (не для отображения) 2. Станции (то есть остановки - для отображения) 3. Расстояние (либо вычислять уже при выводе дороги в программу, для каждой строки выполнив запрос к табл. "дистанция", либо добавить в табл. "дороги" поле "код_дистанции" и заполнять его при добавлении данных в таблицу "дороги", если есть такая возможность. Также можно добавить триггеры, чтобы автоматизировать этот процесс). 4. При необходимости дополнительным запросом получить страны (из таблицы "Узлы"). Возможно, подойдет такое решение. Наверное, что-то можно пересмотреть и улучшить, писал быстро. Например, в таблице "дороги" вроде как глупо указывать узел, если указан код_станции, дублирование получается. Можно убрать вообще поле код_узла, оставить только код_станции и добавить флаг "остановка". UPD: обратил внимание, что все-таки неверно понял насчет узла. Если узел - это некий объект для группировки удаленных станций, тогда в схеме нужно "узлы" и "станции" поменять местами. Таблица "дистанция" будет хранить расстояния между станциями. А в таблице дороги убрать поле "узел" и добавить флаг "остановка".Ответ 3
Можно сделать всё связанными иерархическими таблицами: страна содержит список таблиц дорог, дорога - список таблиц узлов и т.п. Но это, на мой взгляд, неудобно. Я бы свёл всё в одну таблицу (возможно, две, если будет нужна доп. информация), где будут и страны, и дороги, и узлы, и станции. Введите идентификатор, однозначно определяющий тип (пример: 1 - страна, 2 - дорога и т.п.), создайте референсы, указывающие на родителя (станция Толмачёвка имеет родителя за номером 81, а это - Измайловский узел и т.п.). Расстояния тоже можно вводить по-разному. Логичнее, на мой взгляд, в километрах от начала узла. Так и рассчитывать расстояния между станциями будет проще. Например, так: CREATE TABLE `new_table` ( `id` INT NOT NULL COMMENT 'уникальный ID', `ob_type` INT NOT NULL COMMENT 'тип объекта: 1 - страна, 2 -узел, 3 -дорога, 4 - станция', `parent_id1` INT NULL COMMENT 'ссылка на первого родителя - номер его ID', `parent_id2` INT NULL COMMENT 'ссылка на второго родителя - номер его ID', `parent_id3` INT NULL COMMENT 'ссылка на третьего родителя - номер его ID', `name` VARCHAR(90) NULL COMMENT 'Имя объекта', `distance` FLOAT NULL COMMENT 'расстояние от начала узла (только для станций)', `description` TEXT(2000) NULL COMMENT 'Описание', PRIMARY KEY (`id`) COMMENT '', UNIQUE INDEX `id_UNIQUE` (`id` ASC) COMMENT 'Комментарий');Ответ 4
Надо отталкиваться от сущностей. Имеются: Станции Граф описывающий как эти станции соединены друг с другом (то есть станция по сути вершина графа) Есть маршрут который идет по этому графу от узла к узлу (от вершины к вершине) - длина маршрута и есть искомая величина. Итого получаются 3 таблицы, 1 и 3 самоочевидны. Есть сложность со 2-й таблицей - как описать граф. Ладно бы граф был в виде дерева, но в реальности все немного сложнее, поскольку это граф с кольцами, что-то типа такого: Я не совсем глубокий специалист в деле DDL/SQL, но я бы реализовал это через отношение один-ко многим - всегда есть 1 вершина, которая соединена с несколькими вершинами. Как то так.
Комментариев нет:
Отправить комментарий