« Séparation et évaluation » : différence entre les versions
Aucun résumé des modifications Balise : Éditeur de wikicode 2017 |
Aucun résumé des modifications |
||
| Ligne 1 : | Ligne 1 : | ||
== Domaine == | ==Domaine== | ||
[[category:Vocabulaire]] | [[category:Vocabulaire]] | ||
[[Catégorie:Wikipedia-IA]] [[Catégorie:Apprentissage automatique]] [[Catégorie:Algorithme d'optimisation]] | [[Catégorie:Wikipedia-IA]] | ||
[[Catégorie:Apprentissage automatique]] | |||
[[Catégorie:Algorithme d'optimisation]] | |||
[[Catégorie:scotty]] | [[Catégorie:scotty]] | ||
| Ligne 7 : | Ligne 9 : | ||
<br> | <br> | ||
== description == | ==description== | ||
Un algorithme par séparation et évaluation | Un algorithme par séparation et évaluation (''branch and bound)'' est une méthode générique de résolution de problèmes d'optimisation combinatoire. | ||
L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela. | L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela. | ||
| Ligne 14 : | Ligne 16 : | ||
<br> | <br> | ||
== Français == | ==Français== | ||
'''séparation et évaluation''' | '''séparation et évaluation''' | ||
| Ligne 20 : | Ligne 22 : | ||
<br> | <br> | ||
== Anglais == | ==Anglais== | ||
'''branch and bound''' | '''branch and bound''' | ||
<br> | <br> | ||
<br> | <br> | ||
[https://fr.wikipedia.org/wiki/S%C3%A9paration_et_%C3%A9valuation | [https://fr.wikipedia.org/wiki/S%C3%A9paration_et_%C3%A9valuation Source : Wikipedia IA] | ||
<br> | <br> | ||
<br> | <br> | ||
Version du 27 mai 2019 à 20:52
Domaine
description
Un algorithme par séparation et évaluation (branch and bound) est une méthode générique de résolution de problèmes d'optimisation combinatoire.
L'optimisation combinatoire consiste à trouver un point minimisant une fonction, appelée coût, dans un ensemble dénombrable. Une méthode naïve pour résoudre ce problème est d'énumérer toutes les solutions du problème, de calculer le coût pour chacune, puis de donner le minimum. Parfois, il est possible d'éviter d'énumérer des solutions dont on sait, par l'analyse des propriétés du problème, que ce sont de mauvaises solutions, c'est-à-dire des solutions qui ne peuvent pas être le minimum. La méthode séparation et évaluation est une méthode générale pour cela.
Français
séparation et évaluation
Anglais
branch and bound
Source : Wikipedia IA
Contributeurs: Jacques Barolet, wiki
