Discussion :

[asmiti]

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

[pseudocode]

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

http://www.developpez.net/forums/sho...d.php?t=432992

[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

[pseudocode]

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.

[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 ?) ?

[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?

[pseudocode]

Quelle recherche ?

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.

[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.

[pseudocode]

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

Liste des Vols connus:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

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 ?

[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.

[pseudocode]

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:

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.

[asmiti]

et ça consiste en quoi?

[pseudocode]

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.

[asmiti]

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

[pseudocode]

Ca c'est la représentation graphique... Mais comment sont stockées les informations dans le programme ? (tableau, liste, ... )

[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

[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.

[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

[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.