fork 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.     // 次のイテレーション用のdeque
  74.     deque<pair<int, Status>> nexts;
  75.  
  76.     pair<int, Status> state;
  77.     state.second.p[0] = PitcherMax[0];
  78.     state.second.p[1] = 0;
  79.     state.second.p[2] = 0;
  80.     state.second.cnt = 0;
  81.     state.second.ret = toString(state.second.p[0]) + " " + toString(state.second.p[1]) + " " + toString(state.second.p[2]) + "\n";
  82.     state.first = Eval(state.second);
  83.  
  84.     // 初期状態をdequeに追加
  85.     beam.push_front(state);
  86.  
  87.     while (!beam.empty()) // dequeが空になるまでループ
  88.     {
  89.         state = beam.front(); beam.pop_front(); // dequeの先頭から要素を一つ取り出す
  90.         if (check(state.second.p)) break; // 終了条件を満たしていれば終わる
  91.         if (flag[state.second.p[0]][state.second.p[1]][state.second.p[2]]) continue; // 訪れたことがあるならスキップ
  92.         else flag[state.second.p[0]][state.second.p[1]][state.second.p[2]] = true; // 訪れたことがないなら、フラグを立てる
  93.  
  94.         pair<int, Status> newState; // 次の状態
  95.         REP (i, PitcherNum)
  96.         {
  97.             REP (j, PitcherNum)
  98.             {
  99.                 if (i == j) continue; // 同じピッチャーに移すことはないからスキップ (例：８のピッチャー -> ８のピッチャー)
  100.  
  101.                 // 中身を移す処理
  102.                 newState.second.p[i] = max(state.second.p[i] - (PitcherMax[j] - state.second.p[j]), 0);
  103.                 newState.second.p[j] = min(state.second.p[j] + state.second.p[i], PitcherMax[j]);
  104.                 newState.second.p[3 - i - j] = state.second.p[3 - i - j];
  105.  
  106.                 // 移動した回数を1増やす
  107.                 newState.second.cnt = state.second.cnt + 1;
  108.  
  109.                 // ピッチャーの状態遷移をメモする
  110.                 newState.second.ret = state.second.ret + toString(newState.second.p[0]) + " " + toString(newState.second.p[1]) + " " + toString(newState.second.p[2]) + "\n";
  111.  
  112.                 // ピッチャーの中身が移動していない場合はスキップする
  113.                 if (newState.second.p[i] == state.second.p[i]) continue;
  114.  
  115.                 // 評価値を計算
  116.                 newState.first = Eval(newState.second);
  117.  
  118.                 // 次のイテレーションを管理するキューに状態を追加
  119.                 nexts.push_back(newState);
  120.             }
  121.         }
  122.  
  123.         // dequeが空 = 現在のイテレーションが終了
  124.         if (beam.empty())
  125.         {
  126.           // 評価値順にソート
  127.           sort(nexts.begin(), nexts.end(), comp);
  128.  
  129.           // 評価値が高いものをビーム幅分キューに追加
  130.           for (int i = 0; i < Beam && !nexts.empty(); ++i)
  131.           {
  132.             beam.push_back(nexts.front());
  133.             nexts.pop_front();
  134.           }
  135.           nexts.clear();
  136.         }
  137.     }
  138.  
  139.     if (check(state.second.p)) return state.second;
  140.     else
  141.     {
  142.         state.second.cnt = -1;
  143.         state.second.ret = "目的の値になりませんでした";
  144.         return state.second;
  145.     }
  146. }
  147.  
  148. int main()
  149. {
  150.     Status result = SolveBeamSearch();
  151.  
  152.     cout << "目的の値: " << Target << endl;
  153.     cout << "移動回数: " << result.cnt << endl;
  154.     cout << "ピッチャーの状態遷移:" << endl;
  155.     cout << result.ret << endl;
  156.  
  157.     return 0;
  158. }
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
目的の値: 4
移動回数: 6
ピッチャーの状態遷移:
8 0 0
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3
https://ideone.com/lRw4vl
language:
C++14 (gcc 8.3)
created:
4 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!