奥鹏大工20春《人工智能》大作业题目及要求 - A算法参

参

题    目：    A*算法              

1.谈谈你对本课程学习过程中的心得体会与建议？

人工智能是研究如何利用计算机来模拟人脑所从事的感知、推理、学习、思考、规划等人类智能活动，来解决需要用人类智能才能解决的问题，以延伸人们智能的科学。掌握人工智能的基本概念、基本原理、知识的表示、推理机制和求解技术，以及机器学习的技术方法. 掌握人工智能的一个问题和三大技术，即通用问题求解和知识表示技术、搜索技术、推理技术。

人工智能的定义可以分为两部分，即“人工”和“智能”。“人工”比较好理解，争议性也不大。有时我们会要考虑什么是人力所能及制造的，或者人自身的智能程度有没有高到可以创造人工智能的地步，等等。但总的来说，“人工系统”就是通常意义下的人工系统。关于什么是“智能”，就问题多多了。这涉及到其它诸如意识、自我、思维等等问题。人唯一了解的智能是人本身的智能，这是普遍认同的观点。但是我们对我们自身智能的理解都非常有限，对构成人的智能的必要元素也了解有限，所以就很难定义什么是“人工”制造的“智能”了。                               

2. 《人工智能》课程设计, 从以下5个题目中任选其一作答。

《人工智能》课程设计

题目一：A*算法

要    求：（1）撰写一份word文档，里面包括（算法思路、算法程序框图、重排九宫问题）章节。

（2）算法思路：简单介绍该算法的基本思想，100字左右即可。

（3）算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。

（4）对于重排九宫问题的启发式函数： f (x)= p(x)+3s(x)

p(x)是x结点和目标结点相比每个将牌“离家”的最短距离之和；

s(x)是：每个将牌和目标相比，若该将牌的后继和目标中该将牌的后继不同，则该将牌得2分，相同则该将牌得0分，中间位置有将牌得1分，没将牌得0分。

对于给定的初始格局和目标状态请按此启发式函数给出搜索的状态空间图。

初始格局                           目标状态

答：

一、问题描述

八数码问题作为一个经典的问题被大家所熟知，该问题是求解如何从开始的一个状态（布局）到达目标状态所需步数最少的问题。

问题描述

如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678.

　　把第二个图的局面记为：123.46758

　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。

　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

　　输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

　　输出最少的步数，如果不存在方案，则输出-1。

样例输入

12345678.

123.46758

样例输出

3

样例输入

13524678.

46758123.

样例输出

22

二、流程图

三、问题分析

将每一个状态作为一个结点容易想到可以用广搜的方法解决，这种方法简单，但是就算是加入哈希判重也会搜索很多的无用结点。

我们打算用A*算法解决这个问题，既然确定了用A*算法，那么我们首先应该确定估价函数h(x)，估价函数的选取直接决定A*算法的效率，一般对于八数码问题有三种估价函数的选法：

以不在位的数码的个数为估价函数

以不在位的数码归位所需的最短距离和即曼哈顿距离为估价函数

将逆序对数作为估价函数

可以证明前两种都是乐观估计，最后一种不是，因此前两种都可以作为八数码问题的估价函数，但是你的估计值与真实值越近所需要搜索的状态越少，很明显第一种方法太乐观了（估价函数的选取直接决定算法的效率），因此我们采用第二种方法作为八数码问题的估价函数

解决了估价函数的问题以后，第二个需要解决的问题就是判重，我们首先想到的是用集合set，这种方法最简单，但是很不幸这种方法耗时也是最多的，如果时间要求比较高的话，这种情况很容易超时。这里我们不用这种方法，判重问题自然而然想到的是哈希表，好了现在问题又来了，如何创建哈希表，也就是哈希函数怎么写，这个东西比较有技巧，还好对于这种问题有一种现成的方法解决，那就是康托展开 ，还有一个问题就是有些问题是无解的，这种情况我们不希望进行很大力气的搜索之后发现无解，最好是能提前预知，值得庆幸的是八数码无论怎么移动逆序的奇偶性不变，因此我们可以直接通过O（1）的时间判断开始和目标结点的逆序奇偶性是否相同就可以了。有了上面的分析之后，程序就可以写出来了

/** A*算法解决八数码问题（九宫重排）

     *  程序看起来比较长，核心只有 int Astar(int [][COL],int [][COL],int,int);函数

     *  其它函数供Astar函数调用，起辅助作用，还有几个函数仅仅是为了使界面更友好

     *  所有函数均有注释说明

     *  其中可行性判断函数需要对八数码问题进行数学上的简单分析，

     *  hash函数的设计有些技巧，其他函数的原理都是显然的

     *  程序运行有问题可以和我联系

     */

#include

#include

#include

#include

#include

    #define COL 3

    #define MAXSTEP 70

    using namespace std;

    void output(int[][COL]);/*输出函数*/

    void input(int [][COL]);/*输出函数*/

    int Astar(int [][COL],int [][COL],int,int path[]);/*核心函数，起始，终止，深度，方向*/

    bool eq(int from[][COL],int to[][COL]);/*判断起始与终止是否相同*/

    bool change(int from[][COL],const int i,const int j,const int step);/*判断当前状态是否可以进行相应移动,并进行状态转变*/

    int value(const int from[][COL],const int to[][COL]);/*估价函数*/

    void output_tow(int from[][COL],int to[][COL]);/*输出函数，和上面的outpput函数差不多*/

    bool possible(int from[][COL],int to[][COL]);/*可行性判断*/

    int h[9]={40320,5040,720,120,24,6,2,1,1};/*hash函数用到的数据 8-0的阶乘*/

    bool ha[400000];

    struct Node{

        int path[MAXSTEP]; /*路径信息*/

        int expend;/*权重*/

        int deep;/*深度*/

        int x[COL][COL];/*状态信息*/

    };

    struct cmp{

        bool operator() (const Node A,const Node B){

return A.expend>B.expend;

        }

    };

    int pa[MAXSTEP];

priority_queue,cmp> q;/*优先队列*/

    Node make(int from[][COL],int deep,int v,int path[],int step);/*转换函数*/

    int main()

    {

        int from[COL][COL];

        int to[COL][COL];

        int k=0,c;

        memset(ha,0,sizeof(ha));

        memset(pa,-1,sizeof(pa));

        printf("请按行输入原始九宫格,空白的输入0\\n");

        input(from);

        printf("原始九宫格为：\\n");

        output(from);

        printf("请按行输入目标九宫格,空白的输入0\\n");

        input(to);

        printf("目标九宫格为：\\n");

        output(to);

        printf("按任意键显示执行步骤：\\n");

        fflush(stdin);

        getchar();

        if(!possible(from,to)){

cout<<"目标状态不可达，请换一组数据测试！"<            return 0;

        }

        int d=Astar(from,to,0,pa);

cout<<"最优路径到目标位置需要"< cout<<"当前状态"<<'\'<<"目标状态"<        while((c=pa[++k])!=-1){

            int i,j;/*记录当前状态，白板位置*/

cout<<"第"< for(i=0;i<3;i++)

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

                if(from[i][j]==0)

                    goto o;

            o:

                change(from,i,j,pa[k]);

                output_tow(from,to);

cout<<"--------------------------------------"<        }

        return 0;

    }

    void output(int a[][COL])

    {

        int i,j;

for(i=0;i for(j=0;j        printf("%d ",a[i][j]);

            putchar('\\n');

     }

    }

    void output_tow(int from[][COL],int to[][COL])

    {

        int i,j;

for(i=0;i for(j=0;j                printf("%d ",from[i][j]);

cout<<'\'<<'\';

for(j=0;j                printf("%d ",to[i][j]);

            putchar('\\n');

        }

    }

    void input(int a[][COL])

    {

        int i,j,c;

    s:

        int g[9];

        memset(g,0,sizeof(g));

for(i=0;i for(j=0;j                scanf("%d",&a[i][j]);

                c=a[i][j];

if(g[c]||c<0||c>8){

cout<<"输入有误，请重新输入"<                    goto s;

                }

                g[c]++;

            }

    }

    int Astar(int from[][COL],int to[][COL],int deep,int path[])

    {

        if(eq(from,to)){

            memcpy(pa,path,sizeof(pa));

            return deep;

        }

        int i,j;/*记录当前状态，白板位置*/

        int *a=from[0];

        int b[9];

        int m=0;

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

            b[i]=a[i];

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

for(j=0;j if(b[i]>a[j])

                        b[i]--;

                    m+=h[i]*b[i];

            }

        ha[m]=1;

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

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

            if(from[i][j]==0)

                goto ok;

ok: for(int step=0;step<4;step++){

            if(change(from,i,j,step)){

                int v=value(from,to)+deep+1;

                Node n;

                n=make(from,deep+1,v,path,step);

                q.push(n);

                change(from,i,j,step);

            }

        }

        Node p=q.top();

        int flag=0;

        while(!flag){

            a=p.x[0];

            m=0;

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

                b[i]=a[i];

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

for(j=0;j if(b[i]>a[j])

                        b[i]--;

                m+=h[i]*b[i];

            }

            if(!ha[m]){

                q.pop();

                break;

            }

            q.pop();

            p=q.top();

        }

        return Astar(p.x,to,p.deep,p.path);

    }

    bool eq(int from[][COL],int to[][COL])/*判断起始与终止是否相同*/

    {

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

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

                if(from[i][j]!=to[i][j])

                    return 0;

            }

        return 1;

    }

    bool change(int from[][COL],const int i,const int j,const int step)/*判断当前状态是否可以进行相应移动*/

    {

        if((i==0&&step==0)||(i==2&&step==1)||(j==0&&step==2)||(j==2&&step==3))

            return 0;

        int a=from[i][j];

        switch(step){

        case 0:

            from[i][j]=from[i-1][j];

            from[i-1][j]=a;

            break;

        case 1:

            from[i][j]=from[i+1][j];

            from[i+1][j]=a;

            break;

        case 2:

            from[i][j]=from[i][j-1];

            from[i][j-1]=a;

            break;

        case 3:

            from[i][j]=from[i][j+1];

            from[i][j+1]=a;

            break;

        default:

cout<<"WRONG!"<            break;

        }

        return 1;

    }

    int value(const int from[][COL],const int to[][COL])/*估价函数*/

    {

        int i,j,m,n;

        int v=0;

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

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

for(m=0;m<3;m++)

for(n=0;n<3;n++)

                        if(from[i][j]==to[m][n])

                            goto p;

               p:

               if(from[i][j]!=0)

                    v+=(abs(i-m)+abs(j-n));

            }

        return v;

    }

    Node make(int from[][COL],int deep,int v,int path[],int step)/*转换函数*/

    {

        Node p;

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

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

            p.x[i][j]=from[i][j];

        }

        p.deep=deep;

        p.expend=v;

        memcpy(p.path,path,sizeof(int)*MAXSTEP);

        p.path[deep]=step;

        return p;

    }

    bool possible(int from[][COL],int to[][COL])/*可行性判断*/

    {

        int m=0,n=0;

        int i,j,k,l;

        int a[COL*COL],b[COL*COL];

for(i=0;i for(j=0;j                a[i*COL+j]=from[i][j];

                b[i*COL+j]=to[i][j];

            }

for(k=0;k for(l=k+1;l if(a[l]                    m++;

if(b[l]                    n++;

            }

        return (n%2)==(m%2);

    }

题目二：回归算法

要    求：（1）撰写一份word文档，里面包括（常见的回归算法、基于实例的算法具体细节）章节。

（2）常见的回归算法包括：最小二乘法（Ordinary Least Square），逻辑回归（Logistic Regression），逐步式回归（Stepwise Regression），多元自适应回归样条（Multivariate Adaptive Regression Splines）以及本地散点平滑估计（Locally Estimated Scatterplot Smoothing），请选择一个算法描述下算法核心思想

（3）随意选用一个实例实现你所选择的回归算法。

题目三：深度优先搜索算法

要    求：（1）撰写一份word文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。

（2）算法思路：简单介绍该算法的基本思想，至少100字。

（3）算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。

（4）主要函数代码：列出算法的具体代码。

（5）简单描述在人工智能的哪些领域需要使用深度优先搜索算法。

题目四：博弈树

要    求：（1）撰写一份word文档，里面包括（基本概念、计算倒推值、 - 剪枝技术）章节。

（2）基本概念：简单描述博弈树，至少200字。

（3）简单描述 - 剪枝技术。

（4）图示博弈树，其中末一行的数字为假设的估值，请对博弈树作如下工作：计算各节点的倒推值。利用 - 剪枝技术剪去不必要的分支。（可在节点分支上直接加注释）

题目五：广度优先搜索算法

要    求：（1）撰写一份word文档，里面包括（算法思路、算法程序框图、主要函数代码）章节。

（2）算法思路：简单介绍该算法的基本思想，至少100字。

（3）算法程序框图：绘制流程图或原理图，从算法的开始到结束的程序框图。

（4）主要函数代码：列出算法的具体代码。

（5）简单描述在人工智能的哪些领域需要使用广度优先搜索算法。