この質問を stackoverflow と cs.stackexchange.com のどちらに投稿すべきかわかりません。移動する必要があるかどうかお知らせください。
モンテカルロ木探索 (MCTS) の時間計算量を見つけようとしています。グーグルは助けにならないので、私は自分でどこまで計算できるかを見ようとしています.
n反復のために、または時間がなくなる前に、4 つのステップを実行します。だから私たちは持っています
O(n*(選択+拡張+シミュレーション+逆伝播))
展開は、現在選択されているノードに子を追加するだけです。単一リンクリストなどを使用してツリーの子を格納していないと仮定すると、これは一定の時間で発生する可能性があるため、除外できます。
O(n*(選択+シミュレーション+逆伝播))
分岐係数bとtツリー内のノードの総数を考えると、ツリーの深さが log b t であるため、選択フェーズは O(b*log b t) で実行されると想定しています。以上の子供たち。
したがって、時間の複雑さは次のようになります
O(n*(b*log b t+シミュレーション+逆伝播))
バックプロパゲーションには、ツリーの深さに比例する時間もかかるため、次のようになります。
O(n*(b*log b t+シミュレーション+b*log b t))
しかし、これにシミュレーションフェーズを追加する方法がわかりません。