Cheminements Flashcards
Comment répondre à la question “Existe-t-il un chemin de longueur quelconque entre deux points x et y” ?
On les calcul les puissances de la matrice d’adjacence M jusqu’à M^(2k) avec 2k >= n-1
Décrire l’objectif et les conditions l’algorithme de Moore-Dijkstra (1959). Quelle est sa complexité ?
Recherche du plus court chemin entre deux points
Conditions : pas de circuit de valuation négative
Complexité en O(n²) + O(m)
Quelles sont les notations usuelles utilisées dans l’algorithme de Moore-Dijkstra ?
- X = {1,2,3,…,n}
- lij = longueur de l’arc (i,j) s’il existe sinon l’infini
- λi* = longueur du plus court chemin de l’origine 1 vers le sommet j
- S = { i pour lesquels λi = λi* avec 1 ∈ S} et X-S = {les sommets pour lesquels λi* = min [ λk* + lki ]}
Quel est le principe de l’algorithme de Moore-Dijkstra ?
L’algorithme consiste à trouver λi* en affectant à chaque sommet i une valeur provisoire λi qui se stabilise en un nombre d’itérations finies à la valeur λi*. À chaque étape (sommet) on fait k comparaisons (n-1 sommets restants). La somme est de l’ordre de n².
Décrire l’objectif de l’algorithme de Ford (1958-62), son avantage et sa complexité
- recherche du plus court chemin entre deux points
- s’adapte facilement à la recherche du chemin de valeur maximale
- complexité en O(n²m)
Une fois les étapes réparties en niveaux, quelles sont les itérations de l’algorithme de Ford ?
- affecter provisoirement à tout sommet i un poids λi = 0 si i=1 et +∞ sinon
- chercher les arcs (i,j) tel que λj - λi > lij ; on remplace alors λj par λj = λi + lij
- réitérer jusqu’à ce qu’aucun arc ne permette plus de diminuer les λi
Quelle est l’étape préliminaire à l’algorithme de Ford ?
- représenter le graphe en niveau : chaque sommet xi d’un niveau donné est tel que tous les sommets xj qui le suivent immédiatement se trouvent dans les niveaux de numéro inférieur et au moins un dans le niveau de numéro immédiatement inférieur
Quel est le principe de l’algorithme de Bellman-Kalaba ?
- L’algorithme est fondé sur le principe d’optimalité “tout sous-chemin optimal” est optimal
- Il se déroule à rebrousse-chemin en cherchant successivement tous les chemins de longueur p = 1,2,3,.. et en mettant à jour la valeur minimale de la distance pour chaque sommet
Quels sont les problèmes posés par la réalisation d’un objectif décomposable en multiples tâches élémentaires ?
Planifier en optimisant un ou plusieurs critères (coût, temps) et en respectant quelques contraintes.
A quels types de contraintes peut-on faire face dans un problème d’ordonnancement ?
- contraintes potentielles : succession de tâche ou fixation temporelle
- contraintes disjonctives : son simultanéité des tâches
- contraintes cumulatives : ressources limitées à répartir entre les différentes tâches
Que signifie PERT ? A quel type de problème cet algorithme répond-il ?
- Project Evaluation and Review Technique
- Comment ordonnancer les différentes tâches en respectant les contraintes de succession (potentielles) pour minimiser le temps total de réalisation du projet.
Décrire le graphe d’un projet d’ordonnancement avec contraintes de successions (PERT).
- les sommets sont les événements et les arcs sont les opérations dont la valeur équivaut à la durée de la tâche
- entrée = début des opérations, sortie = fin
- il est connexe et sans circuit
Quelle est la première étape de l’algorithme PERT avant de tracer le graphe ?
Simplifier le tableau des tâches antécédentes
Qu’est-ce que la marge libre ?
Le retard possible sans conséquence sur les autres tâches (planning général non perturbé) mij = tj – ti – tij
Qu’est-ce que la marge totale ?
Le retard possible avec des conséquences sur les autres tâches mais sans conséquence sur la durée totale du programme (le retard est en fait absorbé par les marges libres des autres tâches) Mij = tj* – ti – tij
