fork(1) download
copy 
  1. // include
  2. #include <algorithm>
  3. #include <sstream>
  4. #include <iostream>
  5. #include <cmath>
  6. #include <string>
  7. #include <utility>
  8. #include <deque>
  9.  
  10. using namespace std;
  11.  
  12. // 数値を文字列に変換する
  13. template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
  14.  
  15. // repetition
  16. #define FOR(i,a,b) for(int i=(a);i<(b);i++)
  17. #define REP(i,n) FOR(i,0,n)
  18.  
  19. const int Beam       = 10; // ビーム幅
  20. const int Target     = 4; // 目的の値
  21. const int PitcherNum = 3; // ピッチャーの数
  22. const int PitcherMax[PitcherNum] = {8, 5, 3}; // 各ピッチャーの最大値
  23.  
  24. // 終了条件を満たすか調べる
  25. bool check(int *Pitchers)
  26. {
  27.     REP(i, PitcherNum)
  28.         if (Pitchers[i] == Target) return true;
  29.     return false;
  30. }
  31.  
  32. // 現在の状態を保持する構造体
  33. struct Status
  34. {
  35.     int p[3];
  36.     int cnt;
  37.     string ret;
  38. };
  39.  
  40. // 評価関数
  41. int Eval(Status state)
  42. {
  43.     int ret = 0;
  44.     ret -= state.cnt;
  45.     for (auto n : state.p)
  46.     {
  47.         if (n % Target == 0) ret += 10;
  48.         ret -= abs(Target - n);
  49.     }
  50.     return ret;
  51. }
  52.  
  53. // pairの比較(ソート用)
  54. bool comp(pair<int, Status> lhs,  pair<int, Status> rhs)
  55. {
  56.     return lhs.first > rhs.first;
  57. }
  58.  
  59. // ビームサーチで解く
  60. Status SolveBeamSearch()
  61. {
  62.     bool flag[PitcherMax[0]+1][PitcherMax[1]+1][PitcherMax[2]+1]; // ある状態になった事があるかを保持する（この処理がないと無限ループ）
  63.  
  64.     // 配列の初期化
  65.     REP(i, PitcherMax[0]+1)
  66.         REP(j, PitcherMax[1]+1)
  67.             REP(k, PitcherMax[2]+1)
  68.                 flag[i][j][k] = false;
  69.  
  70.     // ビームサーチ用のdeque
  71.     deque<pair<int, Status>> beam;
  72.  
  73.     pair<int, Status> state;
  74.     state.second.p[0] = PitcherMax[0];
  75.     state.second.p[1] = 0;
  76.     state.second.p[2] = 0;
  77.     state.second.cnt = 0;
  78.     state.second.ret = toString(state.second.p[0]) + " " + toString(state.second.p[1]) + " " + toString(state.second.p[2]) + "\n";
  79.     state.first = Eval(state.second);
  80.  
  81.     // 初期状態をdequeに追加
  82.     beam.push_front(state);
  83.  
  84.     while (!beam.empty()) // dequeが空になるまでループ
  85.     {
  86.         state = beam.front(); beam.pop_front(); // dequeの先頭から要素を一つ取り出す
  87.         if (check(state.second.p)) break; // 終了条件を満たしていれば終わる
  88.         if (flag[state.second.p[0]][state.second.p[1]][state.second.p[2]]) continue; // 訪れたことがあるならスキップ
  89.         else flag[state.second.p[0]][state.second.p[1]][state.second.p[2]] = true; // 訪れたことがないなら、フラグを立てる
  90.  
  91.         pair<int, Status> newState; // 次の状態
  92.         REP (i, PitcherNum)
  93.         {
  94.             REP (j, PitcherNum)
  95.             {
  96.                 if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)
  97.  
  98.                 // 中身を移す処理
  99.                 newState.second.p[i] = max(state.second.p[i] - (PitcherMax[j] - state.second.p[j]), 0);
  100.                 newState.second.p[j] = min(state.second.p[j] + state.second.p[i], PitcherMax[j]);
  101.                 newState.second.p[3 - i - j] = state.second.p[3 - i - j];
  102.  
  103.                 // 移動した回数を1増やす
  104.                 newState.second.cnt = state.second.cnt + 1;
  105.  
  106.                 // ピッチャーの状態遷移をメモする
  107.                 newState.second.ret = state.second.ret + toString(newState.second.p[0]) + " " + toString(newState.second.p[1]) + " " + toString(newState.second.p[2]) + "\n";
  108.  
  109.                 // ピッチャーの中身が移動していない場合はスキップする
  110.                 if (newState.second.p[i] == state.second.p[i]) continue;
  111.  
  112.                 // 評価値を計算
  113.                 newState.first = Eval(newState.second);
  114.  
  115.                 // dequeに状態を追加
  116.                 beam.push_back(newState);
  117.             }
  118.         }
  119.  
  120.         // 評価値順にソート
  121.         sort(beam.begin(), beam.end(), comp);
  122.  
  123.         // ビーム幅より大きければ評価値が小さい枝を削除
  124.         while (beam.size() > Beam) beam.pop_back();
  125.     }
  126.  
  127.     if (check(state.second.p)) return state.second;
  128.     else
  129.     {
  130.         state.second.cnt = -1;
  131.         state.second.ret = "目的の値になりませんでした";
  132.         return state.second;
  133.     }
  134. }
  135.  
  136. int main()
  137. {
  138.     Status result = SolveBeamSearch();
  139.  
  140.     cout << "目的の値: " << Target << endl;
  141.     cout << "移動回数: " << result.cnt << endl;
  142.     cout << "ピッチャーの状態遷移:" << endl;
  143.     cout << result.ret << endl;
  144.  
  145.     return 0;
  146. }
  147.  
Success #stdin #stdout 0s 3488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
目的の値: 4
移動回数: 7
ピッチャーの状態遷移:
8 0 0
5 0 3
5 3 0
2 3 3
2 5 1
7 0 1
7 1 0
4 1 3
https://ideone.com/pJiz39
WaterJugProblem Solve with BeamSearch
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!