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

「ゲーム木の深さ(根から葉までの最大距離)が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と関連する良く見られている質問

Q白4個、黒3個中から、無作為に3個同時に取り出す時、2個が白、1個が黒の確率教えてください!

白4個、黒3個中から、無作為に3個同時に取り出す時、2個が白、1個が黒の確率教えてください!

Aベストアンサー

(3C2x3C1)/7C3

Qリンゴ1個とみかん2個を買ったら260円でした。また、リンゴ4個とみかん6個を買ったら920円でした

リンゴ1個とみかん2個を買ったら260円でした。また、リンゴ4個とみかん6個を買ったら920円でした。リンゴとみかんはそれぞれ1個いくらですか。

わかりやすく教えてくださいお願いします!!

Aベストアンサー

リンゴをx円、みかんをy円とすると
 x+2y=260 …①
 4x+6y=920 …②

①を4倍して
 4x+8y=1040

これから②を引くと
 8y-6y=1040-920
 2y=120
 y=60

①に代入すると
 x+60×2=260
 x+120=260
 x=140

リンゴが140円、みかんが60円です。

Q数学の問題です。 1個80円のりんごと1個130円のりんごを合わせて10個と100円の夏みかんを1

数学の問題です。

1個80円のりんごと1個130円のりんごを合わせて10個と100円の夏みかんを1個買ったら1000円であった。80円のりんごは何個買ったか。
解説お願いします。

Aベストアンサー

夏みかんの分を引いてりんごの代金を求めると
 1000-100=900

80円のりんごをx個、130円のりんごをy個買ったとすると
りんごの個数は
 x+y=10 …①

りんごの代金は
 80x+130y=900 …②

この①、②を連立方程式として解きます。
①より
 y=10-x …①’

これを②に代入して
 80x+130(10-x)=900
 80x+1300-130x=900
 400=50x
 x=8

80円のりんごは8個買っています。

Q1から100までの数の中に、2と3の公倍数は16個ですか?

1から100までの数の中に、2と3の公倍数は16個ですか?

Aベストアンサー

はい。
2と3の公倍数は6の倍数で、1から100までの間に6の倍数は
100÷6=16.66…となり、
16個あることがわかります。

Q木によく肥料をほどこすならば、 労せずして確実に結果は実ります。 賢者は木を考えて実をえる、 小人

木によく肥料をほどこすならば、
労せずして確実に結果は実ります。

賢者は木を考えて実をえる、
小人は実を考えて実をえない。

これはどういう意味ですか?

Aベストアンサー

これを読んだ人は存じませんが、

現代風に解釈すると、例えば会社を興す起業。
または長期の株式投資だと思われます。

「お金がお金を生む」「お金に仕事をしてもらう」
という意味だと思われます。

投資をしたお金(木・企業)に
肥料をほどこす(良い情報、良い環境)を与えれば
確実に企業利益は増え続けます。
(また、良い企業には人材も集まります。)
結果、その企業は、一つの会社から10へ、20へ、
そして日本国中へ世界中へ広がっていきます。

いま、パソコンを使っていれば、マイクロソフトのOS、ウインドウズがいい例でしょう。
最初は学生二人が作った小さい箱。それが現在世界中で必要な企業になった。
その企業や「ノウハウ・作品」は全世界で利用、必ず必要とされます。
ーーー
賢者は木を考えて実をえる、
賢いものは木(この場合、企業や投資したお金、5年後10年後の投資した金額の倍以上の価値)を
考えて、実(本当のじつ。「実・み(いっこの実、りんご一個)」ではなく、
企業価値としての実利。実際の利益。実際の利益は増え続けますよね?企業にしろ、
経済が上向きの国の場合、株式投資にしろ。増え続けます。)


小人は実を考えて実をえない。
しょうにん、は、み、をかんがえて、じつをえない
目先の利益に捉われてしまう人は、
目の前に置かれた「りんご1個」のことを考えてしまい、
実じつ=「実際の企業利益や・実際の価値」=を考えない。

と、いう意味だと思われます。

今風のビジネスに置き換えると、
1個100円のりんごを100個一気に売ると、=1万円の儲けです。
ただ、
1個80円にして、一つの洋菓子店に10個販売。それを10店舗作ります。
10店舗と契約を作る為に10週間かかったとします。
ですが、その洋菓子店は、アップルパイ売り続けますよね?
ケーキにも使いますよね?パウンドケーキにも使いますよね?
ほぼ、ずーーーーとリンゴは売れ続けます。

最初は数百円ですが、店舗数と年数を経て莫大な利益につながります。
=ストックビジネスと呼ばれております。
また、フランチャイズ(本部があって、全国で同じ味のレストラン。)も同じだと
思われます。

なんとなく伝われば、いいのですがw

これはどういう意味ですか?

これを読んだ人は存じませんが、

現代風に解釈すると、例えば会社を興す起業。
または長期の株式投資だと思われます。

「お金がお金を生む」「お金に仕事をしてもらう」
という意味だと思われます。

投資をしたお金(木・企業)に
肥料をほどこす(良い情報、良い環境)を与えれば
確実に企業利益は増え続けます。
(また、良い企業には人材も集まります。)
結果、その企業は、一つの会社から10へ、20へ、
そして日本国中へ世界中へ広がっていきます。

いま、パソコンを使っていれば、マイクロソフトのOS...続きを読む


人気Q&Aランキング

おすすめ情報