这个版块看起来似乎挺冷清的. 发点东西热闹下.
最近在系统地学习搜索等技巧, 少不了要接触一下 A* 启发式搜索, 自然地, 也少不了八数码经典的问题..
POJ 正好也有一道 Eight. 那就拿这道题开刀吧..
估价函数为未回家的数码的数量和.       
似乎还是慢了点, 250ms, 但又不是太慢...就是写起来麻烦点..呃, 废话到此为止.
btw: 似乎 cpp 标签又不好使了..

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <cstring>
   
4. 
   
5. using namespace std;
   
6. 
   
7. #define HEAP_PARENT(i)                        (i >> 1)
   
8. #define HEAP_LEFT(i)                        (i << 1)
   
9. #define HEAP_RIGHT(i)                        ((i << 1) + 1)
   
10. #define HEAP_KEY(i)                                (heap[i].key)
    
11. 
    
12. const int heap_max = 400000;
    
13. struct heap_data {
    
14.         int step; // depth
    
15.         int key; // f
    
16.         int v; // node
    
17.         unsigned int path[4]; // path
    
18. } heap[heap_max] = {0};
    
19. 
    
20. class class_heap {
    
21. private:
    
22.         int heap_size;
    
23. 
    
24.         void swap(heap_data &arg1, heap_data &arg2)
    
25.         {
    
26.                 heap_data temp_heap;       
    
27.                 temp_heap = arg1; arg1 = arg2; arg2 = temp_heap;
    
28.         }
    
29. 
    
30.         int heap_min_up(int node)
    
31.         {
    
32.                 int parent;
    
33. 
    
34.                 parent = HEAP_PARENT(node);
    
35.                 if (node > 1 && HEAP_KEY(parent) > HEAP_KEY(node)) {
    
36.                         swap(heap[parent], heap[node]);
    
37.                         return heap_min_up(parent);
    
38.                 }
    
39.                 return node;
    
40.         }
    
41. 
    
42.         int heap_min_down(int node)
    
43.         {
    
44.                 int left, right;
    
45.                 int smallest = node;
    
46. 
    
47.                 left = HEAP_LEFT(node);
    
48.                 right = HEAP_RIGHT(node);
    
49.                 if (left <= heap_size && HEAP_KEY(left) < HEAP_KEY(node)) {
    
50.                         smallest = left;
    
51.                 }
    
52.                 if (right <= heap_size && HEAP_KEY(right) < HEAP_KEY(smallest)) {
    
53.                         smallest = right;
    
54.                 }
    
55.                 if (smallest != node) {
    
56.                         smallest = 0;
    
57.                         if (left <= heap_size) {
    
58.                                 smallest = left;
    
59.                         }
    
60.                         if (right <= heap_size && HEAP_KEY(right) < HEAP_KEY(left)) {
    
61.                                 smallest = right;
    
62.                         }
    
63.                         if (smallest) {
    
64.                                 swap(heap[smallest], heap[node]);
    
65.                                 return heap_min_down(smallest);
    
66.                         }
    
67.                 }
    
68.                 return node;
    
69.         }
    
70. 
    
71. public:
    
72.         class_heap() { heap_size = 0; }
    
73. 
    
74.         void insert(heap_data key)
    
75.         {
    
76.                 heap[++heap_size] = key;
    
77.                 heap_min_up(heap_size);
    
78.         }
    
79. 
    
80.         heap_data extract_min()
    
81.         {
    
82.                 heap_data result = heap[1];
    
83. 
    
84.                 swap(heap[1], heap[heap_size--]);
    
85.                 heap_min_down(1);
    
86.                 return result;
    
87.         }
    
88. 
    
89.         bool empty()
    
90.         {
    
91.                 return (heap_size == 0);
    
92.         }
    
93. };
    
94. 
    
95. class_heap heap_table;
    
96. bool hash[400000] = {0};
    
97. const int dstst = 123456780;
    
98. const int table[10] = {0, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};
    
99. const int markl[10][5] = {  
    
100.         {0, 0, 0, 0, 0},
     
101.         {0, 2, 0, 0, 4},
     
102.         {0, 3, 1, 0, 5},
     
103.         {0, 0, 2, 0, 6},
     
104.         {0, 5, 0, 1, 7},
     
105.         {0, 6, 4, 2, 8},
     
106.         {0, 0, 5, 3, 9},
     
107.         {0, 8, 0, 4, 0},
     
108.         {0, 9, 7, 5, 0},
     
109.         {0, 0, 8, 6, 0}
     
110. };
     
111. const char markc[5] = {0, 'r', 'l', 'u', 'd'};
     
112. const int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
     
113. 
     
114. int calc_hash(int key)
     
115. {
     
116.         int result = 0;
     
117.         int decode[10] = {0};
     
118. 
     
119.         for (int i = 9; i > 0; --i) {
     
120.                 decode[i] = key % 10;
     
121.                 key /= 10;
     
122.         }
     
123.         for (int i = 1; i <= 9; ++i) {
     
124.                 for (int j = i + 1; j <= 9; ++j) {
     
125.                         if (decode[j] < decode[i]) {
     
126.                                 result += fac[9 - i];
     
127.                         }
     
128.                 }               
     
129.         }
     
130.         return result;
     
131. }
     
132. 
     
133. int calc_h(int key)
     
134. {
     
135.         int key1, key2, result;
     
136. 
     
137.         key1 = dstst; key2 = key; result = 0;
     
138.         for (int i = 1; i <= 9; ++i) {
     
139.                 if ((key1 % 10 != key2 % 10) && (key2 % 10 != 0)) {
     
140.                         ++result;
     
141.                 }
     
142.                 key1 /= 10;
     
143.                 key2 /= 10;
     
144.         }
     
145.         return result;
     
146. }
     
147. 
     
148. void expand_node(heap_data old_state)
     
149. {
     
150.         int i, n, k, t, h;
     
151.         int decode[10] = {0};
     
152.         heap_data new_state;
     
153. 
     
154.         t = old_state.v;
     
155.         for (i = 9; i > 0; --i) {
     
156.                 decode[i] = t % 10;
     
157.                 t /= 10;
     
158.                 if (decode[i] == 0) {
     
159.                         k = i;
     
160.                 }
     
161.         }
     
162.         for (i = 1; i <= 4; ++i) {
     
163.                 n = markl[k][i];
     
164.                 if (n != 0) {
     
165.                         t = old_state.v;
     
166.                         t -= table[n] * decode[n];
     
167.                         t += table[k] * decode[n];                       
     
168.                         h = calc_hash(t);
     
169.                         if (!hash[h]) {
     
170.                                 new_state.v = t;
     
171.                                 new_state.key = old_state.step + calc_h(t);                               
     
172.                                 new_state.step = old_state.step + 1;
     
173.                                 memcpy(new_state.path, old_state.path, 16);
     
174.                                 new_state.path[old_state.step / 16] |= ((i - 1) << old_state.step % 16 * 2);
     
175.                                 hash[h] = true;
     
176.                                 heap_table.insert(new_state);
     
177.                         }
     
178.                 }
     
179.         }
     
180. }
     
181. 
     
182. void astar_search()
     
183. {
     
184.         heap_data node;
     
185.         int flag = false;
     
186. 
     
187.         while (!heap_table.empty()) {
     
188.                 node = heap_table.extract_min();
     
189.                 if (node.v == dstst) {
     
190.                         for (int i = 0; i < node.step; ++i) {
     
191.                                 cout<<markc[node.path[i / 16] % 4 + 1];
     
192.                                 node.path[i / 16] >>= 2;
     
193.                         }
     
194.                         flag = true;
     
195.                         break;
     
196.                 } else {
     
197.                         expand_node(node);
     
198.                 }
     
199.         }
     
200.         if (!flag) {
     
201.                 cout<<"unsolvable"<<endl;
     
202.         }
     
203. }
     
204. 
     
205. int main()
     
206. {
     
207.         int src = 0;
     
208.         char ch;
     
209.         heap_data srcst;
     
210. 
     
211.         for (int i = 1; i <= 9; ++i) {
     
212.                 cin>>ch;
     
213.                 if (ch != 'x') {
     
214.                         ch -= '0';
     
215.                         src += table[i] * ch;
     
216.                 }
     
217.         }
     
218.         hash[calc_hash(src)] = true;
     
219.         srcst.v = src;
     
220.         srcst.key = calc_h(src);
     
221.         srcst.step = 0;
     
222.         memset(srcst.path, 0, 16);
     
223.         heap_table.insert(srcst);
     
224.         astar_search();
     
225.         return 0;
     
226. }

复制代码

写的太乱, 不好意思.

FB神牛恐怕都忘了咱有这个版块了吧
最近在学基本的优化算法，希望半年到一年内能搞定一些简单的OI题目。

FB神牛恐怕都忘了咱有这个版块了吧
最近在学基本的优化算法，希望半年到一年内能搞定一些简单的OI题目。 ...
FlowerCode 发表于 2010-2-1 14:43

FC 要搞 ACM 了!

回复 3# ForeverBell


    ACM 就算能做我也不做，太伤脑细胞了。

今天又换了个启发函数, 为所有数码离家的曼哈顿距离之和.
似乎这个更快一点(16ms). 看样子 A* 里启发决定一切.

1. const int dis[10][10] = {
   
2.         {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
   
3.         {0, 0, 1, 3, 1, 2, 3, 2, 3, 4},
   
4.         {0, 1, 0, 1, 2, 1, 2, 3, 2, 3},
   
5.         {0, 2, 1, 0, 3, 2, 1, 4, 3, 2},
   
6.         {0, 1, 2, 3, 0, 1, 2, 1, 2, 3},
   
7.         {0, 2, 1, 2, 1, 0, 1, 2, 1, 2},
   
8.         {0, 3, 2, 1, 2, 1, 0, 3, 2, 1},
   
9.         {0, 2, 3, 4, 1, 2, 3, 0, 1, 2},
   
10.         {0, 3, 2, 3, 2, 1, 2, 1, 0, 1},
    
11.         {0, 4, 3, 2, 3, 2, 1, 2, 1, 0},
    
12. };
    
13. int calc_h(int key)
    
14. {
    
15.         int result = 0;
    
16. 
    
17.         for (int i = 9; i > 0; --i) {
    
18.                 result += dis[i][key % 10];
    
19.                 key /= 10;
    
20.         }
    
21.         return result;
    
22. }

复制代码

"看样子 A* 里启发决定一切"没有启发函数那就不是A*了……
好的启发可以让你没有冗余搜索，相当智能……
坏的启发还不如直接写双向广搜，速度也是超快。
FC想看算法的话，很推荐《算法艺术与信息学竞赛》+《算法艺术与信息学竞赛学习指导》，学习指导高清PDF在Olympiad in Informatics Beginners' Home下载(for free)，话说里面对智能搜索写了不少。
BTW，总觉得IB写过类似的代码……

"看样子 A* 里启发决定一切"没有启发函数那就不是A*了……
好的启发可以让你没有冗余搜索，相当智能……
坏 ...
wangweinoo1 发表于 2010-2-2 19:37

iceboy 啥时候写过了?
ps: 没启发函数 A* 就退化成 BFS 了~

呃，貌似我记错了……

我在想搞这个会不会老得比较快
看到我就头大