Discussion:Séparation et évaluation
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par le projet Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Voici[modifier le code]
Voici une definition (rapide) complémentaire :
Branch and Bound : PSE (Procédure par séparation-évaluation).
Il s'agit d'une méthode de résolution exacte de problèmes d'optimisation (resp. de décision) au moins NP-difficile (resp. NP-complet) au sens fort.
Le principe de base de la PSE est :
- de partitionner l'espace des solutions réalisables à partir d'un noeud en n sous ensembles, donnant ainsi naissance à n noeuds fils (la séparation),
- de juger l'utiliter des fils générés vis à vis de la fonction objectif (l'évaluation).
La procédure débute du noeud racine ne comportant aucune restriction sur l'espace des solutions accessibles et une solution strictement améliorante est décrite à un noeud feuille de l'arbre de recherche.
La procédure nécessite une borne supérieure que l'on peut calculer à l'aide d'une heuristique plus ou moins efficace (cf. descente locale, recuit simulé, recherche tabou, etc...) ou itérativement par invalidation de la précédente borne avec la procédure elle même.
La phase d'évaluation est réalisée à l'aide d'une borne inférieure que l'on compare à la borne supérieure, bien que, souvent, on se contente de se demander si le noeud peut engendrer une solution strictement améliorante avec un booléen en réponse sans se soucier réellement de la valeur numérique.
Il existe principalement deux types de PSE :
- en profondeur d'abord : qui consiste à avoir au plus un seul noeud d'une profondeur donnée dans la pile.
- en largeur d'abord : qui consite à développer tous les noeud d'un même niveau consécutiovement.
Le choix entre profondeur/largeur est étroitement lié à la connaissance du problème, le choix largeur d'abord posant généralement un problème de stockage des noeuds (table de hachage et explosion en mémoire).
L'exécution d'une PSE de déroule en deux partie :
- la recherche de la solution optimale, - la vérification de l'optimalité de la solution.
Le propre de la procédure est qu'il est impossible de savoir dans quelle phase la procédure est rendue avant sa fin complète sachant que le temps nécéssaire à l'exécution complète de la procédure peut être quasi infini.
Ce principe de base peut etre complété par :
- des conditions de dominances sur la structure des solutions, - des conditions de dominances entre les noeuds, - des techniques d'ajustements.
PS : pour etre rigoureux il faudrait rajouter des ref comme Cook71 et Glover89.
Séparation et évaluation[modifier le code]
Il y a également un article Séparation et évaluation qui fait doublon avec cet article. Il faudrait bien sûr fusionner les deux articles.
Branch and bound et Séparation et évaluation[modifier le code]
La méthode porte ces deux noms. La version anglaise est je pense un peu plus utilisée mais la version française est quand même standard. Les deux articles ont à peu près la même ancienneté et un historique faible. L'article Séparation et évaluation est plus technique. L'article "branch and bound" ne permet pas de comprendre la méthode (à mon avis). Francis.sourd 22 août 2005 à 16:21 (CEST)
- Fusion depuis Branch and bound phe 7 novembre 2005 à 04:23 (CET)
Ref/sources[modifier le code]
Quelques références et sources ne feraient pas de mal, d'où le bandeau. Cordialement--Jimmy-jambe (d) 27 juin 2012 à 16:16 (CEST)
- Je viens d'ajouter des sources et de retirer le bandeau.--Roll-Morton (discuter) 16 janvier 2015 à 19:58 (CET)
Idées[modifier le code]
- Ajouter SBB, une version décentralisée de l'algo, où les variables sont les agents (en gros). Les agents choisissent un ordre total. Puis c'est comme branch and bound mais les actions faites sur une variable précise sont faite par l'agent correspondant.