青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

<label id="cjoir"><dl id="cjoir"></dl></label>

<label id="cjoir"><wbr id="cjoir"><meter id="cjoir"></meter></wbr></label>

<label id="cjoir"><dl id="cjoir"></dl></label>

<abbr id="cjoir"></abbr>

coreBugZJ

此 blog 已棄。

A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight

1

/*
2

3

A* 算法求解八數(shù)碼問(wèn)題
4

5

6

----問(wèn)題描述：
7

8

經(jīng)典八數(shù)碼問(wèn)題，
9

在3×3的方格棋盤(pán)上，分別擺放著1到8這八個(gè)數(shù)碼，剩余一個(gè)方格為空白。
10

11

如下為一個(gè)狀態(tài)，
12

13

1 2 3
14

15

x 4 6
16

17

7 5 8
18

19

其中 x 代表空白方格。
20

21

22

現(xiàn)給定初始狀態(tài)，要求對(duì)空白方格執(zhí)行
23

24

左移（l，空白方格與其左邊方格互換），
25

右移（r，空白方格與其右邊方格互換），
26

上移（u，空白方格與其上邊方格互換），
27

下移（d，空白方格與其下邊方格互換），
28

29

這四個(gè)操作使得棋盤(pán)變換為如下的
30

31

1 2 3
32

33

4 5 6
34

35

7 8 x
36

37

的目標(biāo)狀態(tài)。
38

39

40

----輸入：
41

42

初始狀態(tài)。
43

44

形如
45

46

1 2 3 x 4 6 7 5 8
47

48

表示
49

50

1 2 3
51

52

x 4 6
53

54

7 5 8
55

56

57

----輸出：
58

59

如果無(wú)解，輸出字符串"unsolvable"；
60

如果有解，輸出變換過(guò)程，為包含字符 'l'，'r'，'u'，'d' 的字符串，各字符的含義見(jiàn)上文。
61

62

63

----樣例輸入：
64

65

2 3 4 1 5 x 7 6 8
66

67

68

----樣例輸出：
69

70

ullddrurdllurdruldr
71

72

73

----分析：
74

75

本問(wèn)題實(shí)為 POJ 1077 Eight，前年寫(xiě)的代碼，今天加上注釋?zhuān)鳛閷?duì) A* 的復(fù)習(xí)。
76

77

這里只要求找出一個(gè)解即可，不必找出最優(yōu)解，且空間不大，僅 9！，因而 A* 具有優(yōu)勢(shì)。
78

79

簡(jiǎn)單解釋幾個(gè)地方，具體見(jiàn)代碼注釋。
80

81

1.排列轉(zhuǎn)化為序數(shù)
82

例，1 2 3 這三個(gè)數(shù)字的全排列，按字典序，依次為
83

84

123 -- 0
85

132 -- 1
86

213 -- 2
87

231 -- 3
88

312 -- 4
89

321 -- 5
90

91

其中，左側(cè)為排列，右側(cè)為其序數(shù)。
92

轉(zhuǎn)化算法此處不再贅述。
93

94

2.對(duì)形如
95

96

1 2 3
97

98

x 4 6
99

100

7 5 8
101

102

的狀態(tài)，表示為整數(shù) 123946758，其中 x 用數(shù)字 9 代替。
103

104

3.將一個(gè)狀態(tài)視為數(shù)字 1-9 的一個(gè)排列，將此排列轉(zhuǎn)化為序數(shù)，作為此狀態(tài)的 HASH 值。
105

106

4.使用數(shù)據(jù)結(jié)構(gòu) 堆加速挑選最優(yōu)值。
107

108

5.函數(shù) g 的計(jì)算，此狀態(tài)在搜索樹(shù)中的父結(jié)點(diǎn)的數(shù)量。
109

110

6.函數(shù) h 的計(jì)算，見(jiàn)代碼 calcH 函數(shù)。
111

112

113

*/
114

115

116

#include <stdio.h>
117

#include <string.h>
118

#include <stdlib.h>
119

120

#define L 362880
121

#define MAXMAX 2123456789
122

123

typedef struct
124

{
125

int arrange, preIndex, g, h, f, flag; // flag -1 closed, 0 no, 1 open
126

char choice;
127

} State;
128

129

State state[ L ];
130

int start, goal, startIndex, goalIndex;
131

132

// 排列轉(zhuǎn)化為序數(shù)
133

int arrangeToIndex( int arrange ) {
134

int i, j, k, index = 0, t = 0, d[ 10 ];
135

while ( arrange ) {
136

d[ ++t ] = arrange % 10;
137

arrange /= 10;
138

}
139

for ( i = t; i > 1; --i ) {
140

k = 0;
141

for ( j = 1; j < i; ++j ) {
142

if ( d[ i ] > d[ j ] ) ++k;
143

}
144

index = index * i + k;
145

}
146

return index;
147

}
148

149

// 堆
150

int heap[ L + 4 ], heapIndex[ L + 4 ], heapN;
151

152

void heapUp( int j ) {
153

int i = j / 2, x = heap[ j ];
154

while ( i > 0 ) {
155

if ( state[ heap[ i ] ].f <= state[ x ].f ) break;
156

heapIndex[ heap[ j ] = heap[ i ] ] = j;
157

j = i;
158

i = j / 2;
159

}
160

heapIndex[ heap[ j ] = x ] = j;
161

}
162

163

void heapDown( int i ) {
164

int j = i + i, x = heap[ i ];
165

while ( j <= heapN ) {
166

if ( ( j < heapN ) && ( state[ heap[ j ] ].f > state[ heap[ j + 1 ] ].f ) ) ++j;
167

if ( state[ x ].f <= state[ heap[ j ] ].f ) break;
168

heapIndex[ heap[ i ] = heap[ j ] ] = i;
169

i = j;
170

j = i + i;
171

}
172

heapIndex[ heap[ i ] = x ] = i;
173

}
174

175

int heapPop() {
176

int x = heap[ 1 ];
177

heapIndex[ heap[ 1 ] = heap[ heapN-- ] ] = 1;
178

if ( heapN > 1 ) {
179

heapDown( 1 );
180

}
181

return x;
182

}
183

184

void heapAdd( int x ) {
185

++heapN;
186

heapIndex[ heap[ heapN ] = x ] = heapN;
187

heapUp( heapN );
188

}
189

190

// 計(jì)算狀態(tài)的 h 函數(shù)
191

int calcH( int arrange ) {
192

int p, i, h = 0;
193

for ( i = 8; i >= 0; --i ) {
194

p = arrange % 10 - 1;
195

arrange /= 10;
196

h += abs( p % 3 - i % 3 ) + abs( p / 3 - i / 3 );
197

}
198

return h;
199

}
200

201

int input() {
202

int ch, i;
203

start = goal = 0;
204

for ( i = 0; i < 9; ++i ) {
205

do {
206

ch = getchar();
207

} while ( ( ch != EOF ) && ( ( ch < '1' ) || ( ch > '8' ) ) && ( ch != 'x' ) );
208

if ( ch == EOF ) return 0;
209

if ( ch == 'x' ) start = start * 10 + 9;
210

else start = start * 10 + ch - '0';
211

goal = goal * 10 + i + 1;
212

}
213

return 1;
214

}
215

216

// 判斷是否無(wú)解
217

int noAns() {
218

int a = start, d[ 10 ], t = 0, sum = 0, i, j;
219

while ( a ) {
220

d[ t++ ] = a % 10;
221

a /= 10;
222

}
223

for ( i = 1; i < t; ++i )
224

for ( j = 0; j < i; ++j )
225

if ( ( d[ i ] > d[ j ] ) && ( d[ i ] != 9 ) ) ++sum;
226

return sum % 2;
227

}
228

229

char choice[ 4 ];
230

int nextIndex[ 4 ];
231

void next( int arrange ) {
232

static int DI[] = { 0, 1, 0, -1 };
233

static int DJ[] = { 1, 0, -1, 0 };
234

static char DC[] = { 'l', 'u', 'r', 'd' };
235

static int p[ 3 ][ 3 ];
236

int i, j, i0, j0, x, y, k;
237

for ( i = 0; i < 3; ++i )
238

for ( j = 0; j < 3; ++j ) {
239

p[ i ][ j ] = arrange % 10;
240

arrange /= 10;
241

if ( p[ i ][ j ] == 9 ) {
242

i0 = i;
243

j0 = j;
244

}
245

}
246

for ( k = 0; k < 4; ++k ) {
247

i = i0 + DI[ k ];
248

j = j0 + DJ[ k ];
249

if ( ( i >= 0 ) && ( i < 3 ) && ( j >= 0 ) && ( j < 3 ) ) {
250

p[ i0 ][ j0 ] = p[ i ][ j ];
251

p[ i ][ j ] = 9;
252

arrange = 0;
253

for ( x = 2; x >= 0; --x )
254

for ( y = 2; y >= 0; --y )
255

arrange = arrange * 10 + p[ x ][ y ];
256

p[ i ][ j ] = p[ i0 ][ j0 ];
257

x = nextIndex[ k ] = arrangeToIndex( arrange );
258

choice[ k ] = DC[ k ];
259

if ( state[ x ].arrange == 0 ) {
260

state[ x ].arrange = arrange;
261

state[ x ].h = calcH( arrange );
262

}
263

}
264

else {
265

nextIndex[ k ] = -1;
266

}
267

}
268

}
269

270

int astar() {
271

int i, j, k, ng, nf;
272

if ( noAns() ) return 0;
273

startIndex = arrangeToIndex( start );
274

goalIndex = arrangeToIndex( goal );
275

if ( start == goal ) return 1;
276

277

memset( state, 0, sizeof(state) );
278

state[ startIndex ].arrange = start;
279

state[ startIndex ].flag = 1;
280

state[ startIndex ].g = 0;
281

state[ startIndex ].h = state[ startIndex ].f = calcH( start );
282

heapN = 0;
283

heapAdd( startIndex );
284

while ( heapN > 0 ) {
285

i = heapPop();
286

if ( i == goalIndex ) return 1;
287

state[ i ].flag = -1;
288

ng = state[ i ].g + 1;
289

next( state[ i ].arrange );
290

for ( k = 0; k < 4; ++k ) {
291

j = nextIndex[ k ];
292

if ( j < 0 ) continue;
293

nf = ng + state[ j ].h;
294

if ( ( state[ j ].flag == 0 ) || ( ( state[ j ].flag == 1 ) && ( nf < state[ j ].f ) ) ) {
295

state[ j ].preIndex = i;
296

state[ j ].choice = choice[ k ];
297

state[ j ].g = ng;
298

state[ j ].f = nf;
299

if ( state[ j ].flag > 0 ) {
300

heapUp( heapIndex[ j ] );
301

heapDown( heapIndex[ j ] );
302

}
303

else {
304

heapAdd( j );
305

state[ j ].flag = 1;
306

}
307

}
308

}
309

}
310

return 0;
311

}
312

313

void output() {
314

int i, top = -1;
315

char stack[ 1000 ];
316

for ( i = goalIndex; i != startIndex; i = state[ i ].preIndex ) {
317

stack[ ++top ] = state[ i ].choice;
318

}
319

for ( i = top; i >= 0; --i ) {
320

printf( "%c", stack[ i ] );
321

}
322

printf( "\n" );
323

}
324

325

int main() {
326

while ( input() ) {
327

if ( astar() ) output();
328

else printf( "unsolvable\n" );
329

}
330

return 0;
331

}
332

posted on 2012-06-05 15:06 coreBugZJ 閱讀(2690) 評(píng)論(4) 編輯收藏引用所屬分類(lèi): ACM 、Algorithm 、課內(nèi)作業(yè) 、Intelligence

Feedback

# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight 2012-10-23 20:56 soulmachine

static int DI[] = { 0, 1, 0, -1 };
static int DJ[] = { 1, 0, -1, 0 };
static char DC[] = { 'l', 'u', 'r', 'd' };

回復(fù) 更多評(píng)論

# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight 2012-10-23 20:57 soulmachine

這三個(gè)變量對(duì)應(yīng)關(guān)系是不是弄反了，不如向左移動(dòng)，應(yīng)該對(duì)應(yīng)的是 0,-1吧？回復(fù) 更多評(píng)論

# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight 2012-10-23 20:58 soulmachine

這三個(gè)變量對(duì)應(yīng)關(guān)系是不是弄反了，比如向左移動(dòng)，應(yīng)該對(duì)應(yīng)的是 0,-1吧？
回復(fù) 更多評(píng)論

# re: A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight 2012-10-23 21:11 soulmachine

看明白了，input()函數(shù)本來(lái)就是反的，跟直覺(jué)相反，-_-||| 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。


相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營(yíng)技術(shù)類(lèi)職位在線測(cè)試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問(wèn)題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

<ins id="pjuwb"></ins>

<blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

<noscript id="pjuwb"></noscript>

<sup id="pjuwb"><pre id="pjuwb"></pre></sup>

<dd id="pjuwb"></dd>

<abbr id="pjuwb"></abbr>

国产精品二区在线观看| 亚洲一区二区在线| 亚洲欧美国产一区二区三区| 在线日韩精品视频| 国外成人网址| 影音先锋一区| 亚洲区第一页| 一二三四社区欧美黄| 日韩一级不卡| 亚洲图中文字幕| 亚洲一区二区三区中文字幕| 夜夜嗨av一区二区三区| 欧美国产激情| 欧美四级在线| 国产乱肥老妇国产一区二| 国产欧美综合在线| 一区二区在线观看视频| 亚洲美女性视频| 欧美一区二区播放| 久久一区亚洲| 999亚洲国产精| 午夜久久久久久| 巨乳诱惑日韩免费av| 欧美日韩国产美女| 欧美日韩一区二区欧美激情| 国产精品日韩二区| 91久久精品视频| 香蕉成人啪国产精品视频综合网| 久久久久久久波多野高潮日日| 欧美日韩三区四区| 国产欧美日韩综合精品二区| 在线国产亚洲欧美| 欧美一级欧美一级在线播放| 欧美成人久久| 亚洲欧美另类综合偷拍| 嫩模写真一区二区三区三州| 国产精品午夜视频| 在线亚洲成人| 久久综合网色—综合色88| 99精品国产一区二区青青牛奶| 欧美一区二区大片| 美日韩在线观看| 亚洲天堂成人在线视频| 久热精品视频在线观看| 国产区二精品视| 亚洲一区二区三区四区五区黄| 亚洲人体大胆视频| 午夜在线不卡| 99精品福利视频| 久久久久国产精品厨房| 国产精品一二三四| 国产精品99久久久久久宅男 | 在线免费观看日本欧美| 亚洲美女区一区| 免费亚洲一区二区| 久久国产日韩| 国产亚洲欧洲| 久久精品一区四区| 亚洲制服少妇| 国产精品网站在线| 国产精品一区二区黑丝| 亚洲夜间福利| 日韩一级二级三级| 欧美剧在线免费观看网站| 最新中文字幕亚洲| 亚洲第一黄网| 国产精品婷婷午夜在线观看| 一区二区三区四区五区视频| 亚洲第一综合天堂另类专| 久久久久久亚洲精品杨幂换脸 | 最新成人av网站| 久久精品一区二区三区中文字幕| 亚洲欧美一区二区精品久久久| 一区二区三区四区五区视频| 久久综合色8888| 亚洲欧洲精品一区二区三区波多野1战4| 亚洲国产日韩一区| 久久精品伊人| 美女精品一区| 日韩视频免费大全中文字幕| 亚洲人成人99网站| 欧美日韩国产在线观看| 亚洲亚洲精品三区日韩精品在线视频| 欧美一级播放| 亚洲私人影院| 国产在线日韩| 亚洲风情亚aⅴ在线发布| 久久一区激情| 这里只有精品视频在线| 亚洲欧美日本日韩| 国内外成人在线| 欧美在线不卡视频| 可以看av的网站久久看| 亚洲精品一区二区三区婷婷月| 先锋影音国产一区| 欧美一区二区三区日韩| 在线精品国精品国产尤物884a| 中文日韩在线| 久久国产精品一区二区| 在线欧美日韩| 亚洲视频第一页| 一区在线免费| 亚洲一区二区三区视频播放| 亚洲国产日韩欧美在线99| 亚洲欧美日韩在线一区| 日韩视频精品| 免费观看久久久4p| 久久精品国产免费看久久精品 | 欧美成人精品一区| 午夜精品福利电影| 欧美黄在线观看| 美女精品国产| 国产一区激情| 亚洲女女女同性video| 99精品热视频只有精品10| 久久蜜桃香蕉精品一区二区三区| 国产精品入口夜色视频大尺度 | 亚洲欧美日韩国产中文| 欧美成人午夜激情在线| 亚洲尤物精选| 这里只有精品视频| 免费久久精品视频| 亚洲一区图片| 欧美高清视频在线播放| 欧美一区亚洲| 欧美性猛片xxxx免费看久爱| 欧美v国产在线一区二区三区| 在线一区二区三区四区| 尤物精品在线| 亚洲免费影院| 一本色道**综合亚洲精品蜜桃冫| 亚洲国产三级在线| 国产精品一区二区三区久久久| 亚洲精品女av网站| 香蕉久久精品日日躁夜夜躁| 亚洲国内在线| 性欧美xxxx大乳国产app| 性一交一乱一区二区洋洋av| 欧美高清视频免费观看| 久久久五月天| 国产日韩精品在线观看| 亚洲美女91| 亚洲欧美日本伦理| 欧美日韩国产黄| 91久久久亚洲精品| 最新日韩在线| 欧美成人午夜影院| 亚洲精选在线| 99视频精品| 欧美精品午夜| 性欧美暴力猛交另类hd| 麻豆精品视频在线观看| 亚洲一区二区三区四区在线观看 | 久久久av毛片精品| 亚洲欧美在线高清| 免费成人小视频| 久久综合精品国产一区二区三区| 欧美成人激情视频| 美女在线一区二区| 国产一区二区三区自拍| 中文成人激情娱乐网| 亚洲一区久久久| 国产精品黄视频| 亚洲影院色无极综合| 欧美影院成年免费版| 有码中文亚洲精品| 免费在线播放第一区高清av| 欧美www视频在线观看| 亚洲经典在线| 久久精品国产亚洲5555| 亚洲欧洲中文日韩久久av乱码| 国产精品久久二区| 亚洲一级一区| 久久综合色影院| 国产精品一区二区三区观看| 午夜欧美精品久久久久久久| 久久久久9999亚洲精品| 在线看成人片| 欧美日韩午夜精品| 亚洲欧美在线视频观看| 在线观看日韩国产| 欧美凹凸一区二区三区视频| 最新日韩在线| 久久狠狠亚洲综合| 香蕉av777xxx色综合一区| 亚洲一区二区成人| 日韩一区二区精品葵司在线| 国产精品日韩电影| 久久久久99| 91久久一区二区| 亚洲欧美国产另类| 91久久线看在观草草青青| 欧美日韩色综合| 欧美在线播放高清精品| 欧美激情免费观看| 免费在线一区二区| 亚洲影视九九影院在线观看| 国产伊人精品| 欧美手机在线| 欧美人在线视频|

<output id="hxklc"></output>

<button id="hxklc"></button>

<label id="hxklc"></label><label id="hxklc"></label>