Discussion :

[Waldar]

450 ms, ce n'est pas catastrophique !

Les trois étapes sont :

• 1 - requête récursive pour calculer l'ensemble des chemins possibles entre la gare de départ et la gare d'arrivée : résultat placé dans la table CHEMIN avec un numéro comme clef (70968 lignes). J'ai suivi l'excellent tutoriel : http://sqlpro.developpez.com/cours/s...te-recursives/
  Cela me donne des chemins avec un varchar contenant les points de décision et les convoyeurs dans l'ordre de parcours pour chaque chemin.
  (Aie c'est la que je sens que je vais faire hurler les puristes)
  A noter que cette table est 'statique', comme mes convoyeurs sont des données fixes, elle est calculée une seule fois

• 2 - Eclatement de la table chemin en une table DETAIL_CHEMIN contenant une ligne par chemin et par convoyeur (1786536 lignes)

• 3 - recherche des chemins qui m'intéressent dans la table précédente en faisant un produit croisé avec la table ETAPES puis en filtrant les chemins qui ont le nombre d'étapes demandées (soit 10 ici)
  A noter que je doute moi même de la fiabilité de l'algo basé sur un comptage sans s'assurer que l'on compte bien les même convoyeurs

En fait je suis parti sur d'autres postulats.
D'abord ne gérer que les convoyeur qui ont un sens (comme on a plusieurs chemins entre deux points, ne prendre que le plus court OU celui qui est forcé).

En partant du point de départ, suivre les chemins à partir de ces convoyeurs restants, en connectant les points de décision de départ et d'arrivée, et en s'assurant qu'on n'est pas déjà passé par un de ces chemins.

Finalement, je n'ai que peu de récursions, j'ai en tout et pour tout 354 lignes lors de la construction de tous les chemins possibles.
Si je ne fais pas ce premier filtre, ça monte à 45000. Et pourtant, je n'en filtre que 10 sur les 60 !

Ensuite je filtre sur les chemins finis, qui possèdent bien toutes les étapes obligatoires, puis sur le plus court.

[Waldar]

Je ne sais pas trop si vous vous êtes désintéressé de la question, du coup je publie quand même ma petite solution dynamique :

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
; With CONVOYEUR_SEL (no_convoyeur, no_point_decision_from, no_point_decision_to, longueur, vitesse, correctif, rn, etape) as
(
select cvy.no_convoyeur, cvy.no_point_decision_from, cvy.no_point_decision_to, cvy.longueur, cvy.vitesse, cvy.correctif
     , row_number() over(partition by no_point_decision_from, no_point_decision_to order by etp.no_etape desc, longueur desc)
     , case when etp.no_etape is not null then 1 else 0 end 
  from dbo.CONVOYEUR as cvy
       left outer join dbo.ETAPES as etp
         on etp.NO_CONVOYEUR = cvy.NO_CONVOYEUR
)
   ,   CONVOYEUR_MIN (no_convoyeur, no_point_decision_from, no_point_decision_to, longueur, vitesse, correctif, etape) as
(
select no_convoyeur, no_point_decision_from, no_point_decision_to, longueur, vitesse, correctif, etape
  from CONVOYEUR_SEL
 where rn = 1
)
   ,   CTEst (no_point_decision_from, no_point_decision_to, longueur, temps_parcours, chemin, fin_convoyage, nb_etapes_obl) as
(
select null, pde.no_point_decision, 0, cast(0.0 AS float) 
     , '"' + cast(pde.no_point_decision as varchar(max)) + '"'
     , pde.fin_convoyage, 0
  from dbo.POINT_DECISION as pde
 where pde.debut_convoyage = 1
 union all
select pdf.no_point_decision
     , pdt.no_point_decision
     , cte.longueur + cvy.longueur
     , cte.temps_parcours + case cvy.vitesse when 0 then 0.0 else (cvy.longueur / (1000.0*cvy.vitesse)) + (cvy.correctif/60.0) end
     , cte.chemin + ',"' + cast(pdt.no_point_decision as varchar) + '"'
     , pdt.fin_convoyage
     , cte.nb_etapes_obl + cvy.etape
  from CTest as cte
       inner join CONVOYEUR_MIN as cvy
         on cvy.no_point_decision_from = cte.no_point_decision_to
       inner join dbo.POINT_DECISION as pdf
         on pdf.no_point_decision = cvy.no_point_decision_from
       inner join dbo.POINT_DECISION as pdt
         on pdt.no_point_decision = cvy.no_point_decision_to
 where charindex('"' + cast(cvy.no_point_decision_to as varchar) + '"', cte.chemin) = 0
)
   ,   Choix (chemin, longueur, temps_parcours, rn) as
(
select replace(chemin, '"', '') as chemin
     , longueur
     , temps_parcours
     , row_number() over(order by longueur asc)
  from CTest
 where fin_convoyage = 1
   and nb_etapes_obl = (select count(*) from dbo.ETAPES)
)
select chemin, longueur, temps_parcours
  from Choix
 where rn = 1
 
 
chemin                                                      longueur temps_parcours
----------------------------------------------------------- -------- ----------------
36,24,20,13,1,6,7,8,9,10,21,14,15,2,3,4,5,22,12,17,27,18,33   461537 188,571447402597

[Batou69]

Je ne sais pas trop si vous vous êtes désintéressé de la question, du coup je publie quand même ma petite solution dynamique :

Oh non, pas du tout, je suis moins actif, car j'ai pas eu trop le temps ces derniers jours pour venir
Dans tous les cas, merci a tous car vos précieuses indications m'ont permis de résoudre ce problème.

Je vais étudier votre solution pour voir en quoi elle diffère de la mienne, qui parait beaucoup plus compliquée

Merci !