| Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
| Все форумы / Microsoft SQL Server |
  |
||
 Алгоритм поиска кратчайшего питу на SQL
|
|
|
PG81 Member Откуда: Тверь Сообщений: 882 |
Всем привет! имеется огромный граф (более 200 тыс вершин и ребер стока же) находится в БД реализовывал ли кто-нибудь алгоритмы поиска кратчайшего пути на SQL Какой алгоритм выбрали? С какими сложностями столкнулись? Щас сам сижу изучаю материал в тырнетах, интересно что люди скажут. |
| 30 апр 15, 11:05 [17585720] Ответить | Цитировать Сообщить модератору | |
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|||
|
iap Member Откуда: Москва Сообщений: 47049 |
|
||
| 30 апр 15, 11:07 [17585741] Ответить | Цитировать Сообщить модератору | |||
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|
|
PG81 Member Откуда: Тверь Сообщений: 882 |
iap, да с циклами, не направленный |
| 30 апр 15, 11:13 [17585799] Ответить | Цитировать Сообщить модератору | |
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|
|
Сруль. Member Откуда: Сообщений: 121 |
У каждой задачки, свой цимес. Если с правильного хвоста начать, то доберёшься. Чем больше времени тратишь до кода, тем код легче. Я бы начал с рекурсий. От каждой вершины отходит дерево маршрутов. Если научится при построении этого дерева, отбрасывать петли, т.е. те вершины, в которых ветка, уже отметилась, то дерево получится простым. Те ветки что приводят из пункта А в пункт Б, больше не разрабатывать и замерять. Потом сравнить замеренные ветки. В рекурсии, главное, это то условие, что стоит перед запуском функции с новыми паратметрами, и отвчает на вопрос, а не пора ли всё это закончить ? Вот с него, я бы посоветовал начать. Проверить его, до кишок, тогда не будет зацикливаний, а с остальным можно справиться. |
| 3 май 15, 12:19 [17595515] Ответить | Цитировать Сообщить модератору | |
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|
|
Сруль. Member Откуда: Сообщений: 121 |
Извините, за назойливость, но если вы нашли 1 маршрут, то все ветки, длиннее онного, можно, уже, не копать. Оптимизация, типа. |
| 3 май 15, 12:30 [17595526] Ответить | Цитировать Сообщить модератору | |
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|
|
Akina Member Откуда: Зеленоград, Москва, Россия Сообщений: 20960 |
Микроскопом можно забивать гвозди. Но надо ли? SQL-сервер - не тот инструмент, который эффективно решает ТАКИЕ задачи. |
| 3 май 15, 22:26 [17596725] Ответить | Цитировать Сообщить модератору | |
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|
|
Akina Member Откуда: Зеленоград, Москва, Россия Сообщений: 20960 |
Ну то есть можно, конечно, реализовать, например, волновой алгоритм с использованием CTE. Но вынос данных на клиента и применение там эффективных алгоритмов посика, думаю, намного разумнее и эффективнее. |
| 3 май 15, 22:27 [17596734] Ответить | Цитировать Сообщить модератору | |
| Re: Алгоритм поиска кратчайшего питу на SQL
|
|
|
Сруль. Member Откуда: Сообщений: 121 |
Как говаривал один мой знакомый: "В жизни бывает всё". Как задачу поставят, так и спляшешь, здравый смысл понятие расстяжимое. |
| 5 май 15, 11:17 [17601005] Ответить | Цитировать Сообщить модератору | |
| Все форумы / Microsoft SQL Server | |
|
x