るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

情報科学概論のアレ

情報科学概論のロボットの問題を解きました。
とりあえずプログラム書いてPCに計算させます。(ゴリ押しですが何か)

アルゴリズムは愚直に幅優先探索。(6台までは30秒ぐらいで答えが出る。)

ロボットが1~6台の時の最短方法は以下のようになりました。

台数 手順
2 (a,b)
3 (a,b) (a,c) (a,b)
4 (a,b) (c,d) (a,c) (b,d)
5 (a,b) (a,c) (d,e) (a,d) (a,b) (c,e)
6 (a,b) (a,c) (a,d) (e,f) (a,e) (a,b) (a,c) (d,f)

手順の読み方は例えば3台の場合は

1回目にロボットaとロボットbを近づける。 (a,b)
2回目にロボットaとロボットcを近づける。 (a,c)
3回目にロボットaとロボットbを近づける。 (a,b)

みたいな感じです。


これによると6台の場合は最低でも8回は必要らしいです。



以下ゴミコード

const int MAX_N = 10;
int N;
map<vector<int>,bool> visit;

struct State{
  vector<int> robot_bit;//robot_bit[i]:= i番目のロボットのビット表現
  int res;
  string process;
  State(int _rob[MAX_N],int _res,string _process){
    rep(i,N) robot_bit.pb(_rob[i]);
    res = _res;
    process = _process;
  }
};


bool Fin(vector<int>robot_bit){
  rep(i,N)
    if(robot_bit[i] != (1 << N) - 1) return false;
  return true;
}

bool flag[MAX_N][MAX_N][(1 << MAX_N)][(1 << MAX_N)];

const string table = "abcdef";


void bfs(State start){
  queue<State>Q;
  memset(flag,false,sizeof(flag));
  for(Q.push(start); !Q.empty(); ){
    State now = Q.front(); Q.pop();
    int res = now.res;
    string process = now.process;
    vector<int>robot_bit = now.robot_bit;
    if(visit[robot_bit]) continue;
    visit[robot_bit] = true;
    if(Fin(robot_bit)) {
      cout<<"\n[Process]: ";
      cout<<"( (x,y) = x send information to y )\n";
      cout<<process<<"\n\n";
      cout<<"[Count]:\n";
      cout<<res<<endl;
      return;
    }
    //Trying all combination...
    for(int a = 0; a < N; a++){
      for(int b = a + 1; b < N; b++){	
	int robot_next[MAX_N] = {0};
	rep(i,N) robot_next[i] = robot_bit[i];
	robot_next[a] |= robot_next[b];
	robot_next[b] |= robot_next[a];
	string next_process = process;
	char buf[100];
	sprintf(buf,"(%c,%c),",table[a],table[b]);
	string tmp = buf;
	next_process += tmp;

	Q.push(State(robot_next,res + 1,next_process));
	
      }
    }
  }
  puts("Impossible");
}

int main(){
  int robot_bit_init[MAX_N];
  memset(robot_bit_init,0,sizeof(robot_bit_init));
  do{
    cout<<"How many robots?\n>> ";
    scanf("%d",&N);
  }while((N > 6));
  for(int i = 0; i < N; i++)
    robot_bit_init[i] = (1 << i);
  State start(robot_bit_init,0,"");
  bfs(start);
}