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

Откуда: Тверь
Сообщений: 882
Всем привет!
Необходимо сделать прокладку маршрута по складу.
Есть схема склада, есть ненаправленный граф обхода склада (более 20 тыс вершин)
Необходимо построить кратчайший маршрут между двумя произвольными вершинами склада.

В принципе алгоритм Дейкстры не сложный, но хотелось бы перед началом реализации, послушать мнения.
Наверняка кто-то делал подобное,
подскажите какие подводные камни?
как более эффективно реализовать на sql сервере на лету считать или заранее просчитать пути от каждой точки к каждой и хранить в БД?
Может еще чего полезного посоветуете.
27 май 15, 11:22    [17694991]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Winnipuh
Member [заблокирован]

Откуда: Київ
Сообщений: 10428
1. SQLCLR?
2. OrientDB?
27 май 15, 11:40    [17695116]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
WarAnt
Member

Откуда: Питер
Сообщений: 2421
PG81,

Перемножаете все варианты и выбираете тот который нужно.
27 май 15, 11:52    [17695210]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20519
PG81
более 20 тыс вершин

заранее просчитать пути от каждой точки к каждой и хранить в БД

400 млн. маршрутов? ну-ну...

PG81
как более эффективно реализовать на sql сервере

А почему обязательно на SQL-сервере? задача-то больше подходит для решения на стороне клиента...
27 май 15, 11:54    [17695228]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
PG81
Member

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

Идея такая, что один раз рассчитать расстояния, и потом уже пользоваться только готовым результатом получая его из БД
27 май 15, 12:09    [17695316]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20519
Если схема абсолютно статична - ну, наверное, это возможно. Алгоритмы получения всех путей в графе существуют, не вопрос... но представь, сколько оно молотить будет и сколько места зажрёт 400 кк маршрутов.
27 май 15, 12:27    [17695404]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Кот Матроскин
Member

Откуда: Москва
Сообщений: 8933
PG81,

Т.е. "проверить, нет ли готового расчета для конкретных точек, если есть - то взять его, если нет - то рассчитать и сохранить"?
Да, если стоимость путей считается редко - это, конечно, эффективнее, чем считать каждый раз заново.
27 май 15, 12:30    [17695425]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Кот Матроскин
Member

Откуда: Москва
Сообщений: 8933
*меняется редко
27 май 15, 12:32    [17695445]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Wlr-l
Member

Откуда:
Сообщений: 522
Akina,

Если схема абсолютно статична, то получение всех путей в графе это одноразовая задача, поэтому не важно, сколько оно молотить будет, да и сколько места зажрёт 400 кк маршрутов не столь важно. Зато последующие запросы будут выполняться практически мгновенно.
27 май 15, 12:34    [17695463]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Кот Матроскин
Member

Откуда: Москва
Сообщений: 8933
в принципе эффективность еще зависит от связности графа - чем больше ребер, тем выгоднее хранить предрасчет.
27 май 15, 12:40    [17695498]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20519
PG81, покопавшись по сусекам, нашёл когда-то написанный волновой алгоритм поиска пути для MySQL. Правда, он решает чутка другую задачу - поиск самого дешёвого среди самых коротких.
Могу запостить, если нужен.
27 май 15, 13:54    [17696009]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
PG81
Member

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

Ну запости, я против не буду)) мне любопытно
Я как сделаю первый вариант тоже выложу, на критику
27 май 15, 14:12    [17696097]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20519
Посмотрел - для твоей задачи он даже проще, надо несколько инструкций удалить (сделал) и ничего не добавлять. Вот итог:

CREATE PROCEDURE Wave (IN pFrom INT, IN pTo Int)
BEGIN
DECLARE MaxIterations INT DEFAULT 100;

DROP TEMPORARY TABLE IF EXISTS Routes;
CREATE TEMPORARY TABLE Routes(point INT, weight INT, route TEXT, PRIMARY KEY(point));
DROP TEMPORARY TABLE IF EXISTS Step;
CREATE TEMPORARY TABLE Step(point INT, weight INT, route TEXT);

INSERT INTO Routes(point, weight, route) VALUES (pFrom, 0, CAST(pFrom AS CHAR));

WHILE MaxIterations > 0 DO
  TRUNCATE Step;
  INSERT INTO Step (point, weight, route)
    SELECT Graph.point2, Routes.weight+Graph.weight, CONCAT(Routes.route, '/', CAST(Graph.point2 AS CHAR))
    FROM Routes, Graph
    WHERE Routes.point = Graph.point1;
  INSERT IGNORE INTO Routes (point, weight, route)
    SELECT point, weight, route FROM Step;
  UPDATE Routes, Step
    SET Routes.weight = Step.weight, Routes.route = Step.route
    WHERE Routes.point = Step.point AND Routes.weight > Step.weight;
  SET MaxIterations = MaxIterations - 1;
END WHILE;

SELECT weight, route
  FROM Routes
  WHERE point = pTo;

DROP TEMPORARY TABLE IF EXISTS Routes;
DROP TEMPORARY TABLE IF EXISTS Step;
END; @@

Исходные данные берутся из таблицы
CREATE TABLE Graph (
point1 INT NOT NULL, -- from
point2 INT NOT NULL, -- to
weight INT NOT NULL, -- cost
PRIMARY KEY (point1, point2)
);
27 май 15, 14:12    [17696098]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
хмхмхм
Guest
PG81
Всем привет!
Необходимо сделать прокладку маршрута по складу.
Есть схема склада, есть ненаправленный граф обхода склада (более 20 тыс вершин)
Необходимо построить кратчайший маршрут между двумя произвольными вершинами склада.

В принципе алгоритм Дейкстры не сложный, но хотелось бы перед началом реализации, послушать мнения.
Наверняка кто-то делал подобное,
подскажите какие подводные камни?
как более эффективно реализовать на sql сервере на лету считать или заранее просчитать пути от каждой точки к каждой и хранить в БД?
Может еще чего полезного посоветуете.


Мне кажется:
1. Для счета налету лучше все-таки использовать приложение, т.к. сервер плохо работает с рекурсией. Ну или если очень-очень хочется, то на SQL 2014 использовать dll процедуры. Это как раз для извращений, когда хочется код на Net непременно запустить на SQL.
2. Если результаты статичны или добавляются время от времени новые узлы, то можно использовать хранение статичной информации и иногда её обновлять. Тогда тут простой вариант - таблица, где перечислены через разделитель узлы, начальная точка, конечная точка, вес и кол-во узлов. Из нее запрос будет мгновенным в случае создания индекса по двум узлам с include полями из select-а.
27 май 15, 14:13    [17696104]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 20519
Из MySQL-специфичного тут только INSERT IGNORE - это вставка в таблицу, когда вставляются только записи, не нарушающие условий уникальности, вне зависимости от наличия в наборе записей, нарушающих ограничения (такие записи игнорируются, причём разные игнорируемые записи могут нарушать требования разных индексов).
27 май 15, 14:15    [17696114]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
PG81
Member

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

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

К сообщению приложен файл. Размер - 109Kb
27 май 15, 14:16    [17696125]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
PG81
Member

Откуда: Тверь
Сообщений: 882
придумал, рекурсивную функцию
оказалось уровень вложенности не должен превышать 32(((
Как то нужно от нее теперь избавится блин
27 май 15, 17:36    [17697442]     Ответить | Цитировать Сообщить модератору
 Re: Алгоритм Дейкстры на MS SQL Server  [new]
VRafael
Member

Откуда: Москва
Сообщений: 65
PG81, привет!

Я как-раз в прошлом году работал над такой задачей. Также граф с плечами/маршрутами, расчет пути алгоритмом Дейкстры.
Когда сильно увеличился поток отправлений все уперлось в расчет маршрутов, т.к. для каждого отправления был постоянный перерасчет. Пока пробовали разные варианты оптимизации (которые, если честно, не сильно помогли), я продавил вариант с кэширование. На разработку с тестированием ушло всего несколько дней, т.к. ничего сложного в нем нет. Зато после этого как рукой сняло

Как сделано:
  • Весь кэш сбрасывается при вводе и выводе маршрутов в действие
    Желательно минимизировать частоту таких операций, или группировать их в пакеты.
  • Наполнение кэша по мере необходимости
    Ищем путь для отправления в кэше, если нет - рассчитываем и записывам туда (перед добавлением учтите, что другая тразнакция может делать в этот момент тоже самое!). Этот подход позволяет распределить нагрузку равномерно, в отличие от полного пересчета всех путей после сброса кэша.

    Проверил, на текущий момент
  • 1593 точки
  • 5221 маршрута
  • 6542 плеча
    В принципе немного, но если пересчитывать маршрут десятки (если не сотни) тысяч раз в день, то лишняя нагрузка будет ощутима!
  • 27 май 15, 17:44    [17697483]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    churupaha
    Member

    Откуда: Краснодар
    Сообщений: 1015
    PG81,

    вот тут вам дали годный совет

    Akina
    А почему обязательно на SQL-сервере? задача-то больше подходит для решения на стороне клиента...


    оффтоп может натолкнет на мысли
    если и нтересно для анализа сетей у Oracle сначала было PL/SQL API в рамках Oracle Topology Network, а потом они алгоритмы, связанные с анализом сети вынесли в java class'ы для сервера приложения. и на момент 11 g там было два API PL/SQL и Java. Причем для Java API они сделали специальный партишнинг сети (графа) в базе и куски сети хранят в блобах. Java' итератор когда пробегает по сети подкачивает эти блобы и есть кеширование там и т. п.. также можно зарегистрировать своего "визитора" и обрабатывать OnEdge/OnVertex и т. п..

    тынц
    тынц
    27 май 15, 17:49    [17697504]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    VRafael
    Member

    Откуда: Москва
    Сообщений: 65
    PG81,

    Только сейчас увидел что ты из Твери.. Не из Интернет-Решений случайно?
    27 май 15, 17:50    [17697508]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    VRafael
    Member

    Откуда: Москва
    Сообщений: 65
    PG81,

    На скуле желательно такое пилить на свежем In-Memory OLTP (Hekaton) если версия позволяет (SQL Server 2014 Enterprise).
    27 май 15, 17:54    [17697535]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    Ага
    Guest
    Топикстартеру - удалость решить задачу?
    Встала похожая задача, только усложненная поиском оптимальной с точки зрения расстояния ячейки для размещения и всякими нюансами вроде включения в расчет костов на разворот техники при смене направления движения, стоимости подъема на уровень и повышенной стоимости прохода через определенные зоны склада (перемещение в другой блок склада штрафуется)
    31 авг 15, 07:41    [18089522]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    Ага
    Guest
    Похоже ТС все решил почитает на лаврах :).
    По сабжу:
    Считать маршрут от каждой ячейки к каждой на складе с количеством ячеек более 100 тысяч смысла не имеет, тем более для включения пробега и трудоемкости операций как одного из коэффициентов целевой функции размещения.
    Надо упрощать
    В итоге весь склад разбил на области, включая z координату, определил смежный области, весь пол просчитал алгоритмом распространения волны, включив дополнительную стоимость прохода дефицитных областей (переходы, лифты) и количество разворотов техники в расчет. Алгоритм неидеален, из-за отсечения маршрутов с бОльшей стоимостью на каждому этапе отсекает потенциально более дешевые по разворотам маршруты, но для моих целей вполне достаточен. Оптимальный маршрут из области в область всегда, исключение - перемещение в соседний проход при наличии дорожек сверху и снизу.
    В конечном варианте стоимость перемещения топология ячеек внутри области накладывается на стоимость перемещений между областями и выбирается наилучший вариант.
    31 авг 15, 12:38    [18090479]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    PG81
    Member

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

    Если есть вопросы задавай, чуть позже расскажу как сам сделал.
    6 окт 15, 00:28    [18238954]     Ответить | Цитировать Сообщить модератору
     Re: Алгоритм Дейкстры на MS SQL Server  [new]
    Дейкстра1
    Guest
    На оптимальность не претендую, получилось что-то вроде такого:

    Таблица и заполнение:
    CREATE TABLE [dbo].[links](
    	[link_id] [int] IDENTITY(1,1) NOT NULL,
    	[node1_id] [int] NOT NULL,
    	[node2_id] [int] NOT NULL,
    	[weight] [int] NULL,
    	[id_min]  AS (case when [node1_id]<[node2_id] then [node1_id] else [node2_id] end),
    	[id_max]  AS (case when [node1_id]>[node2_id] then [node1_id] else [node2_id] end),
    	[descr] [nvarchar](max) NULL,
    PRIMARY KEY CLUSTERED 
    (
    	[link_id] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY],
    UNIQUE NONCLUSTERED 
    (
    	[id_min] ASC,
    	[id_max] ASC
    )WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
    ) ON [PRIMARY] TEXTIMAGE_ON [PRIMARY]
    
    
    insert into dbo.links
    		 (node1_id, node2_id, weight, descr)
    SELECT * 
    FROM (
    VALUES 
    (1,6,14,NULL),
    (1,3,9,NULL),
    (1,2,7,NULL),
    (6,5,9,NULL),
    (6,3,2,NULL),
    (3,4,11,NULL),
    (3,2,10,NULL),
    (2,4,15,NULL),
    (4,5,6,NULL)) AS vtable 
    ([node1_id],[node2_id],[weight],[descr])
    


    Поиск:
    declare
       @step_id int = 2
      ,@max_recurtion int = 10
      ,@first_node int = 1
      ,@last_node int = 5
    
    
    declare	@t table (
    	deep int
       ,node1_id int
       ,node2_id int
       ,[root] nvarchar(max)
       ,[weight] int
       ,first_node int
       ,last_node as (case when charindex(',', [root]) > 0
    					   then cast(substring(reverse([root]), 0, charindex(',', [root])) as integer)
    					   else 0
    				  end)
       )
    
    insert	 into @t
    		 (
    		  deep
    		 ,node1_id
    		 ,node2_id
    		 ,[root]
    		 ,[weight]
    		 ,first_node
    		 )
    		 select
    			1
    		   ,node1_id
    		   ,node2_id
    		   ,cast(node1_id as nvarchar(8)) + ',' + cast(node2_id as nvarchar(8))
    		   ,l.[weight]
    		   ,l.node1_id
    		 from
    			links l
    
    
    while @step_id < @max_recurtion 
       begin 
    
    	  insert   into @t
    			   (
    				deep
    			   ,node1_id
    			   ,node2_id
    			   ,[root]
    			   ,[weight]
    			   ,first_node
    			   )
    			   select
    				  @step_id
    				 ,t.node2_id
    				 ,l.node2_id
    				 ,t.[root] + ',' + cast(l.node2_id as nvarchar(8))
    				 ,t.[weight] + l.[weight]
    				 ,t.first_node
    			   from
    				  @t t
    				  inner join links l
    					 on t.node2_id = l.node1_id
    						and l.node2_id <> t.node1_id
    			   where
    				  t.deep = @step_id - 1
    
    	  if @@rowcount = 0 
    		 break;
    
    	  set @step_id = @step_id + 1
       end
    
    select
       *
    from
       @t t
    where t.first_node = @first_node and t.last_node = @last_node
    or t.first_node = @last_node and  t.last_node = @first_node
    
    6 окт 15, 10:59    [18239943]     Ответить | Цитировать Сообщить модератору
    Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
    Все форумы / Microsoft SQL Server Ответить