东莞网站建设 牛魔网/seo优化教程
1 问题描述
拼图游戏，通常简单的也叫做八数码问题，就是解决如何通过移动有限的步数，从图的一个状态移动到另外一个状态，如下面的图所示：
2 问题解决的思路
一个简单的思路就是采取广度优先搜索算法，算法思路如下所示：
把起始状态图存储在哈希表中；
把起始状态加入队列当中；
循环判断当前状态是否等于结束状态
从队列中取出元素
寻找所有可以移动的操作，产生新状态X
若新位置状态X不在哈希表中
将X加入队列和哈希表
3 算法的实现
Puzzle.h
/*************************************************************************************/
/*"NITE and DAY" Puzzle */
/*************************************************************************************//*Special symbols.*/
#define SymbolBlank '.' /*Symbol that denotes a blank square.*/
#define SymbolFixed '$' /*Symbol that cannot move.*//*Board dimensiona.*/
#define BoardHeight 3
#define BoardWidth 4
#define BoardSize 12/*Start position.*/
/* N I T E */
/* $ . $ . */
/* D A Y . */
#define StartBoard "NITE$.$.DAY."/*Goal position.*/
/* D A Y . */
/* $ . $ . */
/* N I T E */
#define GoalBoard "DAY.$.$.NITE"/*Number of moves in a minimal length solution for this puzzle,*/
/* where one move is defined as s moving a piece vertically or horizontally*/
/* to an adjacent unoccupied square (and the SymbolFixed piece cannot move).*/
#define MinSolution 66/*Data structure parameters.*/
#define QueueArraySize 50000 /*Queue goes from 0 to QueueArraySize-1.*/
#define HashArraySize 1000003 /*Hash table goes from 0 to HashArraySize-1.*/
#define HashStatsMAX 50 /*Max number of hash bucket size statistics to keep.*/Output.h
/*Output a position; takes 4 arguments:*POS: String that lists pieces in row major order.step: The step number (ignore next two args when step=0).piece: Piece that moved.dir: Direction that the piece moved; 0=north, 1=east, 2=south, 3=west.*/
void OutputPosition(char *POS, int step, char piece, int dir) {
static char *DirectionString[4] = {"north", "east", "south", "west"};
int i;
printf("\nStep %d",step);
if (step>0) printf(", move %c %s",piece,DirectionString[dir]);
printf(":\n");
for (i=0; i<BoardSize; i++) {printf("%c",POS[i]);if ( (i%BoardWidth) == (BoardWidth-1) ) printf("\n"); else printf(" ");}
}/*Utility function to make a positive integer into a string with commas.*/
char *MakeString(int n) {
static int block[100];
static char s[100], *x;
int i=-1, j;
do {block[++i] = n%1000; n /= 1000;} while (n>0);
sprintf(s,"%d",block[i]);
if (block[i]<10) x=s+1; else if (block[i]<100) x=s+2; else x=s+3;
for (j=(i-1); j>=0; j--) {if (block[j]<10) sprintf(x,",00%d",block[j]);else if (block[j]<100) sprintf(x,",0%d",block[j]);else sprintf(x,",%d",block[j]);x += 4;}
sprintf(x,"%c",'\0');
return(s);
}/*Print queue statistics.*/
void QueueStats(int Qarray, int Qmax, int Qfront, int Qrear) {
printf("\nQueue statistics:\n");
printf(" Queue array size: %s\n", MakeString(Qarray));
printf(" Max positions ever in queue: %s\n", MakeString(Qmax));
printf(" Index of Qfront: %s\n", MakeString(Qfront));
printf(" Index of Qrear: %s\n", MakeString(Qrear));
printf(" |Qfront-Qrear| = %s\n", MakeString(abs(Qfront-Qrear)));
}/*Print hash statistics.*/
void HashStats(int Harray, int Hcount, int Hmax) {
printf("\nHash table statistics:\n");
printf(" Hash array size: %s\n", MakeString(Harray));
printf(" No. positions in hash table: %s\n", MakeString(Hcount));
printf(" Max bucket size: %s\n", MakeString(Hmax));
printf("\nHash buckets at the end:\n");
}/*Print number of buckets of given size.*/
/*Call this function once for each bucket size, startiing at 0 and going*/
/* up to the maximum bucket size (the Hmax argument to HashStats).*/
void BucketStat(int Bsize, int Bcount) {
printf(" buckets of size %d = %s\n", Bsize, MakeString(Bcount));
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include "Puzzle.h"
#include "Output.h"/*Position data type.*/
typedef struct pnode
{struct pnode *next; /*next pointer for the hash bucket*/struct pnode *back; /*position from which this one came*/int cost; /*number of moves to get to this position*/char piece; /*piece that moved to this position*/int dir; /*direction moved to enter this position*/char board[BoardSize]; /*this position's board*/
} PositionBody;
typedef PositionBody *TypePosition;/*Queue data type.*/
typedef struct Queue_
{unsigned int head;unsigned int tail;TypePosition arr[QueueArraySize];
}Queue;
typedef Queue* TypeQueue;typedef struct List_
{TypePosition pos;struct List_* next;
}List;enum Move { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 };void initQueue();
void initHash();
void initStartPos();
void enqueue(TypePosition pos);
void runGame();
TypePosition dequeue();
TypePosition newPosition();
List* newList();
unsigned int hash(char* str);
void copyStr(char* str1, char* str2);
int cmpStr(char* str1, char* str2);
TypePosition insertPos(char* str, char piece, int direct, int cost, TypePosition back);
void printResult(TypePosition p);
void statisticQueue();
void statisticHash(char* str);
void clearHash();List hashTable[HashArraySize];
Queue ques;
char start[BoardSize] = StartBoard;
char goal[BoardSize] = GoalBoard;
unsigned int maxQueueNum = 0;
unsigned int QueueNum = 0;
unsigned int hashNum[HashArraySize];
unsigned int maxBucketSize;int main() {initHash();initQueue();initStartPos();runGame();clearHash();//system("pause");return 0;
}void initQueue()
{ques.head = 0;ques.tail = 0;
}void initHash()
{for (int i = 0; i < HashArraySize; i++){hashTable[i].pos = NULL;hashTable[i].next = NULL;}
}void initStartPos()
{TypePosition startPos = insertPos(start, 0, 0, -1, NULL);enqueue(startPos);
}void enqueue(TypePosition pos)
{if (pos == NULL)return;unsigned int newTail = (ques.tail + 1) % QueueArraySize;if (newTail == ques.head){printf("queue overflow!!!");clearHash();exit(1);}else{ques.arr[ques.tail] = pos;ques.tail = newTail;QueueNum++;if (maxQueueNum < QueueNum)maxQueueNum = QueueNum;}
}void runGame()
{while (1){TypePosition p = dequeue();if (p == NULL)return;if (cmpStr(goal, p->board)){//over;printResult(p);statisticQueue();statisticHash(p->board);return;}for (int i = 0; i < BoardSize; i++){int x = i % BoardWidth;int y = i / BoardWidth;int dx[4] = { 0,1,0,-1 };int dy[4] = { -1,0,1,0 };for (int k = 0; k < 4; k++){int newx = x + dx[k];int newy = y + dy[k];if (newx >= 0 && newx < BoardWidth && newy >= 0 && newy < BoardHeight && p->board[i] != SymbolFixed && p->board[i] != SymbolBlank){int newIndex = newy * BoardWidth + newx;if (p->board[newIndex] == SymbolBlank){char newCs[BoardSize] = { 0 };copyStr(newCs, p->board);newCs[i] = SymbolBlank;newCs[newIndex] = p->board[i];TypePosition next = insertPos(newCs, p->board[i], k, p->cost, p);enqueue(next);}}}}}
}TypePosition dequeue()
{//judge if empty queueif (ques.head == ques.tail)return NULL;//return the head elementunsigned int head = ques.head;ques.head = (ques.head + 1) % QueueArraySize;QueueNum--;return ques.arr[head];
}unsigned int hash(char* str)
{unsigned int seed = 131; // 31 131 1313 13131 131313 etc..unsigned int hash = 0;unsigned int cnt = BoardSize;while (cnt--){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF) % HashArraySize;
}TypePosition insertPos(char* str, char piece, int direct, int cost, TypePosition back)
{unsigned int key = hash(str);//the first element in key's bucketif (hashTable[key].pos == NULL){TypePosition ppos = newPosition();ppos->back = back;ppos->next = NULL;ppos->cost = cost + 1;ppos->dir = direct;ppos->piece = piece;copyStr(ppos->board, str);hashTable[key].pos = ppos;hashNum[key]++;return ppos;}//the key's bucket is not emptyList* p = hashTable + key;List* q = p;while (p != NULL){if (cmpStr(p->pos->board, str))return NULL;q = p;p = p->next;}TypePosition ppos = newPosition();ppos->back = back;ppos->next = NULL;ppos->cost = cost + 1;ppos->dir = direct;ppos->piece = piece;copyStr(ppos->board, str);List* newNode = newList();newNode->pos = ppos;newNode->next = NULL;q->next = newNode;//increase the key's biggest bucket sizehashNum[key]++;if (maxBucketSize < hashNum[key])maxBucketSize = hashNum[key];return ppos;
}void printResult(TypePosition p)
{if (p->cost == 0){OutputPosition(p->board, p->cost, p->piece, p->dir);return;}else if (p->cost > 0)printResult(p->back);OutputPosition(p->board, p->cost, p->piece, p->dir);}void copyStr(char* str1, char* str2)
{for (int i = 0; i < BoardSize; i++){str1[i] = str2[i];}
}TypePosition newPosition() {TypePosition p = (TypePosition)malloc(sizeof(PositionBody));if (p == NULL) {printf("Malloc for a new position failed.");clearHash();exit(1);}return p;
}List* newList()
{List* p = (List*)malloc(sizeof(List));if (p == NULL) {printf("Malloc for a new List node failed.");clearHash();exit(1);}return p;
}int cmpStr(char* str1, char* str2)
{for (int i = 0; i < BoardSize; i++){if (str1[i] != str2[i])return 0;}return 1;
}void statisticQueue()
{QueueStats(QueueArraySize, maxQueueNum, ques.head, ques.tail);
}
void statisticHash(char* str) {unsigned int key = hash(str);HashStats(HashArraySize, key, maxBucketSize);//int* arrSize = (int*)malloc(sizeof(int) * (maxBucketSize + 1));int* arrSize = (int*)calloc(maxBucketSize + 1, sizeof(int));for (unsigned int i = 0; i < HashArraySize; i++){arrSize[hashNum[i]]++;}for (int i = 0; i <= maxBucketSize; i++){BucketStat(i, arrSize[i]);}free(arrSize);}void clearHash()
{for (int i = 0; i < HashArraySize; i++){if (hashTable[i].pos != NULL){List* node = hashTable + i;free(node->pos);node = node->next;while (node != NULL){List* p = node->next;free(node->pos);free(node);node = p;}}}
}
Step 0:
N I T E
$ . $ .
D A Y .
Step 1, move I south:
N . T E
$ I $ .
D A Y .
Step 2, move N east:
. N T E
$ I $ .
D A Y .
Step 3, move Y east:
. N T E
$ I $ .
D A . Y
......
Step 63, move E south:
D A Y .
$ . $ E
N . I T
Step 64, move I west:
D A Y .
$ . $ E
N I . T
Step 65, move T west:
D A Y .
$ . $ E
N I T .
Step 66, move E south:
D A Y .
$ . $ .
N I T E
Queue statistics:
Queue array size: 50,000
Max positions ever in queue: 35,919
Index of Qfront: 4,797
Index of Qrear: 4,800
|Qfront-Qrear| = 3
Hash table statistics:
Hash array size: 1,000,003
No. positions in hash table: 652,885
Max bucket size: 7
Hash buckets at the end:
buckets of size 0 = 546,392
buckets of size 1 = 330,171
buckets of size 2 = 99,613
buckets of size 3 = 20,372
buckets of size 4 = 3,030
buckets of size 5 = 387
buckets of size 6 = 34
buckets of size 7 = 4