Catégorie

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. Formellement, étant donnés : un ensemble discret fini; une fonction d'ensemble , dite fonction objectif ; et un ensemble de sous-ensembles de , dont les éléments sont appelés les solutions réalisables, un problème d'optimisation combinatoire consiste à déterminer L'ensemble des solutions réalisables ne saurait être décrit par une liste exhaustive car la difficulté réside ici précisément dans le fait que le nombre des solutions réalisables rend son énumération impossible, ou bien qu'il est NP-complet de dire s'il en existe ou non. La description de est donc implicite, il s'agit en général de la liste, relativement courte, des propriétés des solutions réalisables. La plupart du temps, on est dans les cas particuliers suivants : et où et la cardinalité de est exponentielle en ; donc les propriétés de se traduisent en contraintes linéaires, c'est-à-dire que et un polyèdre de ; Le problème du voyageur de commerce (TSP) où un voyageur de Commerce doit parcourir les N villes d'un pays en effectuant le trajet le plus court. Une résolution par énumération nécessite de calculer ((N-1)!)/2 trajets entre des villes. En particulier, pour 24 villes, il faudrait en générer (23!)/2 2,5×1022. Pour fournir un ordre de grandeur comparatif, une année ne compte qu'environ 3,16×1013 microsecondes. Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d'essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure.

Ontologie

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Exercices associés (10)

Le corbeau et le renard

A few days after the events narrated in the famous fable[1], the crow and the fox meet again. Having learned from its mistakes, the crow is determined not to be fooled again by the fox’s flattery. The fox, however, is set on getting a second piece of cheese. This time , it chooses a more direct method and throws a stone at the crow to scare it. It works beyond expectations: as soon as the stone is thrown, the crow drops the cheese. The crow is perched on a tree of height H; the fox is a distance L from the

Point sur un cylindre

A material point moves on an infinitely long cylinder of radius R. The material point is attracted to a point O on the cylinder’s axes by a force that’s proportional to the distance between the material point and O. There is neither gravity nor friction.

List the forces acting on the material point. Draw these forces on a diagram, as well as the frame of reference associated with the chosen coordinate system.
Write the equations of motion and project them on the frame of reference.

Plot sur plan incliné

A block of mass M on an inclined plane of angle α with respect to the horizontal plane is attached with a massless cable to a mass m, hanging in the air. The friction is dry.

Determine the mass m needed to overcome the dry friction characterised by the static friction coefficient μ_(s).
In motion, the block is subjected to a dry friction characterised by the kinetic friction coefficient μ_(c). Establish the equations of motion.
Overcoming the static friction amounts to finding the

Coquille sphérique

Calculate, in any point of space, the electrostatic potential

V(\bf{r})

and the field

\bf{E}(\bf{r})

created by a spherical shell uniformly charged with an internal radius a, external b, and of total charge u2005+u2005Q, centered at the origin O of the cartesian axes. Graphically represent the functions

V(\bf{r})

and

E_r(\bf{r})

(the radial component of

\bf{E}(\bf{r})

) Replace now the charged shell by an ideal conductor of similar shape. The conductor is neutral and isolated. A charge u2005+u2005

Le liévre et la tortue

A hare and a turtle race over a distance L. The turtle starts running at constant speed

v_{\rm t}

and the hare at constant speed

v_{\rm h}

. The hare is not taking this seriously, and so

v_{\rm h} < v_{\rm t}

. When the turtle reaches a bridge that stands at a distance L′u2004

Afficher plus

Notebooks associés (11)

Designing FIR Filters Using the Parks-McClellan Algorithm

The Parks-McClellan Filter Design Method[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

The Parks-McClellan (PM) algorithm is a clever application of advanced polynomial fitting techniques to the problem of FIR filter design. In this notebook we will explore the key ideas behind the method by considering the design of a simple Type-I lowpass filter. NOTE: This notebook uses interactive widgets. If the interactive controls do not work or show up, please fo

Sustainability Week 1: The Carbon Footprint of Algorithms – Solutions

{#Sustainability-Week-1:-the-Carbon-Footprint-of-Algorithms} How to use this notebook Simply read the text and follow the instructions.
This notebook contains code cells, which can be modified and must be executed to see the result of their content.
To execute a cell, select it and click on the play button (▶) in the tool bar, or type Shift + Enter or Ctr + Enter. As the variables contained in a cell are stored in memory, the order of execution of the cells is important! Notebook by M

Voice Transformation Techniques Using Digital Signal Processing

A Gallery of Voice Transformers[1]¶

                                      [2]Paolo Prandoni, [3]LCAV, EPFL

In this notebook we will explore various ways to implement a system that changes the voice of a speaker. Typical applications for these techniques, strictly sorted by plausibility, include international spy missions and prank telephone calls, and devices such as the one displayed here can be easily bought on the web... or in a novelty shop. No description has been provided for t

Exploring Quantization and Oversampling through One-Bit Music

One-Bit Music[1]¶ In this notebook we will talk about quantization and oversampling and we will do so by taking a trip down memory lane to revisit the early from monophonic square waves, introduce polyphony by way of pulse-width modulation and finish with the basics of sigma-delta quantization. pacman In [1]: import matplotlib import matplotlib.pyplot as plt import numpy as np import scipy.signal as sp from scipy.io import wavfile import IPython In [2]: import sys ! wget -q -O mus