Jai besoin dun exemple pour calculer la pénétrance et le facteur de ramification de larbre de recherche dans une recherche heuristique dans lespace détats. Les définitions sont les suivantes. Penetrance $ P $ est défini par
$ \ qquad \ displaystyle P = \ frac {L} {T} $
et facteur de branchement $ B $ est défini par
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
où $ L $ est la longueur du chemin de la racine à la solution et $ T $ le nombre total de nœuds développés.
Réponse
Considérez larbre de recherche suivant. Votre algorithme de recherche heuristique démarre la recherche au niveau du nœud racine. Les nœuds non développés sont marqués en gris.
Pour une raison quelconque, lheuristique est guidée vers le sous-arbre le plus à gauche, alors quen fait le nœud de but est dans le sous-arbre le plus à droite, marqué en vert.
Les nœuds qui ont été développés sont marqués en rouge. Après que le sous-arbre attrayant le plus à gauche se soit avéré être une impasse, lheuristique est maintenant heureusement guidée directement vers lobjectif. À partir de la situation de la figure précédente, nous « allons développer un total de trois nouveaux nœuds avant darriver à lobjectif.
Daprès la figure ci-dessus, la longueur du chemin vers lobjectif est de 3 $. Il y a des nœuds étendus à 17 $. Par conséquent, pénétrance vaut 3/17 $ \ environ 0,43 $.
Le facteur de branchement est le nombre maximum des successeurs de nimporte quel nœud. Par exemple, le facteur de branchement dun arbre binaire est de 2 $ puisque chaque nœud a au plus deux enfants. De même, dans larbre de recherche ci-dessus, le facteur de branchement est de 3 $.
Quest-ce qui semble vous intéresser nest pas le facteur de branchement, mais le facteur de branchement effectif $ B ^ * $ qui est un moyen pour caractériser la qualité dune heuristique. Si le nombre total de nœuds développés est $ T $, et la longueur du chemin vers lobjectif est $ L $ (cest plus communément appelé s profondeur ), alors $ B ^ * $ est le facteur de branchement quun arbre uniforme de profondeur $ L $ aurait pour contenir des nœuds $ T + 1 $. Par conséquent,
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $$
Si vous branchez les valeurs que nous avons obtenues lors de la recherche, cest-à-dire $ T = 17 $ et $ L = 3 $, vous obtenez $ B ^ * \ environ 2,165 $. Cest exactement la même valeur que vous obtenez en utilisant votre équation; cest simplement une représentation différente pour la même chose.
Le facteur de branchement effectif peut varier dune instance à lautre, mais est quelque peu constant pour les problèmes assez difficiles. Une heuristique bien conçue aurait une valeur de $ B ^ * $ proche de $ 1 $, permettant de résoudre des problèmes assez importants à un prix raisonnable.
Commentaires
- En résolvant la formule pour $ B $, vous get $ B \ approx 2.165 $. Je me demande quelle est linterprétation de cette valeur. Elle ' est proche du facteur de branchement moyen de tous les nœuds internes, mais pas la même.
- @MAcad En fait, ce qui vous intéresse, ce n’est pas le facteur de branchement, mais le facteur de branchement efficace qui est loin de caractériser la qualité d’une heuristique. I ' Je mettrai à jour ma réponse.
- @Juho Je pense que si jutilise la formule du facteur de branchement, je vais tester de nombreux nombres dans le LHS et le calculer et vérifier légalité avec RHS comme suit: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 différent de T = 17, nous devons donc tester B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 le résultat proche de T afin que nous puissions tester B = 2,1 et ainsi de suite jusquà atteindre le résultat T !!!! Je pense que cette formule peut utiliser comme ça :))))