問題タブ [tree-search]

検索が成功した場合、二分木を使用した n 個のキーを含むすべての入力に対する平均検索時間は Big O (lg n) であることがわかっていますが、この結果は失敗した研究にも当てはまりますか?

私はこのように構成されたツリーn-aryを持っています:

アイテムを検索するにはどうすればよいですか? この機能を実装しましたが、機能しません... ありがとうございます。

Hex のゲームのモンテカルロ ツリー検索に基づいて単純な 16 進プレーヤーを開発しました。ここで、RAVE (Rapid Action Value Estimation) と LGP (Last Good Reply) を使用して hex プレーヤーを拡張したいと考えています。記事はこことここにあります。
ツリー検索のパフォーマンスを改善するためにこれらの方法のいずれかを使用し、それを理解するのに役立つ人がここにいるかどうか疑問に思っていましたか?
また、なぜこれらのアルゴリズムが AMAF (All Moves As First) ヒューリスティックと呼ばれているのか知りたいですか?

pとの2 つのノードが与えられqた場合、どのようにして最も低い共通の祖先を見つけますか? (両方とも非常に大きなツリーに属していると仮定します)

ツリーのルートへの参照がありません。

これを行う最も効率的な方法は何ですか? これまでのところ、私が持っている唯一のアイデアは

(1) ノード p を選択します (どちらでも構いません)

(2) p の左部分木を検索し、q がある場合は p を返す

(3) そうでなければ、p の右側の部分木を検索し、q がある場合は p を返す

(4) そうでない場合は、1 レベル親に移動し、p を含まないサブツリーを検索します。q が見つかった場合は、親を返します。

(5) そうでない場合は、もう一度 1 レベル上に移動し、(4) を繰り返します (この親を含まないサブツリーを検索します)

これは非常に非効率に思えます。より良いアルゴリズムはありますか？