浸透度の計算方法の例が必要です状態空間ヒューリスティック検索における探索木の分岐係数。定義は次のとおりです。 浸透度 $ P $は、
$ \ qquad \ displaystyle P = \ frac {L} {T} $
および分岐係数によって定義されます。 $ B $は次のように定義されます
$ \ qquad \ displaystyle \ frac {B} {（B-1）} \ cdot（B ^ L – 1）= T $
ここで、$ L $はルートからソリューションまでのパスの長さであり、$ T $は展開されたノードの総数です。
回答
次の検索ツリーを検討してください。ヒューリスティック検索アルゴリズムは、ルートノードから検索を開始します。展開されていないノードは灰色でマークされます。
何らかの理由で、ヒューリスティックは左端のサブツリーに向かって誘導されています。実際には、ゴールノードが右端のサブツリーにあり、緑色でマークされている場合。
展開されたものは赤でマークされます。魅力的な左端のサブツリーが行き止まりであることが判明した後、ヒューリスティックは幸運にもゴールに直接導かれています。前の図の状況から、「目標に到達する前に、合計3つの新しいノードを拡張します。
上の図から、ゴールまでのパスの長さは$ 3 $です。$ 17 $の拡張ノードがあります。したがって、浸透度は$ 3/17 \約0.43 $です。
分岐係数は最大数ですたとえば、各ノードには最大2つの子があるため、バイナリツリーの分岐係数は$ 2 $です。同様に、上記の検索ツリーでは、分岐係数は$ 3 $です。
内容興味があるように見えるのは分岐係数ではなく、効果的な分岐係数 $ B ^ * $です。ヒューリスティックの品質を特徴づけるため。展開されたノードの総数が$ T $で、ゴールへのパスの長さが$ L $の場合（これはより一般的に知られています。 ■ depth ）の場合、$ B ^ * $は、$ T + 1 $ノードを含むために深さ$ L $の均一なツリーが持つ分岐係数です。したがって、
$$ T + 1 = 1 + B ^ * +（B ^ *）^ 2 + \ cdots +（B ^ *）^ L。$$
If検索で取得した値、つまり$ T = 17 $と$ L = 3 $をプラグインすると、$ B ^ * \ upperx 2.165 $が得られます。これは、方程式を使用して得られる値とまったく同じです。
有効な分岐係数はインスタンス間で異なる可能性がありますが、十分に難しい問題の場合はある程度一定です。適切に設計されたヒューリスティックの値は$ Bになります。 ^ * $は$ 1 $に近いため、かなり大きな問題を合理的に安価に解決できます。
コメント
- $ B $の式を解くと、 $ B \ upperx 2.165 $を取得します。その値の解釈は何でしょうか。'はすべての内部ノードの平均分岐係数に近いですが、同じではありません。
- @MAcad実際、関心があるのは分岐係数ではなく、ヒューリスティックの品質を特徴付ける効果的な分岐係数です。I'回答を更新します。
- @Juho分岐係数の式を使用する場合、LHSで多くの数値をテストして計算し、次のようにRHSと等しいかどうかを確認します。 B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4はT = 17と等しくないため、B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15をテストする必要があります。結果はTに近いので、結果Tに到達するまでB = 2.1などをテストできます!!!!この式は次のように使用できると思います：））））