Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Parcours le plus court, Parcours le plus long

Description

Cette séance de cours traite de la transformation d'un problème de chemin le plus court en un problème de chemin le plus long en optimisation. Il explique les implications de la modification de l'objectif de minimiser à maximiser les coûts, la définition des problèmes de chemin le plus court et le plus long, l'importance de trouver un chemin simple, et le risque de cycles de coûts négatifs. L'instructeur fournit des exemples et explique comment résoudre le problème du chemin le plus long équivaut à résoudre le problème du chemin le plus court avec des coûts négatifs.

Dans MOOC

Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Source officielle

Concepts associés (11)

Problème de plus court chemin

vignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur.

Problème de la plus longue chaîne

vignette|Par suppression d'une arête rouge arbitraire, ce cycle hamiltonien donne une chaîne de longueur maximale. En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin.

Chaîne (théorie des graphes)

Dans un graphe non orienté, une chaîne reliant à , notée , est définie par une suite finie d'arêtes consécutives, reliant à . La notion correspondante dans les graphes orientés est celle de chemin. Une chaîne élémentaire est une chaîne ne passant pas deux fois par un même sommet, c'est-à-dire dont tous les sommets sont distincts. Une chaîne simple est une chaîne ne passant pas deux fois par une même arête, c'est-à-dire dont toutes les arêtes sont distinctes. Un cycle est une chaîne simple dont les deux extrémités sont identiques.

Cost curve

In economics, a cost curve is a graph of the costs of production as a function of total quantity produced. In a free market economy, productively efficient firms optimize their production process by minimizing cost consistent with each possible level of production, and the result is a cost curve. Profit-maximizing firms use cost curves to decide output quantities. There are various types of cost curves, all related to each other, including total and average cost curves; marginal ("for each additional unit") cost curves, which are equal to the differential of the total cost curves; and variable cost curves.

Induced path

In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.

Afficher plus

Séances de cours associées (29)

Chemin le plus court: Propriétés MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Couvre le manque de complémentarité, les conditions d'optimalité, les preuves, les cycles de coûts négatifs et les chemins simples dans l'optimisation du réseau.

Chemin le plus court: Propriétés de l'algorithme MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explique les propriétés de l'algorithme de chemin le plus court et comment trouver le chemin le plus court dans un réseau.

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Le problème du transbordement: le plus court problème de chemin MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Couvre les problèmes de transbordement et de chemin le plus court dans l'optimisation du réseau.

Programmation dynamique : le triangle de Pascal et l'algorithme de Floyd

Explore la programmation dynamique à travers le Triangle de Pascal et l'Algorithme de Floyd.

Afficher plus

Concepts associés (11)

Problème de plus court chemin

Problème de la plus longue chaîne

Chaîne (théorie des graphes)

Cost curve

Induced path

Afficher plus