Board logo

標題: [技術討論] C++功課 [打印本頁]

作者: 神秘二代    時間: 2013-11-24 14:24     標題: C++功課

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

關於類近puzzle玩法的......
希望高人出手相助指點
不便公開code........PM plz~
作者: bluenemo    時間: 2013-11-24 14:47

關於類近puzzle玩法的......
希望高人出手相助指點
不便公開code........PM plz~
神秘二代 發表於 2013-11-24 14:24


Rush Hour?
作者: 神秘二代    時間: 2013-11-24 14:51

本帖最後由 神秘二代 於 2013-11-24 15:06 編輯
Rush Hour?
bluenemo 發表於 2013-11-24 14:47


n-number puzzle, but with two or more slots, also number repeated
(start)-->(goal)
323         233
405          450
067 -->  670
something like that

i don't know how to solve this...... i know there have IDA* concept but algorithm hard to think....T-T
作者: bluenemo    時間: 2013-11-24 15:15

回復 3# 神秘二代

連點樣solve個problem都未有idea? 咁點寫program?
作者: 神秘二代    時間: 2013-11-24 15:29

本帖最後由 神秘二代 於 2013-11-24 15:32 編輯
回復  神秘二代

連點樣solve個problem都未有idea? 咁點寫program?
bluenemo 發表於 2013-11-24 15:15


i have some idea, but cannot cover all cases, i want someone can guide me how to do....
my first think is, find the shortest path between each number, when shortest path found, other number not link this number for shortest path
for example
120        220
320 --> 130
000         000
shortest path --> 1->1(cost:1), 2->2(cost:0), 2->2(cost:2), 3-->3(cost:1), total cost = 4
aleast 4 step to come to goal
second think is, start from slot (0), test move if each slot have the number in 4 position: up, down, right, left. if swaped, check the cost again to find the best path. for each iteration, base cost will increase 1.
but the problem is....some cases cannot fulfill the above algorithm, for example
120        020
322 --> 322
000         001
i don't know how to solve this case.......can give me a some hints?
作者: bluenemo    時間: 2013-11-24 15:37

Not quite sure if i got your game correct... is this like this:

http://en.wikipedia.org/wiki/15_puzzle
作者: 神秘二代    時間: 2013-11-24 15:52

本帖最後由 神秘二代 於 2013-11-24 15:54 編輯
Not quite sure if i got your game correct... is this like this:
bluenemo 發表於 2013-11-24 15:37


thanks, but.....not useful
作者: Jackass_TMxCK    時間: 2013-11-24 19:54

聽唔明你想講咩=.=


你英文唔係太好,不如打返中文=.=
作者: 神秘二代    時間: 2013-11-24 20:02

簡單就係
佢有個nxn ge面版, 上面有0-9的數字, 0=空格
數字可以重複, 而每次會input開始時ge數字面版同完結時ge數字面版
而家要整一個演算法列出行走步驟........
最煩係有N個空格同埋N個相同數字.....
e.g.
123
321
120
變成
123
321
012
走法就係
LL
但有時有幾個0或數字重複我就開始搞唔清應該點分配.....究竟呢個數字最終應該係果個定果個= =
e.g.
123
245
670
final:
122
345
670
咁究竟第二行ge 2係第一行ge邊個2........定係我複雜左? 根本唔洗理邊個2...../_\
睇d example....都無我呢個case, 自己想得好辛苦.......自問唔係編程高手
作者: bluenemo    時間: 2013-11-24 20:14

Check if you can formulate your solution in this form:

http://www.cs.sjsu.edu/~stamp/cv/papers/rh.pdf

If yes, either Dijkstra's algorithm or IDA* search will be able to help search the solution.
作者: Jimmy0911    時間: 2013-11-24 21:20

開個array
做CHECKING
IF right pattern -> true
DONE

唔洗太複雜
作者: 神秘二代    時間: 2013-11-24 21:42

開個array
做CHECKING
IF right pattern -> true
DONE

唔洗太複雜
Jimmy0911 發表於 2013-11-24 21:20


講就易~~
作者: Jimmy0911    時間: 2013-11-25 00:23

回復 12# 神秘二代


之前做過象棋
真係會更難?
作者: 神秘二代    時間: 2013-11-25 00:25

回復  神秘二代


之前做過象棋
真係會更難?
Jimmy0911 發表於 2013-11-25 00:23


象棋AI?

作者: Jimmy0911    時間: 2013-11-25 00:29

回復 14# 神秘二代

year one project未去到ai
二人對戰,做埋UI
作者: Jimmy0911    時間: 2013-11-25 01:10

btw....

師兄試下開array
每個array 做一個number
[1][2][3]
[4][5][6]
[7][8][9]
當NUMBER 係咩時,assign佢係你既pizzle
例如9係空格
1係2,2都可以係2
background 處理用唔重覆既number
但show出黎可以係一樣number

checking
之後每個array 如果旁邊既Number係0,先可以move
最後出番最終答案時 -> done 出looping

唔知咁岩唔岩你
作者: 神秘二代    時間: 2013-11-25 01:37

本帖最後由 神秘二代 於 2013-11-25 01:47 編輯
btw....

師兄試下開array
每個array 做一個number
[1][2][3]
[4][5][6]
[7][8][9]
當NUMBER 係咩時,assig ...
Jimmy0911 發表於 2013-11-25 01:10


用number check空格...唔可行, 你每move一次要loop哂n個elements, 效率超差
同埋你這個想法我都有試過, 就係有某些case會有問題
e.g.
1203
3040
4460
1456
final:
4002
3010
4466
1453
作者: Jimmy0911    時間: 2013-11-25 07:29

回復 17# 神秘二代


咁用英文字囉
作者: Jimmy0911    時間: 2013-11-25 09:04

要efficient用pointer 囉
作者: Jackass_TMxCK    時間: 2013-11-25 18:35

要efficient用pointer 囉
Jimmy0911 發表於 25/11/2013 09:04 AM



    呢個係o(n^2) ge問題
作者: Jackass_TMxCK    時間: 2013-11-25 18:55

兄弟你幾時要交?不如我幫你問下教我2D Game Production個Lecturer點攪lol
佢好勁(應該)

呢個assignment有多少難度。佢有要求Big O唔可以太大定係解到題就得?
作者: Jackass_TMxCK    時間: 2013-11-25 18:59

The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.

研究下點用A*去解
作者: 神秘二代    時間: 2013-11-25 19:39

The n-puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heu ...
Jackass_TMxCK 發表於 2013-11-25 18:59


PM
作者: Jimmy0911    時間: 2013-11-25 20:32

本帖最後由 Jimmy0911 於 2013-11-25 21:38 編輯

回復 20# Jackass_TMxCK


oh,sor
作者: Jimmy0911    時間: 2013-11-25 20:59

本帖最後由 Jimmy0911 於 2013-11-25 21:38 編輯

多左--------del
作者: KoolFreeze    時間: 2013-11-26 01:02

本帖最後由 KoolFreeze 於 2013-11-26 01:05 編輯
開個array
做CHECKING
IF right pattern -> true
DONE

唔洗太複雜
Jimmy0911 發表於 2013-11-24 21:20


How do you check all the configurations of various moves?
Do you know that there are an exponential number of states?
How can you make sure your program run fast enough?

Chess without AI is merely hard-coding.
This problem is more challenging.
作者: KoolFreeze    時間: 2013-11-26 01:16

本帖最後由 KoolFreeze 於 2013-11-26 01:43 編輯

Here is the pseudocode of the basic algorithm

IDAStar(State s, int limit) {
    mark state s as visited
    if s is ending state {
        print the path by tracing the predecessor of s
    } else {
       for all neighbour state s' {
           if s' is not visited && limit >= cost of s' + h(s') {
               mark s' as visited
               record s as the predecessor of s'
               IDAStar(s', limit)
           }
       }
   }
}

where h(s') is an admissible heuristic function, for example, sum of manhattan distances of each tiles.
作者: 神秘二代    時間: 2013-11-26 01:22

本帖最後由 神秘二代 於 2013-11-26 01:24 編輯
Here is the pseudocode of the basic algorithm

IDAStar(State s, int limit) {
    mark state s as vis ...
KoolFreeze 發表於 2013-11-26 01:16


IDAStar(s', limit - (cost of s' + h(s')))
why limit - (cost of s' + h(s'))
also, this algorithm not consider more than 1 slot and duplicate number
but as you said, just basic algorithm
作者: KoolFreeze    時間: 2013-11-26 01:46

回復 28# 神秘二代

My mistake... No need to update the limit.
Just keep calling IDAStar with an increasing limit until a solution can be found.
作者: KoolFreeze    時間: 2013-11-26 01:48

also, this algorithm not consider more than 1 slot and duplicate number
神秘二代 發表於 2013-11-26 01:22


It just depends on how you enumerate neighbour states.
作者: 神秘二代    時間: 2013-11-27 00:04

本帖最後由 神秘二代 於 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
作者: KoolFreeze    時間: 2013-11-27 16:24

回復 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.
作者: KoolFreeze    時間: 2013-11-27 16:31

本帖最後由 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
複製代碼

作者: 神秘二代    時間: 2013-11-27 19:58

本帖最後由 神秘二代 於 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
作者: 神秘二代    時間: 2013-11-27 21:42

本帖最後由 神秘二代 於 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
作者: bluenemo    時間: 2013-11-27 22:29

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?
作者: 神秘二代    時間: 2013-11-28 19:12

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

delete.
作者: 神秘二代    時間: 2013-11-29 09:09

anyone can help
作者: domeso    時間: 2013-11-29 09:15

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?





歡迎光臨 電腦領域 HKEPC Hardware (https://www.hkepc.com/forum/) Powered by Discuz! 7.2