次のような問題が出たのですが、解けなくて困っています。

「ゲーム木の深さ(根から葉までの最大距離)がh、葉以外の状態の子の数が常に2個であるとしたとき、ゲーム木の状態数とhにはどのような関係がありますか。子の数が葉を除いて常にb個であるとしたらどうでしょう。」

どなたか助けてください。
また、このような問題を解くのには、どのような本を参考にしたらよいのでしょうか?教えてください。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

題意をもう少し正確な文章で表すとどうなるんでしょう?


・ここで問題にしているゲームの木は、木である。
   ノードは葉でないか、葉である。
   根(root)であるノードが1個だけある。根であるノードは葉でない。
・葉でないノードに、もし葉でないノードがぶら下がっているならば、ぶら下がっている葉でないノードの数は必ず2である。
こういう意味?

すると、
●葉でないノードが根を除いて偶数個あるのは間違いありません。根を含めると必ず奇数個です。
●深さhのとき、葉でないノードの数の最小値と最大値は幾らになるか。
 根を含めて、最小は2h+1、最大は1+2+4+.....+2^(h-1) = (2^h)-1
です。

さらに、葉でも根でもないノードの数がb個であるという制限を付けると、
●bが奇数の場合:そういうことは起こりません。
●bが偶数の場合:2h≦b≦(2^h)-2 以外の場合は生じ得ない、という以上のことは特に何も言えませんね。

ゲームの木だからゲーム理論、というのは必ずしも当たらない。ゲームの木は多くの場合、完全情報ゲームを想定していて、ゲーム理論とはちょっと条件が違います。むしろグラフ理論と探索(search)の理論が該当するでしょう。後者は特に古典的人工知能において主題だった問題です。
    • good
    • 0

状態数が何を表すのか判りません。

葉の数、ノード数は次の通りです。
葉の数=b^h
ノード数=(b^(h+1)-1)/(b-1)
2分木の時はbに2を入れて下さい。

ゲーム木というのは囲碁、将棋、チェスなどの2人ゲームの戦略決定に使うのですね。そうだとすると2分木の探索法は参考になるとしても、戦略面では、2分木のアルゴリズムよりも、むしろ、「ゲームの理論」の方が参考になるでしょう。ミニマックス法などがそれです。ただゲームの理論だけではおそらく不足でしょう。
実際には多分木を扱うことになるのでしょうね。
上の式を導くだけなら数学の等比級数の和の公式だけで充分でしょう。

回答は式の計算と図解(深さ2の2分木とb分木)をしてご確認下さい。
ゲーム木については下記URLを参考にしました。

参考URL:http://www.csci.yamanashi.ac.jp/~suzu/file.html
    • good
    • 0

プログラミング系の書籍でアルゴリズムについて書いてある本(例えば「C言語とアルゴリズム」みたいな)で「二分木」の項をみれば参考になると思います。

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング