| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 8032 人关注过本帖, 6 人收藏
标题:数字16拼图游戏完成版--带通关演示功能
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 10楼 xzlxzlxzl
不必先去弄最优解啊~弄个其中一个解出来就已经很强大了~~我在你的另一个贴说了一下简单的设想~这只是我的设想而已~现阶段实现不了就不要强求~当我什么都没有说~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-10 00:00
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
https://bbs.bccn.net/thread-455109-1-1.html
搜了个A*算法解八数码~

那个代码要用后缀.cpp运行
为了支持某些旧版编译器我把代码修改了一下(我已经说明了出处)~~

程序代码:
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#define NUM 5 
typedef struct bgMatrix 
{ 
    int v, w; 
    char matrix[NUM][NUM]; 
    int pre; 
    int f; 
    int g; 
    bool isVisited; 
}Matrix; 
typedef struct bgQueue 
{ 
    Matrix* data; 
    int length; 
    int maxLength; 
    int head; 
    int tail; 
}BGQueue; 
typedef BGQueue* Queue; 
typedef struct bgStack 
{ 
    Matrix* data; 
    int top; 
}BGStack; 
typedef BGStack* Stack; 
char srcMatrix[NUM][NUM] = 
{ 
    {'*', '*', '*', '*', '*'}, 
    {'*', '2', '8', '3', '*'}, 
    {'*', '1', '6', '4', '*'}, 
    {'*', '7', '0', '5', '*'}, 
    {'*', '*', '*', '*', '*'} 
}; 
char dstMatrix[NUM][NUM] = 
{ 
    {'*', '*', '*', '*', '*'}, 
    {'*', '1', '2', '3', '*'}, 
    {'*', '8', '0', '4', '*'}, 
    {'*', '7', '6', '5', '*'}, 
    {'*', '*', '*', '*', '*'} 
}; 
int dx[4] = {0, 0, -1, 1}; 
int dy[4] = {1, -1, 0, 0}; 
int cnt = -1; 
Queue queue; 
Stack stack; 
bool astar(Matrix matrix); 
int getG(Matrix matrix); 
void initQueue(int length); 
void putQueue(Matrix matrix); 
Matrix getQueue(void); 
int isQueueEmpty(void); 
int isQueueFull(void); 
void initStack(int length); 
void pushStack(Matrix matrix); 
Matrix popStack(void); 
int isStackEmpty(void); 
int matrixCmp(char src[][NUM], char dst[][NUM]); 
void matrixCpy(char dst[][NUM], char src[][NUM]); 
void matrixPrint(char matrix[][NUM]); 
int main(int argc, char *argv[]) { 
   
    Matrix src; 
   
    initQueue(3628800+1); 
    initStack(3628800+1); 
   
    src.v = 3; 
    src.w = 2; 
    matrixCpy(src.matrix, srcMatrix); 
    src.pre = cnt; 
    src.f = 0; 
    src.g = getG(src); 
    astar(src); 
    return 0; 
} 
bool astar(Matrix matrix) 
{ 
    Matrix t, s; 
   
    int v, w; 
   
    int direction; 
   
    putQueue(matrix); 
   
    while (!isQueueEmpty()) 
    { 
        s = getQueue(); 
       
        cnt++; 
       
        for (direction = 0; direction < 4; direction++) 
        { 
            t = s; 
            v = t.v + dx[direction]; w = t.w + dy[direction]; 
           
            if (srcMatrix[v][w] != '*') 
            { 
                char c = t.matrix[t.v][t.w]; 
                t.matrix[t.v][t.w] = t.matrix[v][w]; 
                t.matrix[v][w] = c; 
               
                t.v = v; 
                t.w = w; 
                t.pre = cnt; 
                t.f = s.f + 1; 
                t.g = getG(t); 
                t.isVisited = false; 
               
                int h = 0;
                for (; h < queue->tail; h++) 
                { 
                    if (matrixCmp(queue->data[h].matrix, t.matrix)) 
                    { 
                        break; 
                    } 
                } 
               
                if (h == queue->tail) 
                { 
                    putQueue(t); 
                   
                    if (matrixCmp(t.matrix, dstMatrix)) 
                    { 
                        pushStack(t); 
                       
                        for (int father = t.pre; !matrixCmp(queue->data[father].matrix, srcMatrix); father = queue->data[father].pre) 
                        { 
                            pushStack(queue->data[father]); 
                        } 
                       
                        puts("PathFind = "); 
                       
                        matrixCpy(t.matrix, srcMatrix); 
                        pushStack(t); 
                       
                        while (!isStackEmpty()) 
                        { 
                            s = popStack(); 
                            matrixPrint(s.matrix); 
                        } 
                       
                        return true; 
                    } 
                } 
            } 
        } 
    } 
   
    return false; 
} 
int getG(Matrix matrix) 
{ 
    int g = 0; 
   
    for (int i = 0; i < NUM; i++) 
    { 
        for (int j = 0; j < NUM; j++) 
        { 
            if (matrix.matrix[i][j] != '*' && matrix.matrix[i][j] != dstMatrix[i][j]) 
            { 
                g++; 
            } 
        } 
    } 
   
    return g; 
} 
void initQueue(int length) 
{ 
    queue =(bgQueue* ) malloc(sizeof(BGQueue)); 
   
    queue->data =(bgMatrix* ) malloc(sizeof(Matrix) * length); 
    queue->length = 0; 
    queue->maxLength = length; 
    queue->head = 0; 
    queue->tail = 0; 
} 
void putQueue(Matrix matrix) 
{ 
    queue->data[queue->tail++] = matrix; 
    queue->tail = queue->tail % queue->maxLength; 
    queue->length++; 
   
    Matrix* a =(bgMatrix* ) malloc(sizeof(Matrix) * queue->maxLength); 
    Matrix* b =(bgMatrix* ) malloc(sizeof(Matrix) * queue->maxLength); 
   
    int an = 0; 
    int bn = 0;
    int i=0;
   
    for (i = 0; i < queue->length; i++) 
    { 
        if (queue->data[i].isVisited) 
        { 
            a[an++] = queue->data[i]; 
        } 
        else 
        { 
            b[bn++] = queue->data[i]; 
        } 
    } 
    for (i = 0; i < bn-1; i++) 
    { 
        for (int j = bn-1; j > i; j--) 
        { 
            int h1 = b[j-1].f + b[j-1].g; 
            int h2 = b[j].f + b[j].g; 
           
            if (h1 > h2) 
            { 
                Matrix t = b[j-1]; 
                b[j-1] = b[j]; 
                b[j] = t; 
            } 
        } 
    } 
   
    for (i = 0; i < an; i++) 
    { 
        queue->data[i] = a[i]; 
    } 
   
    for (i = 0; i < bn; i++) 
    { 
        queue->data[an+i] = b[i]; 
    } 
    free(a); 
    free(b); 
} 
Matrix getQueue(void) 
{ 
    queue->data[queue->head].isVisited = true; 
   
    Matrix ret; 
    ret = queue->data[queue->head++]; 
    queue->head = queue->head % queue->maxLength; 
   
    return ret; 
} 
int isQueueEmpty(void) 
{ 
    return queue->head == queue->tail; 
} 
int isQueueFull(void) 
{ 
    return ((queue->tail+1) % queue->maxLength) == queue->head; 
} 
void initStack(int length) 
{ 
    stack = (bgStack* )malloc(sizeof(BGStack)); 
   
    stack->data =(bgMatrix* ) malloc(sizeof(Matrix) * length); 
    stack->top = 0; 
   
} 
void pushStack(Matrix matrix) 
{ 
    stack->data[stack->top++] = matrix; 
} 
Matrix popStack(void) 
{ 
    Matrix ret; 
    ret = stack->data[--stack->top]; 
   
    return ret; 
} 
int isStackEmpty(void) 
{ 
    return (stack->top == 0); 
} 
int matrixCmp(char src[][NUM], char dst[][NUM]) 
{ 
    int i, j, s, t, ret; 
   
    char srcString[30] = {0}; 
    char dstString[30] = {0}; 
   
    s = 0; 
    t = 0; 
   
    for (i = 0; i < NUM; i++) 
    { 
        for (j = 0; j < NUM; j++) 
        { 
            srcString[s++] = src[i][j]; 
            dstString[t++] = dst[i][j]; 
        } 
    } 
   
    ret = !strcmp(srcString, dstString); 
   
    return ret; 
} 

 
void matrixCpy(char dst[][NUM], char src[][NUM]) 
{ 
    int i, j; 
   
    for (i = 0; i < NUM; i++) 
    { 
        for (j = 0; j < NUM; j++) 
        { 
            dst[i][j] = src[i][j]; 
        } 
    } 
} 
void matrixPrint(char matrix[][NUM]) 
{ 
    char s[60] = {0}; 
   
    int i, j, k; 
   
    k = 0; 
   
    for (i = 0; i < NUM; i++) 
    { 
        for (j = 0; j < NUM; j++) 
        { 
            s[k++] = matrix[i][j]; 
        } 
       
        s[k++] = '\r'; 
        s[k++] = '\n'; 
    } 
   
    s[k++] = '\r'; 
    s[k++] = '\n'; 
   
    puts(s); 
   
}  


[此贴子已经被作者于2017-6-10 04:22编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-10 04:13
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
八数码和数字16完全不在一个数量级好不!8数码只有40320种组合,我一个深度搜索就可以达到目的,如果要得到最优解,我只要写一个4叉树(0的4个方向的运动),留下得到正确结果的路径,找最少节点的那个,很容易实现的,我要写这个,肯定比楼上的代码少且优(捂脸)
数字16有20922789888000种组合,20T的数据容量,即使用虚拟内存,也没有哪个家用级的电脑硬盘存的下,遍历、树是无法完成的,只能是设计一个智能算法,摒弃那些完全达不到目的的树节点,这个智能算法我想不出来。
2017-06-10 06:42
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 13楼 xzlxzlxzl
我的天哪~认真看这个打着A*算法的名义~实质是普通的广搜~~~
运行了那个代码3*3的跑了两三秒才跑出来~
这个数量级别正常的A*算法能在0.1s内跑出答案~虽然不一定是最优解~~~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-06-10 07:07
HOUSAND
Rank: 1
等 级:新手上路
帖 子:4
专家分:5
注 册:2016-8-14
收藏
得分:0 
高手
2017-06-13 19:18
beichei5d
Rank: 4
等 级:业余侠客
威 望:2
帖 子:89
专家分:270
注 册:2016-3-8
收藏
得分:0 
学习了。。

你现在所偷的懒,都将成为以后扇你的巴掌!共勉吧。。。
2017-06-14 15:38
plaodj
Rank: 1
来 自:湖南
等 级:新手上路
帖 子:15
专家分:0
注 册:2008-3-19
收藏
得分:0 
非常不错   很不错的帖子

www.yzqz.cn
2017-06-27 10:47
psy134820
Rank: 1
等 级:新手上路
帖 子:19
专家分:7
注 册:2017-7-5
收藏
得分:0 
回复 楼主 xzlxzlxzl
我复制后发现这一步报错了:void drawmap(unsigned _int64 a,int x,int y)
2017-07-05 19:47
xzlxzlxzl
Rank: 15Rank: 15Rank: 15Rank: 15Rank: 15
来 自:湖北
等 级:贵宾
威 望:125
帖 子:1091
专家分:5825
注 册:2014-5-3
收藏
得分:0 
回复 18楼 psy134820
你可能用的是gcc编译,把代码中的所有“_int64”用“long long”替代即可。
2017-07-06 19:31
psy134820
Rank: 1
等 级:新手上路
帖 子:19
专家分:7
注 册:2017-7-5
收藏
得分:0 
谢谢
2017-07-07 09:51
快速回复:数字16拼图游戏完成版--带通关演示功能
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.039868 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved