質問: (1)の場合分けはなんとなく理解しております。しかし、(2)... ■どこまで理解しているか (1)の場合分けはなんとなく理解しております。しかし、(2)、(3)についてが全くわかっておりません。 ■どこが具体的にわからないか 探索木と枝刈りの問題について 2つ質問があります。 1この問題はどういった分野の勉強をすれば解けるようになるでしょうか? おすすめの参考書などを教えていただけると幸いです。 個人的には、基本情報技術者の参考書なのかな?と思ったりしております。 2(1)~(3)について、具体的な解法を教えていただきたいです。 以上になります。何卒よろしくお願いいたします。
回答: スコアと枝刈りは,ゲームなどの戦略を立てるプログラムを作るときのテクニックの1つです.基本的にゲームのプログラムなどはこの方法で作られています. スコアとは勝利条件(ここではパズルの完成形)の達成しやすさで,ゲームで言えば有利不利を数値化したものです.基本的には,スコアを高くするようにゲームを進める(パズルを解く)ことになります.1つのゲームにおいてもスコアの決め方には無数の多様な方法がありますが,厄介なことは,大抵のゲームでは,どんなスコアの決め方をしたとしても,1ステップ動かしたときにスコアを最大にする動かし方を続けても必ずしも勝利に結びつかない,という性質があります.そのため,何ステップか動かす場合を全探索して,その中でスコアが最大になるような動かし方を選ぶのが良い戦略になります.ただし,全探索が可能なステップ数には限界があります.そのため最初のnステップで全探索を打ち止める必要があり,このことを枝刈りと言います. さて,このパズルにスコアをどうやって決めるかですが,完成形が最大か最小のスコアを達成しているようにしなければならないので,例えば,「隣り合う数字との差のすべてのマスについての和」をスコアにしてみるのはどうでしょうか?(これでうまくいくかはわからないです)このスコアではスコアが小さいときが完成形に近いということです.このスコアを決めて,後は3~5ステップくらいを全探索させて,その中からスコア最小の形を選ばせ,そこまで動かします.まだ完成していなかったら,今度はそこから同じことを繰り返します.恐らくこれで完成できるのではないでしょうか. こういったテクニックは普通のプログラミングの本には書いてない場合もあると思います.私は機械学習の文脈でこのテクニックを知りました.プログラミングの専門書というよりも,機械学習の専門書を読むのが良いと思います.