Algorithme de placement optimal d’une ressource, compte tenu de la distance et de la population cible (Dijkstra)

1 réponse

La recherche d’un placement optimal sur un graphe composé de nÅ“uds et d’arcs est similaire à un calcul de plus court chemin mais doit prendre en considération des poids supplémentaires, ici, la population de chaque nÅ“ud. L’ensemble est réalisé par des procédures Transact SQL dans une base dédiée à ce type de calcul pour MS SQL Server (toutes versions depuis 2000).

Cette méthode est basée sur les procédures de plus court chemin écrites par l’utilisateur SwePeso sur sqlteam.com et utilise l’algorithme de Dijkstra.
Cette solution originale a été proposée par Evan Barke dans le forum consacré à MS SQL Server :
http://www.developpez.net/forums/d1346509/

CRÉATION DE LA BASE DE DONNÉES

/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* CRÉATION DE LA BASE DE DONNÉES                                              *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
CREATE DATABASE DB_DIJKSTRA
GO

ALTER DATABASE DB_DIJKSTRA SET RECOVERY SIMPLE;
GO

DECLARE @SQL NVARCHAR(max);
SELECT @SQL = COALESCE(@SQL, '') +
       CASE "type"
          WHEN 0 THEN'ALTER DATABASE DB_DIJKSTRA MODIFY FILE (NAME = ''' + name +''', SIZE = 250 MB);'
          WHEN 1 THEN'ALTER DATABASE DB_DIJKSTRA MODIFY FILE (NAME = ''' + name +''', SIZE =  50 MB);'
       END  
FROM   sys.master_files
WHERE  name = 'DB_DIJKSTRA';
EXEC (@SQL);

USE DB_DIJKSTRA
GO

CRÉATION DES TABLES DE TRAVAIL :

/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* CRÉATION DES TABLES DE TRAVAIL                                              *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
CREATE TABLE Nodes (
       NodeID      BIGINT IDENTITY (1, 1) NOT NULL PRIMARY KEY,
       NodeName    NVARCHAR(64)           NOT NULL ,
       Cost        FLOAT,
       PathID      BIGINT,
       Calculated  BIT                    NOT NULL DEFAULT 0,
       Population  FLOAT,
       Score       FLOAT
)
GO

CREATE TABLE Paths (
       PathID      BIGINT IDENTITY (1, 1) NOT NULL PRIMARY KEY,
       FromNodeID  BIGINT                 NOT NULL
                   FOREIGN KEY REFERENCES Nodes (NodeID),
       ToNodeID    BIGINT                 NOT NULL
                   FOREIGN KEY REFERENCES Nodes (NodeID),
       Cost        FLOAT                  NOT NULL
);
GO

CREATE TABLE PathsMatrix (
       MatPathID   BIGINT IDENTITY (1, 1) NOT NULL PRIMARY KEY,
       FromNodeID  BIGINT NOT NULL ,
       ToNodeID    BIGINT NOT NULL ,
       Cost        FLOAT  NULL
);
GO

PROCÉDURE DE VIDAGE ET REMISE À ZÉRO AUTO INCRÉMENT :

CREATE PROCEDURE uspDijkstraInitializeMap

AS
/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* PROCÉDURE DE VIDAGE ET REMISE À ZÉRO AUTO INCRÉMENT                         *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
SET NOCOUNT ON;

DELETE FROM Paths;

DBCC CHECKIDENT (Paths, RESEED, 0);

DELETE FROM Nodes;

DBCC CHECKIDENT (Nodes, RESEED, 0);

GO

PROCÉDURE D’AJOUT D’UN CHEMIN :

CREATE PROCEDURE uspDijkstraAddPath
                 @FromNodeName NVARCHAR(64),
                 @ToNodeName   NVARCHAR(64),
                 @Cost         FLOAT
AS
/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* PROCÉDURE D'AJOUT D'UN CHEMIN                                               *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
SET NOCOUNT ON;

DECLARE @FromNodeID BIGINT,
        @ToNodeID   BIGINT,
        @PathID     BIGINT;

SELECT @FromNodeID = NodeID
FROM   Nodes
WHERE  NodeName = @FromNodeName;
 
IF @FromNodeID IS NULL
BEGIN

   INSERT  Nodes (NodeName,      Calculated)
   VALUES        (@FromNodeName, 0);
   
   SELECT @FromNodeID = SCOPE_IDENTITY();
   
END;
 
SELECT @ToNodeID = NodeID
FROM   Nodes
WHERE  NodeName = @ToNodeName;

IF @ToNodeID IS NULL
BEGIN

   INSERT Nodes (NodeName,    Calculated)
   VALUES       (@ToNodeName, 0);
   
   SELECT @ToNodeID = SCOPE_IDENTITY();
   
END
 
SELECT @PathID = PathID
FROM   Paths
WHERE  FromNodeID = @FromNodeID
  AND  ToNodeID = @ToNodeID;
 
IF @PathID IS NULL

   INSERT Paths (FromNodeID, ToNodeID, Cost)
   VALUES (@FromNodeID, @ToNodeID, @Cost);
   
ELSE

   UPDATE Paths
   SET    Cost = @Cost
   WHERE  FromNodeID = @FromNodeID
     AND  ToNodeID = @ToNodeID;
GO

PROCÉDURE DE RÉINITIALISATION DU CALCUL DE COUT :

CREATE PROCEDURE dbo.uspDijkstraClearMap
AS
/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* PROCÉDURE DE RÉINITIALISATION DU CALCUL DE COUT                             *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
SET NOCOUNT ON;
 
UPDATE Nodes
SET    PathID = NULL,
       Cost = NULL,
       Calculated = 0;
GO

PROCÉDURE DE CALCUL DE MOINDRE COUT ENTRE DEUX NŒUDS :

CREATE PROCEDURE uspDijkstraResolve
                 @FromNodeName NVARCHAR(64),
                 @ToNodeName   NVARCHAR(64)
AS
/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* PROCÉDURE DE CALCUL DE MOINDRE COUT ENTRE DEUX NÅ’UDS                        *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
SET NOCOUNT ON;
 
INSERT INTO PathsMatrix (FromNodeID, ToNodeID)
VALUES                  ((SELECT NodeID
                          FROM   Nodes
                          WHERE  NodeName = @FromNodeName) ,
                         (SELECT NodeID
                          FROM   Nodes
                          WHERE  NodeName = @ToNodeName));
 
DECLARE @MatPathID  BIGINT,
        @FromNodeID BIGINT,
        @ToNodeID   BIGINT,
        @NodeID     BIGINT,
        @Cost       FLOAT,
        @PathID     BIGINT;
       
DECLARE @Map TABLE (RowID        BIGINT IDENTITY(-1, -1),
                    FromNodeName NVARCHAR(64),
                    ToNodeName   NVARCHAR(64),
                    Cost         FLOAT);

SELECT TOP 1 @MatPathID = MatPathID
FROM   PathsMatrix
ORDER  BY MatPathID DESC;
 
EXEC uspDijkstraClearMap;
 
SELECT @FromNodeID = NodeID,
       @NodeID = NodeID
FROM   Nodes
WHERE  NodeName = @FromNodeName;
 
IF @FromNodeID IS NULL
BEGIN
   SELECT @FromNodeName = COALESCE(@FromNodeName, '');
   RAISERROR ('From node name ''%s'' can not be found.', 16, 1, @FromNodeName);
   RETURN;
END
 
SELECT @ToNodeID = NodeID
FROM   Nodes
WHERE  NodeName = @ToNodeName;
 
IF @ToNodeID IS NULL
BEGIN
   SELECT @ToNodeName = COALESCE(@ToNodeName, '');
   RAISERROR ('To node name ''%s'' can not be found.', 16, 1, @ToNodeName);
   RETURN;
END
 
UPDATE Nodes
SET    Cost = 0
WHERE  NodeID = @FromNodeID;
 
WHILE @NodeID IS NOT NULL
BEGIN

   UPDATE ToNodes
   SET    ToNodes.Cost = CASE
                            WHEN ToNodes.Cost IS NULL
                               THEN FromNodes.Cost + Paths.Cost
                            WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost
                               THEN FromNodes.Cost + Paths.Cost
                            ELSE ToNodes.Cost
                         END,
          ToNodes.PathID = Paths.PathID
   FROM         Nodes AS FromNodes
          INNER JOIN Paths
                ON Paths.FromNodeID = FromNodes.NodeID
          INNER JOIN Nodes AS ToNodes
                ON ToNodes.NodeID = Paths.ToNodeID
   WHERE  FromNodes.NodeID = @NodeID
     AND  (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost)
     AND  ToNodes.Calculated = 0;
 
   UPDATE FromNodes
   SET    FromNodes.Calculated = 1
   FROM   Nodes AS FromNodes
   WHERE  FromNodes.NodeID = @NodeID;
 
   SELECT @NodeID = NULL;
 
   SELECT TOP 1 @NodeID = Nodes.NodeID
   FROM   Nodes
   WHERE  Nodes.Calculated = 0
     AND  Nodes.Cost IS NOT NULL
   ORDER  BY Nodes.Cost;
END
 
IF EXISTS (SELECT NULL
           FROM   Nodes
           WHERE  NodeID = @ToNodeID
             AND  Cost IS NULL)
BEGIN
   SELECT FromNodeName, ToNodeName, Cost
   FROM   @Map;
   
   RETURN;
END
 
WHILE @FromNodeID  @ToNodeID
BEGIN
   SELECT @FromNodeName = FromNodes.NodeName,
          @ToNodeName = ToNodes.NodeName,
          @Cost = ToNodes.Cost,
          @PathID = ToNodes.PathID
   FROM   Nodes AS ToNodes
          INNER JOIN Paths
                ON Paths.PathID = ToNodes.PathID
          INNER JOIN Nodes AS FromNodes
                ON FromNodes.NodeID = Paths.FromNodeID
   WHERE  ToNodes.NodeID = @ToNodeID;
 
   INSERT @Map (FromNodeName,  ToNodeName,  Cost)
   VALUES      (@FromNodeName, @ToNodeName, @Cost);
 
   SELECT @ToNodeID = Paths.FromNodeID
   FROM   Paths
   WHERE  Paths.PathID = @PathID;
   
END;

UPDATE PathsMatrix
SET    Cost = (SELECT MAX(Cost) FROM @Map)
WHERE  MatPathID = @MatPathID;
 
GO

PROCÉDURE DE GÉNÉRATION DE LA MATRICE DES CHEMINS :

CREATE PROCEDURE dbo.uspDijkstraCreateMatrix
/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* PROCÉDURE DE GÉNÉRATION DE LA MATRICE DES CHEMINS                           *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
AS
 
SET NOCOUNT ON;
 
IF EXISTS (SELECT 1 FROM PathsMatrix)
   TRUNCATE TABLE  PathsMatrix;
 
DECLARE @FROM NVARCHAR(64),
        @TO   NVARCHAR(64);
 
DECLARE cursorNodes CURSOR  
LOCAL FORWARD_ONLY STATIC READ_ONLY
FOR
   SELECT FromNode.NodeName, ToNode.NodeName
   FROM   Nodes AS FromNode
          CROSS JOIN Nodes AS ToNode
   WHERE  FromNode.NodeName  ToNode.NodeName;
 
OPEN cursorNodes;

FETCH cursorNodes INTO @FROM, @TO;
 
WHILE @@FETCH_STATUS = 0
BEGIN

   EXEC dbo.uspDijkstraResolve
        @FromNodeName = @FROM,
        @ToNodeName = @TO;
 
   FETCH cursorNodes INTO @FROM, @TO
END
 
CLOSE cursorNodes;
DEALLOCATE cursorNodes;

GO

PROCÉDURE DE CALCUL DU PLACEMENT OPTIMAL :

CREATE PROCEDURE dbo.uspDijkstraCalculateOptimal
AS
/******************************************************************************
* ALGORITHME DE DIJKSTRA : recherche d'un placement optimal                   *
*******************************************************************************
* PROCÉDURE DE CALCUL DU PLACEMENT OPTIMAL                                    *
*******************************************************************************
* Solution originale d'Evan Barke :http://www.developpez.net/forums/d1346509/ *
******************************************************************************/
SET NOCOUNT ON;
 
DECLARE @FromNodeID NVARCHAR(64);
 
DECLARE cursorNodes CURSOR
LOCAL FORWARD_ONLY STATIC READ_ONLY
FOR
   SELECT FromNode.NodeID
   FROM Nodes AS FromNode;
 
OPEN cursorNodes;

FETCH cursorNodes INTO @FromNodeID;
 
WHILE @@FETCH_STATUS = 0
BEGIN

   UPDATE Nodes SET Score = (SELECT SUM((N.Population)*P.Cost)
                             FROM   Nodes N
                                    INNER JOIN PathsMatrix P
                                          ON P.FromNodeID = N.NodeID
                             WHERE N.NodeID = @FromNodeID)
   WHERE Nodes.NodeID = @FromNodeID;
 
   FETCH cursorNodes INTO @FromNodeID;
 
END
 
CLOSE cursorNodes;

DEALLOCATE cursorNodes;
 
SELECT NodeName, Score
FROM   Nodes
ORDER  BY Score DESC;
 
GO

EXEMPLE :

Notre ami Evan, vivant dans le sud à décider d’implanter sa cabane entre les vignobles de muscat (Lunel) et la mer (La Grande Motte) afin d’y vendre des peaux de kangourou… Quel sera le meilleur placement entre toutes ces villes compte tenu des distances et de la population ?

Phase 1 : initialisons les tables des nœuds et arcs

EXEC dbo.uspDijkstraInitializeMap;

Phase 2 : création des nœuds et arcs

EXEC dbo.uspDijkstraAddPath 'Mauguio', 'St Aunès', 2;
EXEC dbo.uspDijkstraAddPath 'St Aunès', 'Mauguio', 2;
 
EXEC dbo.uspDijkstraAddPath 'Mauguio', 'Mudaison', 3;
EXEC dbo.uspDijkstraAddPath 'Mudaison', 'Mauguio', 3;
 
EXEC dbo.uspDijkstraAddPath 'Mauguio', 'Candillargues', 6;
EXEC dbo.uspDijkstraAddPath 'Candillargues', 'Mauguio', 6;
 
EXEC dbo.uspDijkstraAddPath 'Mauguio', 'La Grande Motte', 4;
EXEC dbo.uspDijkstraAddPath 'La Grande Motte', 'Mauguio', 4;
 
EXEC dbo.uspDijkstraAddPath 'Mauguio', 'Pérols', 6;
EXEC dbo.uspDijkstraAddPath 'Pérols', 'Mauguio', 6;
 
EXEC dbo.uspDijkstraAddPath 'Candillargues', 'Lansargues', 3;
EXEC dbo.uspDijkstraAddPath 'Lansargues', 'Candillargues', 3;
 
EXEC dbo.uspDijkstraAddPath 'Lansargues', 'St Just', 4;
EXEC dbo.uspDijkstraAddPath 'St Just', 'Lansargues', 4;
 
EXEC dbo.uspDijkstraAddPath 'St Just', 'Lunel', 7;
EXEC dbo.uspDijkstraAddPath 'Lunel', 'St Just', 7;
 
EXEC dbo.uspDijkstraAddPath 'Pérols', 'Lattes', 6;
EXEC dbo.uspDijkstraAddPath 'Lattes', 'Pérols', 6;

Phase 3 : création de la matrice des distances

EXEC dbo.uspDijkstraCreateMatrix;

Phase 4 : pondération par la population

UPDATE Nodes SET Population = 16307 WHERE NodeName = 'Mauguio';
UPDATE Nodes SET Population =  3041 WHERE NodeName = 'St Aunès';
UPDATE Nodes SET Population =  2498 WHERE NodeName = 'Mudaison';
UPDATE Nodes SET Population =  1401 WHERE NodeName = 'Candillargues';
UPDATE Nodes SET Population =  8440 WHERE NodeName = 'La Grande Motte';
UPDATE Nodes SET Population =  8509 WHERE NodeName = 'Pérols';
UPDATE Nodes SET Population =  2744 WHERE NodeName = 'Lansargues';
UPDATE Nodes SET Population =  2851 WHERE NodeName = 'St Just';
UPDATE Nodes SET Population = 25277 WHERE NodeName = 'Lunel';
UPDATE Nodes SET Population = 15927 WHERE NodeName = 'Lattes';

Phase 5 : calcul du placement optimal

EXEC dbo.uspDijkstraCalculateOptimal;

RÉSULTAT :

NodeName          Score
----------------- ---------
Lunel             4524583
Lattes            2532393
Mauguio           1223025
Pérols             944499
La Grande Motte    903080
St Just            350673
St Aunès           276731
Lansargues         271656
Mudaison           247302
Candillargues      121887

Il semble que le vignoble de Lunel soit plus attirant que la mer bleu de la grande Motte !

Le site web sur le SQL et les SGBDR
MVP Microsoft SQL Server



Frédéric Brouard, alias SQLpro, ARCHITECTE DE DONNÉES

Expert  S.G.B.D  relationnelles   et   langage  S.Q.L

Moste  Valuable  Professionnal  Microsoft  SQL Server

Société SQLspot  :  modélisation, conseil, formation,

optimisation,  audit,  tuning,  administration  SGBDR

Enseignant: CNAM PACA, ISEN Toulon, CESI Aix en Prov.

L’ntreprise SQL Spot

Une réflexion au sujet de « Algorithme de placement optimal d’une ressource, compte tenu de la distance et de la population cible (Dijkstra) »

  1. Avatar de hmirahmira

    Cet article est vraiment excellent !
    Merci à vous deux SQL_EVAN (Evan Barke)et SQL_PRO (Frédéric BROUARD). SQL_EVAN d’avoir publié la version initiale de cet article et à SQLPro d’avoir mis au propre et publié le présent article sur son blog.

    J’ai constaté 4 petites erreurs :

    ———————–
    1 : Dans le premier script, je vous propose, sauf erreur de ma part, la modification ci-dessous. En effet, sinon seule la taille du fichier de données est mise à jour (250 MB) et pas celle du fichier de log (50 MB) !

    DECLARE @SQL NVARCHAR(max);
    SELECT @SQL = COALESCE(@SQL,  ») +
    CASE « type »
    WHEN 0 THEN’ALTER DATABASE DB_DIJKSTRA MODIFY FILE (NAME =  »’ + name + »’, SIZE = 250 MB);’
    WHEN 1 THEN’ALTER DATABASE DB_DIJKSTRA MODIFY FILE (NAME =  »’ + name + »’, SIZE = 50 MB);’
    END
    FROM sys.master_files
    — WHERE name = ‘DB_DIJKSTRA'; — hmira 15/08/2014 (ligne mise en commentaire)
    WHERE db_name(database_id) = ‘DB_DIJKSTRA’ — hmira 15/08/2014 (ligne de remplacement)
    EXEC (@SQL);
    ———————–
    2 : Dans la procédure uspDijkstraResolve, il manque le signe (ou opérateur ) je crois que cela est lié à l’éditeur du blog et HTML (?). je vous propos la modification ci-dessous (sinon la procédure ne compile pas ! c’est dommage !) :

    — WHILE @FromNodeID @ToNodeID — hmira 15/08/2014 (ligne mise en commentaire)
    WHILE @FromNodeID @ToNodeID — hmira 15/08/2014 (ligne de remplacement : ajout signe entre @FromNodeID et @ToNodeID )
    ———————–
    3 : Dans la procédure uspDijkstraResolve, remplacer < par < sinon la procédure en compile pas !

    ..
    — WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost — hmira 15/08/2014 (ligne mise en commentaire )
    WHEN FromNodes.Cost + Paths.Cost < ToNodes.Cost — hmira 15/08/2014 (ligne de remplacement)
    ..
    AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost) — hmira 15/08/2014 (ligne mise en commentaire )
    AND (ToNodes.Cost IS NULL OR FromNodes.Cost + Paths.Cost < ToNodes.Cost) — hmira 15/08/2014 (ligne de remplacement)
    ———————–
    4 : Idem dans procédure dbo.uspDijkstraCreateMatrix, il manque le signe (ou opérateur ) je crois que cela est lié à l’éditeur du blog et HTML (?). je vous propose la modification ci-dessous (sinon la procédure ne compile pas ! c’est dommage !) :

    — WHERE FromNode.NodeName ToNode.NodeName; — hmira 15/08/2014 (ligne mise en commentaire )
    WHERE FromNode.NodeName ToNode.NodeName; — hmira 15/08/2014 (ligne de remplacement : ajout du signe )
    ———————–

    Encore une fois, Merci.

    A+

    ↓

Laisser un commentaire