* Bonjour, *
Pour un projet on m'a demandé de faire un algo de placement optimal d'un centre commercial (distance entre et population des villes)
Je me suis amusé à le faire en T-SQL et je n'ai pas trouvé de vrai procédure sur le net. Il y avait une partir sur le plus court chemin écrites par un utilisateur SwePerso sur sqlteam.com mais je l'ai modifié pour le pousser plus loin.
Voici le code si cela vous intéresse:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10 CREATE TABLE [dbo].[Nodes] ( [NodeID] [int] IDENTITY (1, 1) NOT NULL , [NodeName] [varchar] (20) NOT NULL , [Cost] [int] NULL , [PathID] [int] NULL , [Calculated] [tinyint] NOT NULL, [Population] INT NULL, [Score] INT ) ON [PRIMARY] GO
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 CREATE TABLE [dbo].[Paths] ( [PathID] [int] IDENTITY (1, 1) NOT NULL , [FromNodeID] [int] NOT NULL , [ToNodeID] [int] NOT NULL , [Cost] [int] NOT NULL ) ON [PRIMARY] GO
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 ALTER TABLE [dbo].[Nodes] WITH NOCHECK ADD CONSTRAINT [PK_Nodes] PRIMARY KEY CLUSTERED ( [NodeID] ) ON [PRIMARY] GO
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 ALTER TABLE [dbo].[Paths] WITH NOCHECK ADD CONSTRAINT [PK_Paths] PRIMARY KEY CLUSTERED ( [PathID] ) ON [PRIMARY] GO
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14 ALTER TABLE [dbo].[Paths] ADD CONSTRAINT [FK_Paths_FromNodes] FOREIGN KEY ( [FromNodeID] ) REFERENCES [dbo].[Nodes] ( [NodeID] ), CONSTRAINT [FK_Paths_ToNodes] FOREIGN KEY ( [ToNodeID] ) REFERENCES [dbo].[Nodes] ( [NodeID] ) GO-----------------------------------------------------------------
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 CREATE TABLE [dbo].[PathsMatrix] ( [MatPathID] [int] IDENTITY (1, 1) NOT NULL , [FromNodeID] [int] NOT NULL , [ToNodeID] [int] NOT NULL , [Cost] [int] NULL ) ON [PRIMARY] GO
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13 CREATE PROCEDURE dbo.uspDijkstraInitializeMap AS DELETE FROM Paths DBCC CHECKIDENT (Paths, RESEED, 0) DELETE FROM Nodes DBCC CHECKIDENT (Nodes, RESEED, 0) GO
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8 CREATE PROCEDURE dbo.uspDijkstraClearMap AS UPDATE Nodes SET PathID = NULL, Cost = NULL, Calculated = 0 GO--------------------------------------------------------
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75 CREATE PROCEDURE dbo.uspDijkstraAddPath ( @FromNodeName VARCHAR(20), @ToNodeName VARCHAR(20), @Cost INT ) AS SET NOCOUNT ON DECLARE @FromNodeID INT, @ToNodeID INT, @PathID INT 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
---------------------------
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133 CREATE PROCEDURE dbo.uspDijkstraResolve ( @FromNodeName VARCHAR(20), @ToNodeName VARCHAR(20) ) AS 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 INT = (SELECT TOP 1 MatPathID FROM PathsMatrix ORDER BY MatPathID DESC) EXEC dbo.uspDijkstraClearMap DECLARE @FromNodeID INT, @ToNodeID INT, @NodeID INT, @Cost INT, @PathID INT SELECT @FromNodeID = NodeID, @NodeID = NodeID FROM Nodes WHERE NodeName = @FromNodeName IF @FromNodeID IS NULL BEGIN SELECT @FromNodeName = ISNULL(@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 = ISNULL(@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 CREATE TABLE #Map ( RowID INT IDENTITY(-1, -1), FromNodeName VARCHAR(20), ToNodeName VARCHAR(20), Cost INT ) IF EXISTS (SELECT NULL FROM Nodes WHERE NodeID = @ToNodeID AND Cost IS NULL) BEGIN SELECT FromNodeName, ToNodeName, Cost FROM #Map DROP TABLE #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 DROP TABLE #Map GO
--------------------
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 CREATE PROCEDURE dbo.uspDijkstraCreateMatrix AS SET NOCOUNT ON IF EXISTS (SELECT 1 FROM PathsMatrix) BEGIN TRUNCATE TABLE PathsMatrix END DECLARE @From VARCHAR(20), @To VARCHAR(20) DECLARE cursorNodes CURSOR FOR SELECT FromNode.NodeName, ToNode.NodeName FROM nodes as FromNode CROSS JOIN nodes as ToNode WHERE FromNode.NodeName <> ToNode.NodeName OPEN cursorNodes FETCH NEXT FROM cursorNodes INTO @From, @To WHILE @@FETCH_STATUS = 0 BEGIN EXEC dbo.uspDijkstraResolve @FromNodeName = @From, @ToNodeName = @To FETCH NEXT FROM cursorNodes INTO @From, @To END CLOSE cursorNodes DEALLOCATE cursorNodes
* Merci *
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89 CREATE PROCEDURE dbo.uspDijkstraCalculateOptimal AS DECLARE @FromNodeID VARCHAR(20) DECLARE cursorNodes CURSOR FOR SELECT FromNode.NodeID FROM nodes as FromNode OPEN cursorNodes FETCH NEXT FROM cursorNodes INTO @FromNodeID WHILE @@FETCH_STATUS = 0 BEGIN UPDATE Nodes SET Score = (SELECT SUM((N.Population)*P.Cost) FROM Nodes N JOIN PathsMatrix P ON P.FromNodeID = N.NodeID WHERE N.NodeID = @FromNodeID) WHERE Nodes.NodeId = @FromNodeID FETCH NEXT FROM cursorNodes INTO @FromNodeID END CLOSE cursorNodes DEALLOCATE cursorNodes SELECT NodeName, Score FROM Nodes ORDER BY Score DESC ------------------------- -- delete previous map EXEC dbo.uspdijkstrainitializemap -- create a new map 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 -- Create matrix of distances EXEC dbo.uspDijkstraCreateMatrix -- UPDATE populations 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' -- Placement Optimale EXEC dbo.uspDijkstraCalculateOptimal
Partager