- ベストアンサー
ゲーム木探索について教えてください。
ymmasayanの回答
- ymmasayan
- ベストアンサー率30% (2593/8599)
状態数が何を表すのか判りません。葉の数、ノード数は次の通りです。 葉の数＝ｂ＾ｈ ノード数＝（ｂ＾（ｈ＋１）－１）／（ｂ－１） ２分木の時はｂに２を入れて下さい。 ゲーム木というのは囲碁、将棋、チェスなどの２人ゲームの戦略決定に使うのですね。そうだとすると２分木の探索法は参考になるとしても、戦略面では、２分木のアルゴリズムよりも、むしろ、「ゲームの理論」の方が参考になるでしょう。ミニマックス法などがそれです。ただゲームの理論だけではおそらく不足でしょう。 実際には多分木を扱うことになるのでしょうね。 上の式を導くだけなら数学の等比級数の和の公式だけで充分でしょう。 回答は式の計算と図解（深さ２の２分木とｂ分木）をしてご確認下さい。 ゲーム木については下記ＵＲＬを参考にしました。
関連するQ&A
- 探索木の問題について
探索木について。 探索木において、探索効率を高めるため（探索経路を短くするため）、子の数を最大ｍ個までとするｍ分探索木を考える。この木の探索についての計算量は、どのように考えれば良いですか。 説明してください。 という問題なのですが 画像のA,Bのタイプのどちらで考えればいいのかわかりません そこで、どちらのタイプで考えればいいのか あわよくば、問題についても答えを教えてください よろしくおねがいします
- 締切済み
- 情報工学
- 幸福の木の根元がぐらぐらして…
幸福の木の根元がぐらぐらしてきました。 どうも土が痩せて少なくなってしまったように見えます。 根自体はまだ硬く，いちおう土に張った状態で，引っこ抜けるわではありません。 枝からは，少ないですが葉が茂ってます。 各種園芸サイトを見た結果， ・挿木ができるそうなので，今生きている枝を切って，やってみるか， ・それとも今の根を生かして，土を新しくして植え替えようか と考えています。 いずれがよいと思われますか？ また，どちらにしても，冬なので，無事に新しい根が張るでしょうか？ 春まで待つべきでしょうか？ （東京都内で室内で育てています） 今の状態のまま，根がぐらぐら…というのも，どうしたものかと悩んでます。 かわいそうな幸福の木…それでも葉を繁らせているのが，けなげです。 園芸初心者ですので，皆さんのアドバイスをお聞かせ下さい！
- ベストアンサー
- その他（趣味・娯楽・エンターテイメント）
- アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 二分木の高さについて
二分木の高さについて このカテゴリでいいのか迷ったのですが。。。 １）、葉を含めて節点の総数がNであるような二分木の高さの範囲、というのはどういったのものなのでしょうか？ また逆に２）、高さｈの二分木のもつ要素の最大と最小はいくつなのでしょうか？ 導き方も含めてお答えいただけると助かります。 ちなみに１）の自分の答えは完全二分木のときはlogn、最悪にバランスが取れていない時がnです。
- ベストアンサー
- C・C++・C#
- 幸福の木 挿し木後の手入れ
幸福の木が大きくなったので、横から伸びた茎を切り、水に入れて数ヶ月が経ちました。かなり根が出てきているのですが、その後どう手入れしたらよいか分かりません。土に植え替えたあと、葉はどう処理すればいいのでしょうか？今、葉は細く、しかも長く伸びており、かなり不格好な状態です・・・。
- 締切済み
- 園芸・ガーデニング・観葉植物
- Ｂ木とＲ木の違いを教えて下さい
当方、今年情報系の学科に入学しました大学1回生です。 大学のレポートで 問：Ｂ木とＲ木のキー、及び探索方法の違いを調べよ。 という問題が出題されたのですが Ｒ木というものに関する資料が少なくて困っています。 今、自分で調べた結果 探索方法に関しては ・Ｂ木 根から始めて探索キーの値とノードのキーを比較しながら 部分木をたどっていく。 葉に到達したときのに葉のキーの値と探索キーが等しければ成功、 等しくなければ失敗。 ・Ｒ木 点質問で探索キー（？）を含むMBRを探索 範囲質問 というのが違いかなと思うのですが、上手く1つの文章で表現できません。 （Ｒ木の探索方法についてはイマイチ理解できない） またキーに関する違いと言うのもイマイチよく分かりません。 違いを教えていただけると嬉しいです。 また、どなたかＲ木に関する詳しい解説のあるＨＰか書籍をご存知ではないでしょうか？ 宜しく御願い致します。
- 締切済み
- その他([技術者向] コンピューター)
- 二分探索木のパターン数
二分探索木のパターン数 二分探索木とは、上の値より大きければ右に、小さければ左に子を作っていくツリー状のものです。 例えば 6 ／ ＼ 4 9 ／＼ ／ 2 5 8 ／ 7 こんな感じです。 http://ja.wikipedia.org/wiki/%e4%ba%8c%e5%88%86%e6%9c%a8 で、問題なのですが、[1,2,3,4,5,6,7,8,9]といった9つの数値がある時、二分探索木は何通りできるか。 というものです。図を書いて色々考えてみたのですが求め方が分かりません。 全パターン書き出すのは量的に辛すぎますし、CやPで計算するのでしょうが、どのような式になるのでしょうか？
- ベストアンサー
- 数学・算数
- 木や雑草を食べられる生物の秘密
木や雑草を食べられる生物の秘密というのはいったいどこにあるのでしょうか？ つまり、人間では食べられない植物を食べられる生物の秘密を聞きたいです。 戦争中などであれば、そういったものを食べた人たちが居ると思いますが、食べて問題はなかったのでしょうか？ また、茎、根、葉のうち人間でも食べられるのはどこでしょうか？
- ベストアンサー
- 生物学
- コーヒーの木の根腐れ 処置
昨年もらったコーヒーの木を２本育てています。 いまいち成長がよろしくありません。 宜しくないと言うよりも、葉の先が茶色に変色しているので、ここで検索したら、どうやら『根腐れ』らしいのです。 あわてて、ＵＣＣコーヒー館のすくすく編集部のＨＰ参考にして、培養土を配合して植え替えを行いました。 根の状態は、葉の少ないほうが赤茶色で、根腐れしてるかも。 葉の多いほうはかろうじて薄い赤茶色で、まだ復活するかも。 の状態です。ここから、復活させる方法をご存知の方、アドバイスお願いします。 べつのＨＰには植え替え後剪定が必要とありましたが、剪定は必要でしょうか？茶色い葉だけ落とすのでしょうか？でも、その場合、葉がなくなるような気がしますので、この場合剪定しないほうがいいのでしょうか？ すいません！どなたか教えて下さい。 よろしくお願いします。
- ベストアンサー
- 園芸・ガーデニング・観葉植物