きっかけ 先日、友人にある問題を出題され、その答え合わせにプログラムで解いてみようと思ったからです。あと、ビームサーチは書いたことなかったので、練習も兼ねて書いてみました。(今回は探索空間が狭いので、わざわざビームサーチを使う理由はないです。また、評価関数が適当なので近似解しか求まりません) 今回扱う問題 一般的にWater Jug Problemと呼ばれる問題です。(間違ってたらすみません) 映画「ダイハード3」の中でも似た問題が出てきました。 問題概要 ユウキ君は8dLのピッチャーに入ったヨーグルトスムージーをレイちゃんと半分にする方法を考えています。 ユウキ君は8dL、5dL、3dL入るピッチャーを使うことができます。 スムージーを最低何回移し替えればいいでしょうか？ というような問題です。 考察 全探索で求まりそう 最小回数を求めるなら幅優先探索が使えそう! ということで書いていき
