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

Optimisation discrète: problème de vendeur itinérant

Description

Cette séance de cours présente le problème des vendeurs itinérants, où l'objectif est de trouver l'itinéraire le plus court pour visiter toutes les villes une seule fois. L'instructeur couvre la modélisation du problème avec des variables et des contraintes de décision, y compris des contraintes supplémentaires et une représentation du réseau. La séance de cours se termine par la formulation du problème et un résumé.

Dans MOOC

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

Source officielle

Concepts associés (14)

Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers. Three notable branches of discrete optimization are: combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures integer programming constraint programming These branches are all closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.

Optimisation combinatoire

L’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur un ensemble. L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées (fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la commande.

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Problème du voyageur de commerce

vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné un ensemble de villes, le plus court circuit passant par chaque ville une seule fois. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité.

Afficher plus

Séances de cours associées (37)

Optimisation discrète : définir la couverture MOOC: Optimisation : principes et algorithmes - Optimisation discrète et en réseau

Explore le problème de couverture de l'ensemble à travers l'exemple de compléter une collection d'autocollants à un coût minimum.

Optimisation avec contraintes : conditions KKT

Couvre les conditions KKT pour l'optimisation avec des contraintes, essentielles pour résoudre efficacement les problèmes d'optimisation.

Problème de vendeur itinérant: Introduction et méthodes d'approximation

Présente le problème des vendeurs itinérants et explore les méthodes d'approximation à l'aide des chaînes de Markov.

Méthodes d'optimisation : discussion théorique

Explore les méthodes d'optimisation, y compris les problèmes sans contraintes, la programmation linéaire et les approches heuristiques.

Le problème du sac à dos MOOC: Information, Calcul, Communication: Introduction à la pensée informatique

Présente le problème du sac à dos, un problème d'optimisation discret avec des contraintes et des algorithmes pour le résoudre.

Afficher plus

Concepts associés (14)

Discrete optimization

Optimisation combinatoire

Optimisation (mathématiques)

Optimization problem

Problème du voyageur de commerce

Afficher plus