A*算法解題
參考:
http://m.shnenglu.com/longzxr/archive/2009/08/12/92978.htmlhttp://www.chhaya.me/?p=182第一次寫(xiě)A*，寫(xiě)的相當(dāng)?shù)胤爆?，一方面是由于自己?xiě)了優(yōu)先級(jí)隊(duì)列，另一方面則是由于需要保存的信息相對(duì)較多，每個(gè)狀態(tài)在隊(duì)列中的位置都隨著pop與push動(dòng)態(tài)變化，所以新添了idx[]數(shù)組來(lái)存儲(chǔ)當(dāng)前的位置，數(shù)組下標(biāo)是hash值
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define STR_LEN 9
5 #define HASH_LEN 362880 /* 9! */
6 const int facs[] = {1, 2, 6, 24, 120, 720, 5040, 40320};
7 const char letters[] = "udlr";
8 const int pos[] = {-3, 3, -1, 1}; /* up, down, left, right */
9 const int movable[][4] = {0,1,0,1, 0,1,1,1, 0,1,1,0, 1,1,0,1, 1,1,1,1, 1,1,1,0, 1,0,0,1, 1,0,1,1, 1,0,1,0};
10 const int points[][2] = {{0,0}, {1,0}, {2,0}, {0,-1}, {1,-1}, {2,-1}, {0,-2}, {1,-2}, {2,-2}};
11 int distance[STR_LEN][STR_LEN];
12 struct EACH {
13 char str[STR_LEN+1];
14 int pos, value;
15 } queue[HASH_LEN];
16 int pre[HASH_LEN], dir[HASH_LEN], g[HASH_LEN], h[HASH_LEN], idx[HASH_LEN];
17 int mark[HASH_LEN]; /* 0: unvisited / 1: open-list / 2: closed-list */
18 int target; /* target hash value: "123456780" */
19
20 /* ------begin: priority queue ------*/
21 int count;
22 #define LEFT_CLD(i) ((i<<1)+1)
23 #define RIGHT_CLD(i) ((i+1)<<1)
24 #define PARENT(i) ((i-1)>>1)
25
26 int
27 compare_item(struct EACH *arg1, struct EACH *arg2)
28 {
29 return ((g[arg1->value] + h[arg1->value]) - (g[arg2->value] + h[arg2->value]));
30 }
31
32 void
33 swap(i, j)
34 {
35 struct EACH tmp = queue[i];
36 queue[i] = queue[j];
37 queue[j] = tmp;
38 idx[queue[i].value] = j;
39 idx[queue[j].value] = i;
40 }
41
42 void
43 min_heapify(int heapsize, int i)
44 {
45 int min = i;
46 int left = LEFT_CLD(i);
47 int right = RIGHT_CLD(i);
48 if(left<heapsize && compare_item(queue+min, queue+left)>0)
49 min = left;
50 if(right<heapsize && compare_item(queue+min, queue+right)>0)
51 min = right;
52 if(min != i) {
53 swap(i, min);
54 min_heapify(heapsize, min);
55 }
56 }
57
58 struct EACH
59 pop()
60 {
61 struct EACH rt = queue[0];
62 swap(0, count-1);
63 --count;
64 min_heapify(count, 0);
65 return rt;
66 }
67
68 void
69 up_heapify(int from)
70 {
71 int cld, pt;
72 cld = from;
73 pt = PARENT(cld);
74 while(cld>0 && compare_item(queue+cld, queue+pt)<0) {
75 swap(cld, pt);
76 cld = pt;
77 pt = PARENT(cld);
78 }
79 }
80
81 void
82 push(struct EACH item)
83 {
84 int cld, pt;
85 ++count;
86 queue[count-1] = item;
87 up_heapify(count-1);
88 }
89 /* -------end: priority queue -------*/
90
91 /* permutation -> number */
92 int
93 hash_func(char *str)
94 {
95 int i, j, cnt, result = 0;
96 for(i=1; i<STR_LEN; i++) {
97 cnt = 0;
98 for(j=0; j<i; j++)
99 if(str[j] > str[i])
100 ++cnt;
101 result += (cnt*facs[i-1]);
102 }
103 return result;
104 }
105
106 int
107 dist(int i, int j)
108 {
109 int px, py;
110 px = points[i][0] - points[j][0];
111 py = points[i][1] - points[j][1];
112 px = px>=0 ? px : -px;
113 py = py>=0 ? py : -py;
114 return px+py;
115 }
116
117 /* estimate function: manhattan distance */
118 int
119 estimate(char *str)
120 {
121 int i, rt = 0;
122 for(i=0; i<STR_LEN; i++)
123 if(str[i] != '0')
124 rt += distance[i][str[i]-'0'-1];
125 return rt;
126 }
127
128 void
129 output(int hash_value)
130 {
131 if(pre[hash_value] == -1)
132 return;
133 output(pre[hash_value]);
134 printf("%c", letters[dir[hash_value]]);
135 }
136
137 void
138 Astar(char *start_str, int start_pos)
139 {
140 int i, th, hvalue, curp, nxtp;
141 char nxt[STR_LEN+1];
142 struct EACH cur, tmp;
143 strcpy(queue[0].str, start_str);
144 queue[0].pos = start_pos;
145 queue[0].value = hash_func(start_str);
146 count = 1;
147 mark[queue[0].value] = 1; /* open list */
148 g[queue[0].value] = 0;
149 h[queue[0].value] = estimate(start_str);
150 pre[queue[0].value] = -1;
151 dir[queue[0].value] = -1;
152 idx[queue[0].value] = 0;
153 while(count != 0) {
154 cur = pop();
155 if(cur.value == target) {
156 output(target);
157 printf("\n");
158 return;
159 }
160 mark[cur.value] = 2;
161 curp = cur.pos;
162 for(i=0; i<4; i++) {
163 if(movable[curp][i]) {
164 nxtp = curp + pos[i];
165 strcpy(nxt, cur.str);
166 nxt[curp] = nxt[nxtp];
167 nxt[nxtp] = '0';
168 hvalue = hash_func(nxt);
169 if(mark[hvalue]==1 && g[hvalue]>(g[cur.value]+1)) {
170 g[hvalue] = g[cur.value]+1;
171 pre[hvalue] = cur.value;
172 dir[hvalue] = i;
173 up_heapify(idx[hvalue]);
174 } else if(mark[hvalue]==0) {
175 strcpy(tmp.str, nxt);
176 tmp.pos = nxtp;
177 tmp.value = hvalue;
178 mark[hvalue] = 1;
179 g[hvalue] = g[cur.value]+1;
180 h[hvalue] = estimate(nxt);
181 pre[hvalue] = cur.value;
182 dir[hvalue] = i;
183 idx[hvalue] = count;
184 push(tmp);
185 }
186 }
187 }
188 }
189 printf("unsolvable\n");
190 }
191
192 int
193 main(int argc, char **argv)
194 {
195 int i, j, len, sp, cnt=0;
196 char input[STR_LEN*5], num[STR_LEN+1];
197 fgets(input, STR_LEN*5-1, stdin);
198 len = strlen(input);
199 for(i=0; i<len; i++) {
200 if(input[i]>='0' && input[i]<='8')
201 num[cnt++] = input[i];
202 else if(input[i]=='x') {
203 num[cnt++] = '0';
204 sp = cnt-1;
205 }
206 }
207 num[STR_LEN] = '\0';
208 for(i=0; i<STR_LEN; i++)
209 for(j=0; j<STR_LEN; j++)
210 distance[i][j] = dist(i, j);
211 memset(pre, -1, sizeof(pre));
212 memset(dir, -1, sizeof(dir));
213 memset(idx, -1, sizeof(idx));
214 memset(mark, 0, sizeof(mark));
215 memset(g, 0, sizeof(g));
216 memset(h, 0, sizeof(h));
217 target = hash_func("123456780");
218 Astar(num, sp);
219 return 0;
220 }