[技術討論] C++功課

本帖最後由 神秘二代 於 2013-11-24 14:28 編輯

關於類近puzzle玩法的......
希望高人出手相助指點
不便公開code........PM plz~

I personally would suggest you consult your lecturer for your course work problem, you paid for that, and thats how you learn from the course, if all you do is coming to a public forum and cry for help, why don't you just learn yourself instead of going for the course?

TOP

anyone can help

TOP

本帖最後由 神秘二代 於 2013-11-29 09:10 編輯

delete.

TOP

i think the key point is, h will changed in every state, and due to duplicate number, h are not accu ...
神秘二代 發表於 2013-11-27 21:42


dynamic programming is to optimize a solution rather than a solution itself?

TOP

本帖最後由 神秘二代 於 2013-11-27 21:56 編輯

i think the key point is, h will changed in every state, and due to duplicate number, h are not accurate
may need to use dynamic programming

TOP

本帖最後由 神秘二代 於 2013-11-27 21:19 編輯
I've written an example program. It can handle arbitrary number of slots and duplicate numbers. I on ...
KoolFreeze 發表於 2013-11-27 16:31


Sorry, your algorithm cannot pass the following case
5
50204
34030
63310
35361
23111

5
30002
34050
63311
35364
23111

Your algorithm result is 32, but correct answer is 18......
and..... some of cases also cannot get the best solutions.....
So that what i said cannot cover all of cases......

but anyway, thanks for your help

TOP

本帖最後由 KoolFreeze 於 2013-11-27 16:32 編輯

I've written an example program. It can handle arbitrary number of slots and duplicate numbers. I only focus on simplicity rather than speed, so there are still many rooms for optimization.
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>

  4. using namespace std;

  5. typedef vector< vector<int> > State;

  6. map<State, bool> visited;
  7. vector<State> path;
  8. State start, target;
  9. int N;

  10. void input(State &s) {
  11.   s = State(N, vector<int>(N));
  12.   for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> s[i][j];
  13. }

  14. inline int h(const State &s, const State &t) {
  15.   int a, b, c, d, tot = 0;
  16.   for (a = 0; a < N; ++a) for (b = 0; b < N; ++b) if (s[a][b] != 0) {
  17.     int best = N + N;
  18.     for (c = 0; c < N; ++c) for (d = 0; d < N; ++d) if (t[c][d] == s[a][b]) {
  19.       if (best > abs(a - c) + abs(b - d)) best = abs(a - c) + abs(b - d);
  20.     }
  21.     tot += best;
  22.   }
  23.   return tot;
  24. }

  25. bool IDAStar(const State &s, int cost, int limit) {
  26.   visited[s] = true;
  27.   path.push_back(s);
  28.   if (s == target) {
  29.     for (int x = 0; x <= cost; ++x) {
  30.       cout << "== Step " << x << " ==" << endl;
  31.       for (int i = 0; i < N; ++i) {
  32.         for (int j = 0; j < N; ++j) cout << path[x][i][j] << ' ';
  33.         cout << endl;
  34.       }
  35.     }
  36.   } else if (cost + h(s, target) <= limit) {
  37.     for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) if (s[i][j] == 0) {
  38.       for (int d = 0; d < 4; ++d) {
  39.         int ni = i + ((d + 1) % 2) * (d - 1), nj = j + (d % 2) * (d - 2);
  40.         if (ni >= 0 && ni < N && nj >= 0 && nj < N && s[ni][nj] != 0) {
  41.           State ns(s);
  42.           swap(ns[i][j], ns[ni][nj]);
  43.           if (!visited[ns] && IDAStar(ns, cost + 1, limit)) return true;
  44.         }
  45.       }
  46.     }
  47.   }
  48.   path.pop_back();
  49.   return s == target;
  50. }

  51. int main() {
  52.   cout << "N? ";
  53.   cin >> N;
  54.   cout << "Starting state?" << endl;
  55.   input(start);
  56.   cout << "Target state?" << endl;
  57.   input(target);
  58.   for (int limit = 0; !IDAStar(start, 0, limit); ++limit) {
  59.     visited.clear();
  60.     cout << "Searching with limit " << limit << "..." << endl;
  61.   }
  62.   return 0;
  63. }
複製代碼
Example input
  1. N? 4
  2. Starting state?
  3. 1 2 0 3
  4. 3 0 4 0
  5. 4 4 6 0
  6. 1 4 5 6
  7. Ending state?
  8. 4 0 0 2
  9. 3 0 1 0
  10. 4 4 6 6
  11. 1 4 5 3
複製代碼

TOP

回復 31# 神秘二代

A simple solution is to find all spaces and swap each with any adjacent tile.

For heuristic function, you don't need to insist on matching each tile of the same digit to a different location. Otherwise, it becomes a Maximum Weight Matching problem, which can be quite complicated. You can simply use the shortest manhattan distance to that digit at the target state. It is still an admissible heuristic.

TOP

本帖最後由 神秘二代 於 2013-11-27 00:06 編輯
It just depends on how you enumerate neighbour states.
KoolFreeze 發表於 2013-11-26 01:48


as i said....not easy to guess since duplicate number

TOP