Гость
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Рекурсивное соединение произвольного числа записей / 9 сообщений из 9, страница 1 из 1
03.02.2022, 11:52
    #40131440
Alibek B
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Есть список Узлов: nodes (node_id, name, gps).
Если список Линий: links (node1, node2, name).
Линия соединяет между собой два узла.

Есть понятие Маршрут — это последовательность (цепочка) из нескольких линий, где конечный Узел одной Линии является начальным Узлом другой Линии. Колец нет, то есть Маршрут это всегда незамкнутая цепочка. Длина цепочки (количество промежуточных узлов) может быть произвольной, их может быть несколько десятков.
Данные хранятся в СУБД MySQL, точнее в MariaDB 10.
Можно ли с помощью запроса построить все Маршруты?
В ряде случаев цепочка может разветвляться, в этом случае Маршрут должен строится по самой длинной цепочке.

Не поможете с примером подобного запроса?
...
Рейтинг: 0 / 0
03.02.2022, 12:58
    #40131457
paver
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Alibek B.

Можно ли с помощью запроса построить все Маршруты?

Задача довольно мутно сформулирована, но по-любому ответ - нет.
Странная идея - решать задачу коммивояжера с помощью SQL
...
Рейтинг: 0 / 0
03.02.2022, 13:11
    #40131464
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Alibek B.
Можно ли с помощью запроса построить все Маршруты?

Можно. А зачем?

Не, я бы ещё понял "От А до Б через В". А вот так абстрактно...

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

Alibek B.
точнее в MariaDB 10.

С точностью у тебя как-то нелады. 10,1 и 10,6 - это ну нас только две большие разницы...
...
Рейтинг: 0 / 0
03.02.2022, 13:32
    #40131472
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Вот пример. 8 узлов, 13 рёбер... и 101 маршрут.

https://dbfiddle.uk/?rdbms=mariadb_10.3&fiddle=19180acdcfac0f42e090d76ed142b991
...
Рейтинг: 0 / 0
03.02.2022, 16:38
    #40131512
Alibek B
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
MariaDB 10.0.38.

Количество Узлов - порядка тысячи.
Количество Линий - порядка тысячи.
Количество трасс будет меньше, порядка сотни. Трассы не замкнуты.
Выглядеть будет скорее так. Красным нарисована самая длинная трасса.
...
Рейтинг: 0 / 0
03.02.2022, 19:34
    #40131544
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Тысяча рёбер - это уже минимум тысяча маршрутов.
...
Рейтинг: 0 / 0
03.02.2022, 23:09
    #40131578
Alibek B
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Поскольку разветвлений не так много, а существенная часть ребер является связной цепочкой и сводится к одному маршруту, то в моем случае маршрутов значительно меньше, чем ребер. Особенно если пропускать те ребра, которые уже считаются частью других маршрутов.
...
Рейтинг: 0 / 0
03.02.2022, 23:18
    #40131579
Alibek B
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Я не подписал свой рисунок.
Но допустим, точки на красной линии можно обозначить как 1, 2, 3, 4 (снизу вверх). Соответственно, красная линия это 1234.
Отвод фиолетовой линии будет 5, соответственно фиолетовая линия будет 25.
Отвод зеленой линии будет 6, соответственно зеленая линия будет 36.

Возможны другие варианты.
Например 125, 634, 23. Или 5236, 21, 34.
Но в первом случае варианты короче (максимум два сегмента, а 1234 это три сегмента).
А во втором случае 5236 равен по длине 1234 и тоже является приемлемым решением.
При равной длине выбирается маршрут с меньшим значением node1.

Правда я уже понял, что в рамках SQL эту задачу не решить.
Потому что в моем случае соединений значительно больше и они более сложные.
И какой-нибудь один выбранный маршрут может заблокировать несколько других длинных маршрутов, у которых имеются общие узлы.
То есть маршруты нужно выбирать в комплексе с их взаимодействием на другие маршруты.
...
Рейтинг: 0 / 0
04.02.2022, 11:41
    #40131647
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивное соединение произвольного числа записей
Alibek B. , ты что-то не так понимаешь... речь идёт не об окончательных, самых длинных, маршрутах, а вообще о всех возможных, начиная с маршрутов длины 1. Их надо построить абсолютно все - и только потом выбирать самые длинные.
На SQL задача решаема - я показал как. Но при тысяче узлов количество всех маршрутов, из которых надо выбирать самые длинные, получится просто астрономическим.
...
Рейтинг: 0 / 0
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Рекурсивное соединение произвольного числа записей / 9 сообщений из 9, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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