Branch and Bound Flashcards
(115 cards)
1
Q
Quelle structure de données utilise BFS ?
A
Une file (queue) FIFO
2
Q
Quelle est la complexité de BFS avec une liste d’adjacence ?
A
Θ(n + a), où n = sommets, a = arêtes
3
Q
Quel parcours est utilisé pour l’ordre topologique ?
A
DFS (profondeur)
4
Q
À quoi servent les couleurs blanc, gris et noir dans DFS ?
A
Blanc = non découvert, Gris = découvert, Noir = visité
5
Q
Quelles composantes l’algorithme DFS (parcours en profondeur) permet-il de détecter ?
A
Cycles, composantes fortement connexes, ordre topologique
6
Q
Quelle est l’idée du Branch and Bound ?
A
Explorer l’arbre des solutions possibles, tout en coupant (élaguant) les branches non prometteuses,
c’est-à-dire celles qui ne peuvent pas mener à une meilleure solution que celle déjà trouvée.
En gros l’idée c’est de brancher pour explorer et de borner pour éliminer intelligemment les solutions non optimales
7
Q
Vrai ou Faux : Le Branch and Bound est plus efficace que le backtracking
A
Vrai
8
Q
Vrai ou Faux : Branch and Bound ne retourne jamais en arrière
A
Faux
9
Q
À quoi sert une borne supérieure dans un problème de maximisation ?
A
Une borne supérieure dans un problème de maximisation est une estimation du meilleur score qu’on pourrait espérer obtenir en explorant une branche donnée de l’arbre de recherche.
10
Q
Exemple de problème typique ?
A
Problème d’assignation ou sac à dos
11
Q
Que signifie ‘élaguer une branche’ ?
A
Ne pas explorer une solution car elle est sous-optimale
12
Q
Quelle structure de données est souvent utilisée dans l’algorithme Branch and Bound ?
A
Une file de priorité (priority queue) -> Pourquoi?
Pour explorer les branches les plus prometteuses en premier, selon leur borne (inférieure ou supérieure)
13
Q
Quel est le lien entre Branch and Bound et DFS (parcours en profondeur)?
A
Branch and Bound explore en profondeur avec coupures intelligentes. Or B&B peut aussi utiliser BFS (parcours en largeur) ou best-first mais DFS avec élagage est la stratégie classique.
14
Q
Comment calcule-t-on une borne inférieure ?
A
En estimant la meilleure solution possible à partir d’un nœud
15
Q
Vrai ou Faux : On explore toujours toute l’arborescence
A
Faux
16
Q
Pourquoi utiliser Branch and Bound ?
A
L’idée principale est de réduire le nombre de solutions explorées inutilement
17
Q
que fait-on si la borne est pire que la solution actuelle ?
A
On ne continue pas (élagage)
18
Q
Comment choisir l’enfant à explorer en priorité ?
A
Celui avec la meilleure borne
19
Q
Branch and Bound est-il adapté aux problèmes NP-complets ?
A
Oui, en particulier pour ceux d’optimisation
20
Q
Vrai ou Faux : Le problème du sac à dos peut être résolu par Branch and Bound
A
Vrai
21
Q
Quel type de problème permet de calculer une borne facilement ?
A
Problème linéaire ou combinatoire
22
Q
À quoi sert la borne inférieure dans un problème de minimisation ?
A
Éliminer les branches avec coût trop élevé
23
Q
Comment éviter les doublons dans le sac à dos ?
A
Ne visiter qu’un sous-ensemble bien ordonné
24
Q
Branch and Bound fonctionne-t-il en largeur ?
A
Possible, mais profondeur prioritaire est plus courant
25
Quelle est la meilleure stratégie pour explorer en DFS vs B&B?
En retour en arrière (backtracking): utiliser un parcours en profondeur (DFS), potentiellement avec ordre glouton (objets à fort rapport valeur/poids d’abord).
En Branch and Bound :
explorer en priorité les nœuds avec les meilleures bornes (best-first) pour élaguer rapidement les branches non prometteuses.
Cela permet de trouver rapidement une bonne borne et réduire l’espace de recherche.
26
Que veut dire Branch and Bound ? (Concept derrière)
C’est une méthode d’optimisation qui explore un arbre implicite tout en élaguant les branches qui ne peuvent pas mener à une meilleure solution.
27
Explique comment fonctionne une borne dans Branch and Bound.
C’est une estimation (inférieure ou supérieure) de la meilleure solution possible à partir d’un nœud. Elle sert à élaguer.
28
Pourquoi Branch and Bound est plus efficace que le simple retour en arrière ?
Parce qu’il élimine plus tôt les solutions sous-optimales grâce aux bornes.
29
Donne un exemple où Branch and Bound est utile.
Le problème d’assignation ou du sac à dos avec contraintes. Il permet de réduire le nombre de solutions testées.
30
Que veut dire élaguer une branche ?
Ne pas explorer un sous-arbre car on sait qu’il ne peut pas contenir une meilleure solution que celle déjà trouvée.
31
Que veut dire Branch and Bound ?
C’est une méthode d’optimisation qui explore un arbre implicite tout en élaguant les branches qui ne peuvent pas mener à une meilleure solution.
32
Explique comment fonctionne une borne dans Branch and Bound.
C’est une estimation (inférieure ou supérieure) de la meilleure solution possible à partir d’un nœud. Elle sert à élaguer.
33
Pourquoi Branch and Bound est plus efficace que le simple retour en arrière ?
Parce qu’il élimine plus tôt les solutions sous-optimales grâce aux bornes.
34
Donne un exemple où Branch and Bound est utile.
Le problème d’assignation ou du sac à dos avec contraintes. Il permet de réduire le nombre de solutions testées.
35
Que veut dire élaguer une branche ? sur quoi se base t on?
Elagueer c’est ne pas explorer un sous-arbre car on sait qu’il ne peut pas contenir une meilleure solution que celle déjà trouvée.
on se base sur des bornes, soit inférieures, soit supérieurs selon le type de problème donc minimisation ou maximisation, et la borne est sur les solutions qu’on pourrait obtenir avec les enfants de chaque nœud où chaque arête du parent vers son enfant est une décision distincte d’ajouter un candidat à la solution partielle du parent du noeud.
Donc on prend la plus petite borne des sous solution ou bien la plus grande dépendamment du problème et on la fixe sur le parent
36
Complète :
Si borne (nœud) > meilleure_solution alors ______
on élague la branche
37
Quand Branch and Bound n’améliore-t-il pas les performances ?
Quand toutes les bornes sont proches ou équivalentes
38
Complète :
À chaque nœud, calculer une borne ______
inférieure (ou supérieure selon le problème)
39
Pourquoi Branch and Bound est mieux que backtracking simple ?
Parce qu'il évite d'explorer les branches qui ne peuvent pas battre la solution actuelle
40
Complexité de Branch and Bound ?
Dépend des heuristiques et du problème, mais dans le pire cas, exponentielle
41
Structure de données souvent utilisée pour prioriser les nœuds ?
File de priorité (min-heap)
42
Qu’est-ce que le backtracking (retour arrière) ?
C’est une méthode de résolution qui construit progressivement des solutions candidates et revient en arrière dès qu’un candidat ne peut plus mener à une solution valide.
43
Quel est l’exemple classique de backtracking dans les manuels ?
Le problème des huit reines sur un échiquier 8x8, où il faut placer les reines sans qu’elles ne s’attaquent.
44
Quand peut-on utiliser le backtracking ?
Uniquement quand on peut définir une solution partielle et tester rapidement si elle peut conduire à une solution complète.
45
Pourquoi le backtracking est-il plus efficace qu’une approche brute-force ?
Parce qu’il élimine de nombreuses solutions candidates avec un seul test dès que l’ajout d’un candidat brise la solution partielle (il abandonne la branche et revient en arrière sur ses choix) en évitant d’explorer des branches inutiles.
46
Dans quels types de problèmes le backtracking est-il utile ?
Problèmes de satisfaction de contraintes comme les mots croisés, sudoku, arithmétique verbale, parsing, sac à dos, etc.
En gros, tout problème dont la solution peut être construite par incrémentation de candidats sur des solutions partielles
47
Pourquoi le backtracking est-il qualifié de métaheuristique ?
Parce qu’il dépend de procédures données par l’utilisateur pour définir les solutions partielles et les tests de validité.
48
Le backtracking garantit-il de trouver toutes les solutions ?
Oui, s’il est appliqué correctement à un problème fini, il trouvera toutes les solutions dans un temps borné.
49
Quel langage de programmation a intégré une fonctionnalité de backtracking dès 1962 ?
Le langage SNOBOL
50
Quelle est la stratégie d’exécution utilisée dans les langages comme Icon, Planner, Prolog ?
Le backtracking
51
Qu’est-ce que la méthode Branch & Bound ?
C’est une méthode d’optimisation qui explore un arbre de recherche tout en élaguant les branches qui ne peuvent pas mener à une solution optimale.
52
Quelle est la différence principale entre Backtracking et Branch & Bound ?
Branch & Bound utilise des bornes pour éliminer des branches, alors que le backtracking élimine seulement celles qui sont invalides.
53
Qu'est-ce qu’une borne inférieure dans Branch & Bound ?
C’est une estimation minimale du coût que pourrait avoir une solution en explorant une branche donnée.
54
Quand élaguer une branche dans Branch & Bound ?
Quand la borne inférieure d’une solution partielle est supérieure au coût de la meilleure solution connue.
55
Donne un exemple de problème classique résolu par Branch & Bound.
Le problème du sac à dos ou le problème d’assignation.
56
Branch & Bound garantit-il une solution optimale ?
Oui, si les bornes sont correctement calculées, il explore toutes les solutions possibles de façon optimisée.
57
Quelle structure est utilisée pour explorer les branches dans Branch & Bound ?
Souvent une file de priorité ou une pile, selon la stratégie choisie (best-first ou depth-first).
58
Que signifie « élagage » dans Branch & Bound ?
Cela signifie ne pas explorer une branche de l’arbre de recherche car elle est sous-optimale.
59
Quel est le lien entre Branch & Bound et la programmation dynamique ?
Les deux utilisent des sous-problèmes, mais Branch & Bound explore un arbre tandis que la programmation dynamique stocke toutes les solutions intermédiaires.
60
Branch & Bound est-il une approche exacte ou heuristique ?
C’est une approche exacte (contrairement à la plupart des métaheuristiques).
61
Que fait l’algorithme Branch and Bound pour résoudre un problème d’optimisation ?
Il divise le problème en sous-problèmes et utilise une fonction de borne pour éliminer ceux qui ne peuvent pas contenir la solution optimale.
62
Dans quel type de problèmes Branch and Bound est-il le plus utilisé ?
Les problèmes d’optimisation combinatoire et les problèmes NP-difficiles.
63
Quelle structure logique l’arbre de recherche de B&B représente-t-il ?
Un arbre enraciné où chaque branche correspond à un sous-ensemble de solutions candidates.
64
Quand une branche de l’arbre est-elle élaguée dans Branch and Bound ?
Lorsqu’une borne inférieure ou supérieure montre que cette branche ne peut pas produire une meilleure solution que celle déjà trouvée.
65
Pourquoi l’estimation des bornes est-elle cruciale en Branch and Bound ?
Parce que de bonnes bornes permettent d’éliminer rapidement les branches inutiles, accélérant la recherche de l’optimal.
66
Que se passe-t-il si les bornes sont mal estimées ou absentes dans Branch and Bound ?
L’algorithme devient une recherche exhaustive (brute-force).
67
Quelle est l’utilité de la borne supérieure dans Branch and Bound ?
Elle donne une estimation du meilleur coût qu’on peut espérer d’une branche, utilisée pour comparer et décider d’élaguer.
68
Pourquoi Branch and Bound est-il considéré comme une méthode systématique ?
Car il énumère les solutions candidates en explorant un espace d’états structuré (arbre), tout en appliquant des bornes pour optimiser.
69
Branch & Bound combine des idées de quels deux paradigmes classiques d’algorithmique ?
Divide & Impera ;; Programmation Dynamique
70
Comme Divide & Impera, Branch & Bound fait quoi ?
Il divise l’espace des solutions en sous-problèmes (branches de l’arbre de recherche).
71
Comme la Programmation Dynamique, Branch & Bound vise quoi ?
À résoudre un problème d’optimisation en trouvant une solution optimale parmi plusieurs choix possibles.
72
Quelle est la différence entre Branch & Bound et la Programmation Dynamique dans la gestion des sous-problèmes ?
Branch & Bound explore tous les cas sauf ceux éliminés par borne ; la prog. dynamique évite les recalculs grâce à la mémoïsation.
73
Quelle est la différence entre Divide & Impera et Branch & Bound ?
Divide & Impera fusionne les résultats de sous-problèmes, Branch & Bound explore un arbre et élaguent les branches inutiles.
74
Branch & Bound utilise-t-il une table de mémoïsation comme la programmation dynamique ?
Non, il n'enregistre pas les résultats des sous-problèmes déjà résolus, il se base sur des bornes pour élaguer.
75
Quel est le point commun entre les trois : Divide & Impera, Prog. Dynamique et Branch & Bound ?
Ils décomposent un problème en sous-problèmes mais utilisent des stratégies différentes pour explorer ou optimiser.
76
Que signifie « élaguer une branche » dans Branch and Bound ?
Ne pas explorer un sous-arbre de l’espace de recherche parce qu’il ne peut pas mener à une solution meilleure que la meilleure connue.
77
Pourquoi élaguer est-il essentiel dans Branch and Bound ?
Cela permet de réduire l’espace de recherche et d’éviter d’explorer inutilement des solutions sous-optimales.
78
Dans quel cas peut-on élaguer une branche dans Branch and Bound ?
Quand sa borne inférieure est plus grande que le coût de la meilleure solution actuelle.
79
Quel est le lien entre élagage et performance de B&B ?
Plus on peut élaguer de branches tôt, plus l’algorithme est rapide et efficace.
80
Peut-on toujours élaguer dans Branch and Bound ?
Non, seulement si on a des bornes efficaces pour estimer la qualité d’une branche.
81
Pourquoi le branch and bound est plus efficace que le backtracking?
Parce que Branch and Bound ne se contente pas de rejeter les solutions invalides comme le backtracking,
il élimine aussi intelligemment les solutions valides mais sous-optimales grâce aux bornes.
82
Comment calcule-t-on une borne inférieure dans Branch and Bound ?
On estime le coût minimal possible d’une solution complète à partir d’un état partiel, en supposant les choix les plus favorables pour compléter.
83
À quoi sert une bonne borne inférieure dans Branch and Bound ?
À éliminer rapidement les branches non prometteuses de l’arbre de recherche (élagage efficace).
84
Vrai ou Faux : Une borne inférieure permet de prouver qu’un sous-problème est sous-optimal.
Vrai
85
Complète : Une borne inférieure est une estimation du ________ que peut valoir une solution à partir d’un état partiel.
meilleur coût possible
86
Donne un exemple de borne inférieure dans le problème du sac à dos.
On complète la capacité restante avec les objets ayant le meilleur rapport valeur/poids, même partiellement.
87
Pourquoi une mauvaise borne inférieure nuit-elle à l’efficacité de Branch and Bound ?
Parce qu’elle empêche d’élaguer efficacement et force à explorer trop de branches inutiles.
88
Dans un problème de sac à dos, comment calcule-t-on une borne supérieure à un nœud ?
On complète la capacité restante avec les objets restants triés par valeur/poids, même partiellement, pour estimer la valeur maximale possible.
89
Que représente un nœud dans l’arbre de recherche de Branch & Bound ?
Une solution partielle à un problème, par exemple une sélection partielle d’objets dans un sac à dos.
90
Quand peut-on élaguer une branche dans un arbre B&B ?
Quand sa borne est pire que la meilleure solution connue (elle ne peut pas contenir l’optimal).
91
Quelles sont les informations qu’on doit tenir à jour dans un algorithme Branch and Bound ?
La meilleure solution courante, les bornes pour chaque nœud, la structure d’exploration (pile/file).
92
Dans un exercice type de B&B, que dois-tu faire pour chaque nœud de l’arbre ?
Calculer la borne, décider s’il faut élaguer, explorer les sous-problèmes s’il reste prometteur.
93
Comment représenter les états dans un problème B&B ?
Sous forme de solutions partielles, ex : objets sélectionnés + capacité restante + valeur actuelle.
94
Pourquoi trie-t-on les objets par valeur/poids dans le sac à dos pour calculer une borne ?
Parce que cela maximise la valeur ajoutée à la borne si on complète partiellement la solution.
95
Quel est le rôle principal de la borne dans B&B ?
Permet d’éliminer des sous-problèmes qui ne peuvent pas battre la meilleure solution actuelle.
96
Quelle est la stratégie typique d’exploration utilisée dans Branch & Bound ?
DFS (parcours en profondeur), parfois best-first avec file de priorité.
97
Que faut-il faire dès qu’on trouve une solution complète meilleure que celle enregistrée ?
Mettre à jour la meilleure solution connue pour améliorer les futurs élagages.
98
Quand est-ce que Branch and Bound devient inefficace ?
Quand il ne peut pas élaguer beaucoup de branches, donc explore presque tout l’arbre.
99
Pourquoi de mauvaises bornes rendent B&B inefficace ?
Parce qu’elles n’éliminent pas assez de branches, et l’algorithme dégénère en brute-force.
100
Pourquoi Branch and Bound est lent quand les valeurs des solutions sont proches ?
Parce qu’il doit explorer presque toutes les branches pour être sûr d’avoir la meilleure solution.
101
Pourquoi B&B peut être inefficace pour des petits problèmes ?
Car le coût du calcul des bornes peut dépasser le gain d’élagage ; un algorithme plus simple suffit.
102
Quel est le danger d’une mauvaise stratégie d’exploration dans B&B ?
On trouve tard une bonne solution, donc on élague peu au début, et on explore trop de branches.
103
Vrai ou Faux : Branch and Bound fonctionne toujours mieux que backtracking.
Faux. Il peut être moins efficace si les bornes sont inutiles ou coûteuses à calculer.
104
Complète : B&B devient une recherche exhaustive quand il ne peut pas ________ efficacement.
élaguer
105
Dans quel cas B&B ne fonctionne **pas du tout** ou est inutile ?
Quand il n’existe pas de borne pour évaluer les sous-problèmes, ou si le problème ne peut pas être décomposé efficacement.
106
Pourquoi B&B ne fonctionne pas pour des problèmes sans fonction d'évaluation partielle ?
Car il ne peut pas calculer de borne pour estimer la qualité d’un sous-problème.
107
Donne un exemple de situation où backtracking simple est préférable à B&B.
Quand les contraintes sont simples et peu de solutions sont valides — le coût des bornes n'est pas justifié.
108
Qu’est-ce qu’un graphe implicite ?
C’est un graphe dont la structure (nœuds et arêtes) est décrite mais pas complètement construite en mémoire. Seules les parties nécessaires sont générées dynamiquement.
109
En quoi le graphe implicite est utile dans les algorithmes de recherche de solution ?
Il permet d’éviter de stocker tout l’espace de recherche en mémoire et de ne générer que les chemins pertinents selon la méthode (retour en arrière, B&B, etc.).
110
Quelle est l’idée générale du retour en arrière ?
Explorer les solutions de manière récursive et revenir en arrière si on détecte une impasse ou si on veut tester une autre possibilité.
111
Quelle structure de parcours est utilisée dans le retour en arrière ?
Un parcours en profondeur (DFS).
112
Donne un pseudo-code générique pour le retour en arrière sur le sac à dos avec objets retournés.
SacADosRetourArr2(objet, poids) : valeur_max ← 0, objets_max ← {}; pour i ← objet à n : si w[i] ≤ poids : (val_cour, obj_cour) ← récursion; val_cour ← val_cour + v[i]; obj_cour ← obj_cour + {i}; si val_cour > valeur_max : valeur_max ← val_cour, objets_max ← obj_cour; retourner (valeur_max, objets_max)
113
Dans quel cas cette approche devient inefficace ?
Lorsque l’espace de recherche est très grand et qu’il n’y a pas de mécanisme de coupure : on teste alors toutes les combinaisons possibles.
114
Quel est le gain entre les approches naïves et intelligentes pour les 8 reines ?
Naïf: C(64,8) ≈ 4.4G combinaisons; 1 reine/ligne: 88 ≈ 16.8M; 1 reine/ligne+colonne (permutations): 8! = 40320; Retour en arrière: ≈ 2057 solutions testées.
115
Formule du calcul de la borne pour problème du sac à dos version 0-n?
pour un noeud quelconque arrivé à l'objet k, sa borne est:
Σ_i=1 à k xi.vi + (W - Σ_i=1 à k xi.wi)*v)k+1/w_k+1
