ログイン新規登録

【重要】NoSchool勉強Q&Aサービス終了のお知らせ

いつもNoSchool勉強Q&Aをご利用いただきありがとうございます。2021年4月30日をもちましてサービスを終了させて頂くこととなりました。サービス終了に伴い今までの質問/回答等の全ての投稿データも運営側で非公開とし、ユーザー様のほうで閲覧/取得が出来ない状態となります。投稿データの保存をご希望の場合はサービス終了期日までに投稿データの保存等をお願いいたします。
詳細はこちら

お使いのブラウザ（Internet Explorer）では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ：Google Chrome（グーグル・クローム）

CLOSE

（1）の場合分けはなんとなく理解しております。しかし、（２）...

■どこまで理解しているか

（1）の場合分けはなんとなく理解しております。しかし、（２）、（３）についてが全くわかっておりません。

■どこが具体的にわからないか

探索木と枝刈りの問題について

2つ質問があります。
①この問題はどういった分野の勉強をすれば解けるようになるでしょうか？
おすすめの参考書などを教えていただけると幸いです。
個人的には、基本情報技術者の参考書なのかな？と思ったりしております。

②(1)~(3)について、具体的な解法を教えていただきたいです。

以上になります。何卒よろしくお願いいたします。

（1）の場合分けはなんとなく理解しております。しかし、（２）...

画像ビューアで開く

（1）の場合分けはなんとなく理解しております。しかし、（２）...

画像ビューアで開く

1年前

あお@polca さんの質問

回答(1件)

ベストアンサーに選ばれました

先生

先生の回答 1年前

スコアと枝刈りは，ゲームなどの戦略を立てるプログラムを作るときのテクニックの1つです．

基本的にゲームのプログラムなどはこの方法で作られています．

スコアとは勝利条件（ここではパズルの完成形）の達成しやすさで，ゲームで言えば有利不利を数値化したものです．基本的には，スコアを高くするようにゲームを進める（パズルを解く）ことになります．

1つのゲームにおいてもスコアの決め方には無数の多様な方法がありますが，厄介なことは，大抵のゲームでは，どんなスコアの決め方をしたとしても，1ステップ動かしたときにスコアを最大にする動かし方を続けても必ずしも勝利に結びつかない，という性質があります．

そのため，何ステップか動かす場合を全探索して，その中でスコアが最大になるような動かし方を選ぶのが良い戦略になります．ただし，全探索が可能なステップ数には限界があります．そのため最初のnステップで全探索を打ち止める必要があり，このことを枝刈りと言います．

さて，このパズルにスコアをどうやって決めるかですが，完成形が最大か最小のスコアを達成しているようにしなければならないので，

例えば，「隣り合う数字との差のすべてのマスについての和」をスコアにしてみるのはどうでしょうか？（これでうまくいくかはわからないです）

このスコアではスコアが小さいときが完成形に近いということです．

このスコアを決めて，後は3～5ステップくらいを全探索させて，その中からスコア最小の形を選ばせ，そこまで動かします．まだ完成していなかったら，今度はそこから同じことを繰り返します．

恐らくこれで完成できるのではないでしょうか．

こういったテクニックは普通のプログラミングの本には書いてない場合もあると思います．私は機械学習の文脈でこのテクニックを知りました．

プログラミングの専門書というよりも，機械学習の専門書を読むのが良いと思います．

ログインしてコメントする

回答へコメントする

＞

情報処理の質問

＞

（1）の場合分けはなんとなく理...