Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Алгоритм поиска кратчайшего питу на SQL  [new]
PG81
Member

Откуда: Тверь
Сообщений: 882
Всем привет!
имеется огромный граф (более 200 тыс вершин и ребер стока же)
находится в БД
реализовывал ли кто-нибудь алгоритмы поиска кратчайшего пути на SQL
Какой алгоритм выбрали? С какими сложностями столкнулись?
Щас сам сижу изучаю материал в тырнетах, интересно что люди скажут.
30 апр 15, 11:05    [17585720]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
iap
Member

Откуда: Москва
Сообщений: 47049
PG81
более 200 тыс вершин и ребер стока же
C циклами значит?
30 апр 15, 11:07    [17585741]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
PG81
Member

Откуда: Тверь
Сообщений: 882
iap,

да с циклами, не направленный
30 апр 15, 11:13    [17585799]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
Сруль.
Member

Откуда:
Сообщений: 121
У каждой задачки, свой цимес.
Если с правильного хвоста начать, то доберёшься.
Чем больше времени тратишь до кода,
тем код легче.
Я бы начал с рекурсий.
От каждой вершины отходит дерево маршрутов.
Если научится при построении этого дерева, отбрасывать петли, т.е. те вершины, в которых ветка, уже отметилась,
то дерево получится простым.
Те ветки что приводят из пункта А в пункт Б, больше не разрабатывать и замерять.
Потом сравнить замеренные ветки.

В рекурсии, главное, это то условие, что стоит перед запуском
функции с новыми паратметрами, и отвчает на вопрос, а не пора ли
всё это закончить ?
Вот с него, я бы посоветовал начать.
Проверить его, до кишок, тогда не будет зацикливаний, а с остальным можно справиться.
3 май 15, 12:19    [17595515]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
Сруль.
Member

Откуда:
Сообщений: 121
Извините, за назойливость, но если вы нашли 1 маршрут, то все ветки, длиннее онного, можно, уже, не копать.
Оптимизация, типа.
3 май 15, 12:30    [17595526]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20960
Микроскопом можно забивать гвозди. Но надо ли?
SQL-сервер - не тот инструмент, который эффективно решает ТАКИЕ задачи.
3 май 15, 22:26    [17596725]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20960
Ну то есть можно, конечно, реализовать, например, волновой алгоритм с использованием CTE. Но вынос данных на клиента и применение там эффективных алгоритмов посика, думаю, намного разумнее и эффективнее.
3 май 15, 22:27    [17596734]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм поиска кратчайшего питу на SQL  [new]
Сруль.
Member

Откуда:
Сообщений: 121
Как говаривал один мой знакомый:
"В жизни бывает всё".
Как задачу поставят, так и спляшешь,
здравый смысл понятие расстяжимое.
5 май 15, 11:17    [17601005]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить