第二篇：人工智能-八数码难题

**********大学信息工程与自动化学院学生实验报告

（ 20## — 2013  学年第 1 学期）

课程名称：人工智能  开课实验室：信自楼442               2012 年10月 24日

一、上机目的及内容

1.上机内容

用确定性推理算法求解教材65-66页介绍的八数码难题。

2.上机目的

（1）复习程序设计和数据结构课程的相关知识，实现课程间的平滑过渡；

（2）掌握并实现在小规模状态空间中进行图搜索的方法；

（3）理解并掌握图搜索的技术要点。

二、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）设计并实现程序，求解出正确的解答路径；

（2）对所设计的算法采用大O符号进行时间复杂性和空间复杂性分析；

（3）对一般图搜索的技术要点和技术难点进行评述性分析。

程序流程图：

 

三、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++6.0软件

四、实验方法、步骤（或：程序代码或操作过程） 

#include    <stdlib.h>

#include    <stdio.h>

typedef struct Node {

    int num[9]; //棋盘状态

    int deepth; //派生的深度 g(n)

    int diffnum; //不在位的数目 h(n)

    int value; //耗散值 f(n)=g(n)+h(n)

    struct Node * pre;

    struct Node * next;

    struct Node * parent;

}numNode;                //end of struct numNode

int origin[9]; //棋盘初始状态

int target[9]; //棋盘目标状态

int numNode_num,total_step;

numNode *open,*close; //Open表和Close表

numNode *create_numNode()

{

    return (numNode *)malloc(sizeof(numNode));

}

numNode *open_getfirst(numNode *head); //返回第一项，并从Open表中删除

void open_insert(numNode *head,numNode *item); //向Open表中按序插入新节点

void close_append(numNode *head,numNode *item); //向Close表中插入新节点

http://www.xakss.com 锁具安装

http://www.xakss.cn 锁具维修

http://www.xaksss.cn 安全管家

int expand(numNode *item); //扩展节点

int print_result(numNode *item); //打印结果

numNode *copy_numNode(numNode *orgin);

char isNewNode(numNode *open,numNode *close,int num[9]);

                                                //是否在Open表或Close表中

void print_num(int num[9]); //打印棋盘状态

int diff(int num[9]); //求不在位棋子的个数

void init(); //初始化，获得棋盘初始状态和目标状态

void swap(int *a,int *b);

int operate(int num[],int op);

void free_list(numNode *head);

// Name: 主函数

int main(int argc,char*argv[])

{                                 //初始化Open表和Close表

    open=create_numNode();

    close=create_numNode();

    open->pre=open->next=close->pre=close->next=NULL;

    init();   //由用户输入初始和目标状态

  

    numNode *p1;    //初始化初始节点

    p1=create_numNode();

    p1->parent=NULL;

    p1->deepth=0;

       int i=0;

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

       {

        p1->num[i]=origin[i];

    }

    open_insert(open,p1);

    numNode_num=1;

    p1=open_getfirst(open);

    while (p1!=NULL)

       {

        close_append(close,p1);

        if(expand(p1))

            return EXIT_SUCCESS;

        p1=open_getfirst(open);

    }

    printf("No solution!\n");

    return EXIT_SUCCESS;

}              

   

void init ( ) //初始化

{

    while(1)

    {

              printf("                               八数码程序                     \n  ");

              printf("---------------------------------------------------------------------\n");

              char temp[10];

              printf("   请输入初始状态: ");

        scanf("%s",&temp);

        int i=0;

        for ( i=0;i<9 && temp[i]-'0'>=0 && temp[i]-'0'<=8; i++)

           {

            origin[i]=temp[i]-'0';

        }

        printf(" \n ");

        printf("   请输入目标状态:  ");

        scanf("%s",&temp);

        int j=0;

        for ( j=0; j<9 && temp[j]-'0'>=0 && temp[j]-'0'<=8; j++)

         {

            target[j]=temp[j]-'0';

        }

        system("cls");

        if ( i==9&&j==9)

        {

            break;

        }

    }

}        // end of function init

void open_insert (numNode *head,numNode *item)

{

    numNode *p,*q;

    p=head->next;

    q=head;

    while ( p!=NULL && item->value > p->value )

       {

        q=p;

        p=p->next;

    }

    q->next=item;

    item->pre=q;

    item->next=p;

    if(p!=NULL)

    {

        p->pre=item;

    }

}        /* ----- end of function open_insert ----- */

   

numNode * open_getfirst (numNode *head)

{

    numNode *p;

    if ( head->next == NULL )

       {

        return NULL;

    }

    p=head->next;

    head->next=p->next;

    if ( p->next != NULL )

       {

        p->next->pre=head;

    }

    p->pre=NULL;

    p->next=NULL;

    return p;

}        /* ----- end of function open_getfirst ----- */

   

void close_append (numNode *head,numNode *item)

{

    item->next=head->next;

    item->pre=head;

    head->next=item;

    if ( item->next!=NULL )

       {

        item->next->pre=item;

    }

}        /* ----- end of function close_append ----- */

   

int expand (numNode *p1)

{

    numNode * p2;

    int op=1;

    for ( op=1; op<=4; op++)

       {

        p2=copy_numNode(p1);

        operate(p2->num,op);

        if(isNewNode(open,close,p2->num)=='N')

        {

            p2->parent=p1;

            p2->deepth=p1->deepth+1;

            p2->diffnum=diff(p2->num);

            p2->value=p2->deepth+p2->diffnum;

            if(p2->diffnum==0)

            {

                total_step=print_result(p2);

                printf("Total step: %d\n",total_step);

                free_list(open);

                free_list(close);

                return 1;

            }

            else

            {

                numNode_num++;

                open_insert(open,p2);

            }

        }

        else

            free(p2);

    }

    return 0;

}        /* ----- end of function expand ----- */

   

int operate(int m[], int op)

{

    int blank;

    blank=0;

    while (m[blank]!=0 && blank<9 )

        ++blank;

    if (blank==9)

        return 1;

    switch (op) {

        case 1: /* up */

            if (blank>2)

                swap(m+blank,m+blank-3);

            break;

        case 2: /* down */

            if (blank<6)

                swap(m+blank,m+blank+3);

            break;

        case 3: /* left */

            if (blank!=0 && blank!=3 && blank!=6)

                swap(m+blank,m+blank-1);

            break;

        case 4: /* right */

            if (blank!=2 && blank!=5 && blank!=8)

                swap(m+blank,m+blank+1);

            break;

        default : return 1;

    }

    return 0;

}

  

void swap(int *a, int *b)

{

    int c;

    c=*a;

    *a=*b;

    *b=c;

}

    numNode *

copy_numNode (numNode *origin)

{

    numNode *p;

    p=create_numNode();

    p->deepth=origin->deepth;

    p->diffnum=origin->diffnum;

    p->value=origin->value;

    int i;

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

       {

        (p->num)[i]=(origin->num)[i];

    }

    return p;

}        /* ----- end of function copy_numNode ----- */

  

int diff (int num[9])

{

    int i,diffnum=0;

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

        if(num[i]!=target[i])

            diffnum++;

    return diffnum;

}        /* ----- end of function diff ----- */

    char

isNewNode (numNode *open,numNode *close,int num[9])

{

    numNode *p;

    int i=0;

    p=open->next;   

    while ( p!=NULL )

    {

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

         {

            if(p->num[i]!=num[i])

                break;

        }

        if(i==9)

            return 'O'; //Open

        p=p->next;

    }

    p=close->next;

    while ( p!=NULL )

       {

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

        {

            if(p->num[i]!=num[i])

                break;

        }

        if(i==9)

            return 'C'; //Close

        p=p->next;

    }

    return 'N';

}        /* ----- end of function isNewNode ----- */

   

void free_list (numNode *head)

{

    numNode *p,*q;

    p=head->next;

    while ( p!=NULL )

       {

        q=p->next;

        free(p);

        p=q;

    }

    free(head);

}        /* ----- end of function free_list ----- */

void print_num (int num[9])

{   

    int i;

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

       {

        printf("  %d\t",num[i]);

        if((i%3)==2)

            printf("\n");

    }

}        /* ----- end of function print_num ----- */

  

int print_result ( numNode *item)

{

    numNode *p;

    int step;

    p=item;

    if(p!=NULL)

    {

        step=print_result(p->parent);

        printf("\nStep %d:\n",step+1);

        print_num(p->num);

        return step+1;

    }

    else

    {

        return -1;

    }

}  

五、实验过程原始记录( 测试数据、图表、计算等)

输入要解决的数据串 213654870

还要输入目标数据串 123804765

最后通过20步的广度优先算法排序可得到结果如下：

 

 

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

    在老师动手给我们编程演示一次后，我多次看过老师的代码，明白其中的流程和思路，用C语言写了一个，和老师的相比相差甚远啊。我们通过这次实验有效地复习了数据结构的相关的知识，为以后的学习和研究做了先前的准备，这一点非常的开心，但是该问题我们编程还是有一定的困难，需要我们以后多加的复习相关的语言知识，努力的坚强的的编程，多读代码。

由上面的结果,通过和其它的算法比较,我得出了以下结论对广度优先算法进行归纳:

广度优先搜索法在有解的情形总能保证搜索到最短路经，也就是移动最少步数的路径。但广度优先搜索法的最大问题在于搜索的结点数量太多，因为在广度优先搜索法中，每一个可能扩展出的结点都是搜索的对象。随着结点在搜索树上的深度增大，搜索的结点数会很快增长，并以指数形式扩张，从而所需的存储空间和搜索花费的时间也会成倍增长。在进行广度搜索时候，将父结点所在的数组索引记录在子结点中了，所以得到目标排列的时候，我们只要从子结点逆向搜索就可以得到最优搜索路径了。

通过上机，我们学到了不少的知识，理论上想的和实际是不一样的，我们要学好人工智能首先要学好数据结构，数据结构和C、C++语言都是一门基础性的课程，需要把理论变为实践，我们一定要把基础打好，几乎每一样与计算机相关的考试都有数据结构，所以更应该好好学习。上机使我们温故了C++的知识，虽然它有一定的难度，但只要我们用心去做，一定可以做好的，心有多大舞台就有做大。从此数据结构变得不再那么陌生了，首先从看别人程序到自己尝试着编，然后不断地调整，问同学，网上查，最后终于成功了，但是感觉自己的知识还是很少，需要多加的努力，更加的投入学习，只要用心，人工智能是能学好的。

注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。