Parcours d'une matrice(Gantt)

Version imprimable

09/01/2008, 10h49
asmiti

Parcours d'une matrice(Gantt)

Bonjour,
je travaille sur un programme de gestion de vols.Les vols sont sont représentés sur une matrice(diagramme de Gantt).Je cherche à trouver les vols qui se chevauchent.J'ai déjà l'algo naif mais je cherche à l'améliorer vu que je suis obligé de parcourir tous les vols sur la meme ligne pour trouver les conflits.Est ce que qq'un a une idée pour cet algo.
Merci d'avance
09/01/2008, 11h14
pseudocode

Est-ce que ton probleme est similaire a celui la:

http://www.developpez.net/forums/sho...d.php?t=432992
09/01/2008, 11h47
asmiti

RE

Le point commun entre les deux c'est que chaque vol est bien défini par une date de début et une date de fin et je cherche evidemment les chevauchenments.Mais l'algo que t viens de me passer va parcourir tous les vols alors que moi je cherche à éviter ça
09/01/2008, 13h24
pseudocode

Citation:

Envoyé par asmiti

Le point commun entre les deux c'est que chaque vol est bien défini par une date de début et une date de fin et je cherche evidemment les chevauchenments.Mais l'algo que t viens de me passer va parcourir tous les vols alors que moi je cherche à éviter ça

hum... trouver TOUS les vols qui se chevauchent sans parcourir TOUS les vols, je vois pas trop comment faire. :koi:
09/01/2008, 16h17
ToTo13

Bonjour,

pour connaitre les chevauchements, il faut parcourir AU MOINS UNE FOIS la liste de tous les vols.
Ensuite, ce que tu cherches à minimiser c'est la complexité de la recherche.

Sur qu'elle période se déroule les vols et qu'elle est l'unité minimum de temps (la minutes ?) ?
10/01/2008, 11h01
asmiti

oui,la durée min est en minutes.J'ai pensé à faire un algo en dichotomie pour limiter la recherche en ajoutant un autre parametre qui est le temps.Je serai donc pas obligé de parcourir tt le diagramme mais j'ai des soucis avec les cas particuliers.T'en penses quoi?
10/01/2008, 11h36
pseudocode

Quelle recherche ? :koi:

L'algo sweep construit au fur et a mesure la liste des zones qui se chevauchent. Y a un truc que j'ai pas du comprendre dans ton probleme. :aie:
10/01/2008, 17h37
asmiti

au fait mon probleme ressemble à celui là http://www.developpez.net/forums/sho...d.php?t=293580,
C'est un systeme de gestion de vols sur un diagramme de Gantt,quand j'ajoute un nouveau vol,je cherche la liste des vols avec lesquels mon nouveau vol chevauche.
mais j'arrive pas à trouver le code qui remplacera la commande OVERLAPS.

Je comprend pas pourquoi le sweep ne convient pas. :koi:
Peut-etre qu'avec un exemple tu pourras me dire ou ca coince:

Liste des Vols connus:

Code:

1
2
3
4
5
 
Vol1 - 10:00 à 12:00
Vol2 - 11:00 à 15:00
Vol3 - 13:00 à 15:00
Vol4 - 14:00 à 16:00

construction de la table sweep des vols connus:

Code:

1
2
3
4
5
6
7
8
9
10
11
 
 date :   id [action]: ## : actifs
--------------------------------------------
10:00 : Vol1 [start] : +1 : [Vol1]
11:00 : Vol2 [start] : +2 : [Vol1,Vol2]
12:00 : Vol1 [end]   : +1 : [Vol2]
13:00 : Vol3 [start] : +2 : [Vol2,Vol3]
14:00 : Vol4 [start] : +3 : [Vol2,Vol3,Vol4]
15:00 : Vol2 [end]   : +2 : [Vol3,Vol4]
15:00 : Vol3 [end]   : +1 : [Vol4]
16:00 : Vol4 [end]   :  0 : []

Maintenant, on veut tester les conflits possibles pour un nouveau vol de 12:30 à 14:30

Code:

1
2
3
4
5
6
7
8
 
1. Liste des vols actifs à 12:30 
=> chercher l'entrée précendent 12:30 dans la table sweep --> 12:00
=> copier la liste des vols actifs de cette entrée --> [Vol2]
 
2. Liste des vols partant après 12:30 et avant 14:30
==> parcourir la table sweep entre 12h30 et 14h30
    et enumerer la liste de entrées qui sont en [start] --> [Vol3] , [Vol4]

La liste des vols en conflit est donc: Vol2 , Vol3 , Vol4

10/01/2008, 18h31
Graffito
Bonjour,

Est-ce que tu recherches plûtot ?
1. une requête (ou une combinaison de requêtes) SQL sur une base de donnée,
2. un algo sur des enregistrements chargés en mémoire.
Citation:

Je cherche les vols qui se chevauchent
- l'ensemble de tous les couples sur toute la base ?
- les vols opérant à une heure précise ?
15/01/2008, 11h35
asmiti

je cherche plutot un algo que je vais ensuite coder en c#.L'algo de sweep correspond à ce que je recherche mais le probleme c'est le stockage des données.Au fait j'ai plusieurs ressources ou je stocke plusieurs vols donc si à chaque fois je vais créer un tableau de sweep l'appli sera lourde à telecharger et inmaintenable.
15/01/2008, 11h42
pseudocode

Citation:

Envoyé par asmiti

Au fait j'ai plusieurs ressources ou je stocke plusieurs vols donc si à chaque fois je vais créer un tableau de sweep l'appli sera lourde à telecharger et inmaintenable.

Comme l'a dit ToTo13:

Citation:

pour connaitre les chevauchements, il faut parcourir AU MOINS UNE FOIS la liste de tous les vols.

Si tu as créé une ressource par vol, il va falloir que tu ouvres toutes des ressources au moins une fois. Peut-etre qu'il vaudrait mieux créer une autre ressource qui serait un "index" de tous les vols, avec au minimum les infos necessaires au sweep.
15/01/2008, 11h52
asmiti

et ça consiste en quoi?
15/01/2008, 11h56
pseudocode

Citation:

Envoyé par asmiti

et ça consiste en quoi?

Créer un index pour le sweep ?

Bah c'est juste une liste avec les 3 infos : #vol, date départ, date arrivée.

Avec cette liste tu peux construire la table de sweep à la demande... En ajoutant une heuristique sur la durée maximum des vols, tu peux meme restreindre la construction de la table de sweep à un intervalle de temps utile.
16/01/2008, 11h32
asmiti

1 pièce(s) jointe(s)

Au fait mes vols et mes ressources sont répartis comme l'indique l'image ci jointe.Donc en matière de stockage ca va etre très dur et le chargement très lent
16/01/2008, 16h23
pseudocode

Ca c'est la représentation graphique... Mais comment sont stockées les informations dans le programme ? (tableau, liste, ... )
16/01/2008, 17h09
asmiti

la je fais tout refaire en ce qui concerne le stockage des donées.Donc j'ai libre choix

la représentation graphique c'était juste pour t'éclaircir le problème;)
16/01/2008, 17h34
pseudocode

Dans ce cas, tu peux regrouper tes infos par "semaine". Chaque objet "semaine" contient la liste des vols qui partent (start) dans la semaine.

- Pour ton affichage tu as besoin de 4 ou 5 objets "semaine" simultanément.

- Pour l'algo de conflit, si on considere que les vols ne durent pas plus de 7 jours, tu as besoin de 3 a 4 "semaines" (S-1,S,S+1,S+2) pour construire le tableau de sweep.
17/01/2008, 10h31
asmiti

excuse moi je t ai pas donne le bon exemple,au fait c'est le meme schema mais au lieu des semaines c'est plutot des heures.donc ca sera pas possible de créer des tableau semaine
17/01/2008, 10h40
pseudocode

Semaine, mois, heure... En fait ce sont des unités de temps. L'important c'est de trouver la taille de l'unité de temps qui a un sens dans ton métier (jour, demi-journée, ... )

Un petit détour par le forum "conception" pourrait peut-être t'aider. ;)