B*
は、グラフ検索アルゴリズムについてです。Bツリーのバリアントについては
、B *ツリーを参照してください
でコンピュータサイエンス、B *（発音「Bスター」）である最良優先 グラフ探索アルゴリズム与えられた初期からの最小コストパス見つかったノードをいずれかに目標ノード（一の以上の可能な目標のうち）。1979年にHansBerlinerによって最初に発行され、A *検索アルゴリズムに関連しています。
コンテンツ
1 概要
2 詳細
2.1 推定ではなく間隔評価 2.2 バックアッププロセス 2.3 検索の終了 2.4 拡張
2.4.1 戦略の選択
2.4.2 非ルートノードでの戦略の選択
2.5 堅牢性 2.62.6 2人用ゲームの拡張 2.7 アプリケーション
3 も参照してください
4 参考文献
概要
アルゴリズムは、単一の点値推定ではなく、ツリーのノードの間隔を格納します。次に、ツリーのリーフノードを、最上位ノードの1つが明らかに「最良」の間隔になるまで検索できます。
詳細
推定ではなく間隔評価
B *ツリーのリーフノードには、単一の数値ではなく間隔である評価が与えられます。間隔には、そのノードの真の値が含まれているはずです。リーフノードに接続されたすべての間隔がこのプロパティを満たす場合、B *は目標状態への最適なパスを識別します。
バックアッププロセス
ツリー内の間隔をバックアップするために、親の上限は子の上限の最大値に設定されます。親の下限は、子の下限の最大値に設定されます。異なる子がこれらの境界を提供する可能性があることに注意して
検索の終了
B *は、「分離」を作成するためにノードを体系的に拡張します。これは、ルートの直接の子の下限が、ルートの他の直接の子の上限と少なくとも同じ大きさである場合に発生します。根元で分離を作成するツリーには、最高の子が少なくとも他の子と同じくらい良いという証拠が含まれています。
実際には、複雑な検索は実際のリソース制限内で終了しない場合がしたがって、アルゴリズムは通常、時間やメモリ制限などの人為的な終了基準で拡張されます。人工的な制限に達した場合、どの移動を選択するかについてヒューリスティックな判断を行う必要が通常、ツリーは、ルートノードの間隔などの広範な証拠を提供します。
拡張
B *はベストファーストのプロセスです。つまり、ツリーをトラバースし、繰り返し下降して拡張するリーフを見つけることが非常に効率的です。このセクションでは、展開するノードを選択する方法について説明します。（注：ツリーがメモリに常駐しているかどうかは、実メモリまたは仮想メモリを介してツリーをマッピングおよび/または管理する方法を含む、全体的な実装効率の関数です。）
ツリーのルートで、アルゴリズムは、prove-bestとdisprove-restと呼ばれる2つの戦略のいずれかを適用します。最良の証明戦略では、アルゴリズムは上限に関連付けられたノードを選択します。そのノードを拡張すると、その下限が他のノードの上限よりも高くなることが期待されます。
disprove-rest戦略は、2番目に高い上限を持つルートの子を選択します。そのノードを拡張することで、最高の子の上限を下限よりも小さくできる可能性が
戦略の選択
最高の上限を持つ子ノードの下限がすべての下限の中で最高になるまで、disprove-rest戦略を適用することは無意味であることに注意して
元のアルゴリズムの説明では、どの戦略を選択するかについてのガイダンスは提供されていませんでした。小さいツリーを持つ選択肢を拡張するなど、いくつかの合理的な選択肢が
非ルートノードでの戦略の選択
ルートの子が選択されると（prove-bestまたはdisprove-restを使用）、アルゴリズムは、上限が最も高い子を繰り返し選択することにより、リーフノードに下降します。
リーフノードに到達すると、アルゴリズムはすべての後続ノードを生成し、評価関数を使用してそれらに間隔を割り当てます。次に、バックアップ操作を使用して、すべてのノードの間隔をバックアップする必要が
転置が可能な場合、バックアップ操作では、選択パス上にないノードの値を変更する必要がある場合がこの場合、変更を伝播できるように、アルゴリズムには子からすべての親へのポインターが必要です。バックアップ操作でノードに関連付けられた間隔が変更されない場合、伝播が停止する可能性があることに注意して
堅牢性
間隔が正しくない場合（ノードのゲーム理論値が間隔内に含まれていないという意味で）、B *は正しいパスを識別できない可能性がただし、アルゴリズムは実際のエラーに対してかなり堅牢です。
Mavenの（スクラブル）プログラムは、評価エラーが可能であるB *のロバスト性を向上させる技術革新を有しています。分離が原因で検索が終了した場合、Mavenは、すべての評価間隔を少し広げた後、検索を再開します。このポリシーはツリーを徐々に広げ、最終的にすべてのエラーを消去します。
2人用ゲームの拡張
B *アルゴリズムは、2人のプレーヤーによる決定論的ゼロサムゲームに適用されます。実際、唯一の変更は、そのノードで移動する側に関して「最良」を解釈することです。したがって、あなたの側が動いている場合は最大値を取り、対戦相手が動いている場合は最小値を取ります。同様に、移動する側の観点からすべての間隔を表し、バックアップ操作中に値を無効にすることができます。
アプリケーション
AndrewPalayはB *をチェスに適用しました。エンドポイントの評価は、null-move検索を実行することによって割り当てられました。同じハードウェアで実行されているアルファベータプルーニング検索エンジンと比較して、このシステムがどれだけうまく機能したかについての報告はありません。
Mavenの（スクラブル）プログラムは、* endgamesに検索をBを適用しました。エンドポイント評価は、ヒューリスティック計画システムを使用して割り当てられました。
B *検索アルゴリズムは、一連の組み合わせゲームの合計ゲームで最適な戦略を計算するために使用されています。
も参照してください
分枝限定法
参考文献
ベルリナー、ハンス（1979）。「B *ツリー検索アルゴリズム。最良の最初の証明手順」。人工知能。12（1）：23–40。土井：10.1016 / 0004-3702（79）90003-1。
ラッセル、SJ; Norvig、P。（2003）人工知能：現代的なアプローチ。ニュージャージー州アッパーサドルリバー：プレンティスホール。NS。188. ISBN 0-13-790395-2。
シェパード、ブライアン（2002）。「世界選手権キャリバースクラブル」。人工知能。134（1–2）：241–275。土井：10.1016 / S0004-3702（01）00166-7。