優先度付きキュー 15パズル aスター 幅優先探索 aoj マンハッタン距離 alds1_13_c

ALDS1_13_C 15 パズル

ALDS1_13_C 15 パズル
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_C

8パズルを16マスに拡張したバージョン.
必要な探索量が膨大になるので時間とメモリにさらなる工夫が必要.

解説

基本的には8パズルのアルゴリズムを使用し、変更するのは以下の1点.

8パズルでは次の可能性の盤面を適当な順番でキューから取り出していたのに対し、今回は盤面に何らかの点数を付与してそれが良い順にキューを処理する.
点数として、その盤面に到達するまでにかかった遷移回数+正解盤面までのマンハッタン距離の総和を使用する.

まず、遷移回数はキューに新しい盤面を入れるごとに+1する.
正解盤面までの距離が同じ場合は遷移回数が少ないほうが優秀な解答なので遷移回数を少ない方から処理する.

マンハッタン距離というのは、座標上の点間のxの距離とyの距離の合計.
16マスあるので、それぞれの点の正解までのマンハッタン距離を合計すればざっくりとした必要遷移回数が求められる.

これらの合計が少ないほうが優秀な解答なので優先度付きキューを使って優先的に探索を進めていく.

盤面を表すのにvectorや遷移を表すのにstringを使うと時間制限超過でミスになるので使わない.

解答

  • 時間: 1:51s
  • メモリ: 257108KB
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#define N 4
#define NN (N*N)

vector<Int> dx = {0, 0, -1, 1};
vector<Int> dy = {-1, 1, 0, 0};
vector<char> dirs = {'u', 'd', 'l', 'r'};
Int MDT[NN][NN];


class Puzzle {
public:
  Int vec[NN];
  Int blank, estimate, cost;

  Puzzle(): blank(-1), estimate(-1), cost(0) {
    loop(n,0,NN) vec[n] = -1;
  }

  Puzzle(Int vec[NN], Int blank, Int cost) {
    loop(n,0,NN) this->vec[n] = vec[n];
    this->blank = blank;
    this->cost = cost;

    updateEstimate();
  }

  bool operator < (const Puzzle &other) const {
    return estimate > other.estimate;
  }

  bool operator == (const Puzzle &other) const { 
    loop(n,0,NN) {
      if (vec[n] != other.vec[n]) return false;
    }

    return true;
  }

  void updateEstimate() {
    estimate = cost;
    loop(n,0,NN) {
      if (vec[n] == NN) continue; // blank
      estimate += MDT[n][vec[n]-1];
    }
  }

  Puzzle move(Int dir) {
    Int sx, sy, tx, ty;
    sx = blank % N;
    sy = blank / N;

    switch (dir) {
      case 0:
      case 1:
      case 2:
      case 3:
        tx = sx + dx[dir];
        ty = sy + dy[dir];
        break;
      default:
        cout << "Invalid dir: " << dir << endl;
        exit(1);
        break;
    }

    Puzzle p;

    if (tx < 0 || N <= tx || ty < 0 || N <= ty) {
      return p;
    }

    p = *this;
    swap(p.vec[sy * N + sx], p.vec[ty * N + tx]);
    p.blank = ty * N + tx;
    p.cost++;
    p.updateEstimate();
    return p;
  }
};

namespace std {
  template <>
  struct hash<Puzzle>
  {
    std::size_t operator()(const Puzzle& p) const
    {
      std::size_t seed = NN;
      for(auto& i : p.vec) {
        seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
      }
      return seed;
    }
  };
}


Int targetVec[NN] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
Puzzle target(targetVec, 15, -1);
Puzzle source;


Int bfs() {
  priority_queue<Puzzle> Q;
  unordered_map<Puzzle, bool> DONE;

  Q.push(source);
  DONE[source] = true;

  Puzzle top;

  while (!Q.empty()) {
    top = Q.top(); Q.pop();
    if (top == target) return top.cost;

    loop(dir,0,dirs.size()) {
      Puzzle p = top.move(dir);
      if (p.blank == -1) continue;
      if (DONE[p]) continue;
      DONE[p] = true;
      Q.push(p);
    }
  }

  cout << "No solution" << endl;
  return -1;
}

void input() {
  Int vec[NN];
  Int blank = -1;
  loop(h,0,N) {
    loop(w,0,N) {
      cin >> vec[h*N + w];
      if (vec[h*N + w] == 0) {
        blank = h * N + w;
        vec[h*N+w] = NN;
      }
    }
  }
  loop(n,0,NN) source.vec[n] = vec[n];
  source.blank = blank;
  source.cost = 0;
  source.updateEstimate();
}

void solve() {
  loop(i,0,NN) {
    loop(j,0,NN) {
      MDT[i][j] = abs(i/N - j/N) + abs(i%N - j%N);
    }
  }
  cout << bfs() << endl;
}


int main() {
  input();
  solve();
}