| Property |
Value |
| dbo:abstract
|
- Un algorithme par séparation et évaluation, ou branch and bound en anglais, 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. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt destiné aux problèmes de recherche opérationnelle. (fr)
- Un algorithme par séparation et évaluation, ou branch and bound en anglais, 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. Cette méthode est très utilisée pour résoudre des problèmes NP-complets, c'est-à-dire des problèmes considérés comme difficiles à résoudre efficacement. Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt destiné aux problèmes de recherche opérationnelle. (fr)
|
| dbo:discoverer
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8454 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:auteur
|
- Djamal Rebaïne (fr)
- Djamal Rebaïne (fr)
|
| prop-fr:langue
| |
| prop-fr:site
|
- Université du Québec à Chicoutimi (fr)
- Université du Québec à Chicoutimi (fr)
|
| prop-fr:url
|
- http://www.uqac.ca/rebaine/8INF806/techniquedebranchandboundcourshiver2005.pdf|titre=Note de cours : La méthode de branch and bound (fr)
- http://www.uqac.ca/rebaine/8INF806/techniquedebranchandboundcourshiver2005.pdf|titre=Note de cours : La méthode de branch and bound (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Un algorithme par séparation et évaluation, ou branch and bound en anglais, 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. (fr)
- Un algorithme par séparation et évaluation, ou branch and bound en anglais, 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. (fr)
|
| rdfs:label
|
- Branch-and-Bound (de)
- Ramificación y poda (es)
- Séparation et évaluation (fr)
- Метод ветвей и границ (ru)
- 分枝限定法 (ja)
- Branch-and-Bound (de)
- Ramificación y poda (es)
- Séparation et évaluation (fr)
- Метод ветвей и границ (ru)
- 分枝限定法 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
