《人工智能导论》上机实验指导书

基于人工智能的状态空间搜索策略研究

——八数码问题求解

（一）实验软件

TC2.0 或 VC6.0 编程语言或其它编程语言

（二）实验目的

1. 熟悉人工智能系统中的问题求解过程；

2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；

3. 熟悉对八数码问题的建模、求解及编程语言的应用。

（三）需要的预备知识

1. 熟悉TC2.0 或 VC6.0 编程语言或者其它编程语言；

2. 熟悉状态空间的宽度优先搜索、深度优先搜索和启发式搜索算法；

3. 熟悉计算机语言对常用数据结构如链表、队列等的描述应用；

4. 熟悉计算机常用人机接口设计。

（四）实验数据及步骤

1. 实验内容

八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

(a) 初始状态          (b) 目标状态

图1 八数码问题示意图

请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。

2. 实验步骤

（1）分析算法基本原理和基本流程；

程序采用宽度优先搜索算法，基本流程如下：

（2）确定对问题描述的基本数据结构，如 Open 表和 Closed 表等；

（3）编写算符运算、目标比较等函数；

（4）编写输入、输出接口；

（5）全部模块联调；

（6）撰写实验报告。

（五）实验报告要求

所撰写的实验报告必须包含以下内容：

1. 算法基本原理和流程框图；

2. 基本数据结构分析和实现；

3. 编写程序的各个子模块，按模块编写文档，含每个模块的建立时间、功能、输入输出参数意义和与其它模块联系等；

4. 程序运行结果，含使用的搜索算法及搜索路径等；

5. 实验结果分析；

6. 结论；

7. 提供全部源程序及软件的可执行程序。

附：实验报告格式

一、实验问题

二、实验目的

三、实验原理

四、程序框图

五、实验结果及分析

六、结论

七、源程序及注释

#include<stdio.h>

#include<conio.h>

int n,m;

typedef struct Node

{

char matrix[10];/*存储矩阵*/

char operate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/

char extend;/*是否可以扩展，Y代表可以，N代表不可以*/

int  father;/*指向产生自身的父结点*/

}Node;

char start[10]={"83426517 "};/*此处没有必要初始化*/

char end[10]={"1238 4765"};/*此处没有必要初始化*/

Node base[4000];

int result[100];/*存放结果的base数组下标号，逆序存放*/

int match()/*判断是否为目标*/

{

int i;

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

{

  if(base[n-1].matrix[i]!=end[i])

  {

   return 0;

  }

}

return 1;

}

void show()/*显示矩阵的内容*/

{

int i=1;

while(m>=0)

{

  int mm=result[m];

  //clrscr();

  printf("\n\n\n   状态方格\t\t步骤 %d",i);

  printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);

  printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[3],base[mm].matrix[4],base[mm].matrix[5]);

  printf("\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[6],base[mm].matrix[7],base[mm].matrix[8]);

  //sleep(1);

  m--;

  i++;

}

}

void leave()/*推理成功后退出程序之前要执行的函数，主要作用是输出结果*/

{

n--;

while(base[n].father!=-1)

{

  result[m]=n;

  m++;

  n=base[n].father;

}

result[m]=0;

result[m+1]='\0';

show();

//clrscr();

printf("\n\n\n\n\n\n\n\n\n\t\t\t\t搜索结束\n\n\n\n\n\n\n\n\n\n");

getch();

//exit(0);

}

int left(int x)/*把下标为X的数组中的矩阵的空格左移*/

{

int i,j;

char ch;

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

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==0||i==3||i==6||i==9)

{

  return 0;

}

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

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i-1];

base[n].matrix[i-1]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='R';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

        if(match(i))

leave();

return 1;

}

int right(int x)/*把下标为X的数组中的矩阵的空格右移*/

{

int i,j;

char ch;

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

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==2||i==5||i==8||i==9)

{

  return 0;

}

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

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i+1];

base[n].matrix[i+1]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='L';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

if(match(i))

leave();

return 1;

}

int up(int x)/*把下标为X的数组中的矩阵的空格上移*/

{

int i,j;

char ch;

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

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==0||i==1||i==2||i==9)

{

  return 0;

}

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

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i-3];

base[n].matrix[i-3]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='D';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

        if(match(i))

leave();

return 1;

}

int down(int x)/*把下标为X的数组中的矩阵的空格下移*/

{

int i,j;

char ch;

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

{

  if(base[x].matrix[i]==' ')

   break;

}

if(i==6||i==7||i==8||i==9)

{

  return 0;

}

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

{

  base[n].matrix[j]=base[x].matrix[j];

}

ch=base[n].matrix[i+3];

base[n].matrix[i+3]=base[n].matrix[i];

base[n].matrix[i]=ch;

base[n].operate='U';

base[n].extend='Y';

base[n].father=x;

base[x].extend='N';

n++;

        if(match(i))

leave();

return 1;

}

main()

{

int i;

char a[20],b[20];

n=1;

//textcolor(LIGHTGREEN);

//clrscr();

/*以下是输入初始和目标矩阵，并把输入的0转换为空格*/

printf("Please input the start 9 chars:");

scanf("%s",a);

printf("Please input the end 9 chars:");

scanf("%s",b);

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

{

  if(a[i]=='0')

  {

   start[i]=' ';

   continue;

  }

  if(b[i]=='0')

  {

   end[i]=' ';

   continue;

  }

  start[i]=a[i];

  end[i]=b[i];

}

start[9]='\0';

end[9]='\0';

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

{

  base[0].matrix[i]=start[i];

}

base[0].operate='N';

base[0].extend='Y';

base[0].father=-1;

/*以上是为第一个base数组元素赋值*/

for(i=0;n<4000;i++)

{

  if(base[i].extend=='Y')

  {

   if(base[i].operate=='L')

   {

    right(i);up(i);down(i);

   }

   if(base[i].operate=='R')

   {

    left(i);up(i);down(i);

   }

   if(base[i].operate=='U')

   {

    left(i);right(i);down(i);

   }

   if(base[i].operate=='D')

   {

    left(i);right(i);up(i);

   }

   if(base[i].operate=='N')

   {

    left(i);right(i);up(i);down(i);

   }

  }

}

}

 

第二篇：人工智能实验报告 八数码难题

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

（ 2012  —  2013   学年第  1  学期）

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

一、上机目的及内容

1.上机内容

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

2.上机目的

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

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

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

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

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

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

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

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

1台PC及VISUAL C++6.0软件

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

流程图：

源代码：

Source files:

主函数main：

#include <iostream>

#include "Node.h"

#include "Queue.h"

#include "Search.h"

#include "Tree.h"

void CreateNode1(std::vector<int>& s)

{

    s.push_back(2);

    s.push_back(8);

    s.push_back(3);

    s.push_back(1);

    s.push_back(0);

    s.push_back(4);

    s.push_back(7);

    s.push_back(6);

    s.push_back(5);

}

void CreateNode4(std::vector<int>& d)

{

    d.push_back(2);

    d.push_back(8);

    d.push_back(3);

    d.push_back(1);

    d.push_back(6);

    d.push_back(4);

    d.push_back(7);

    d.push_back(0);

    d.push_back(5);

}

void CreateNode8(std::vector<int>& d)

{

    d.push_back(0);

    d.push_back(2);

    d.push_back(3);

    d.push_back(1);

    d.push_back(8);

    d.push_back(4);

    d.push_back(7);

    d.push_back(6);

    d.push_back(5);

}

void CreateNode20(std::vector<int>& d)

{

    d.push_back(2);

    d.push_back(0);

    d.push_back(8);

    d.push_back(1);

    d.push_back(4);

    d.push_back(3);

    d.push_back(7);

    d.push_back(6);

    d.push_back(5);

}

void CreateNode27(std::vector<int>& d)

{

    d.push_back(1);

    d.push_back(2);

    d.push_back(3);

    d.push_back(8);

    d.push_back(0);

    d.push_back(4);

    d.push_back(7);

    d.push_back(6);

    d.push_back(5);

}

void CreateNode_test1(std::vector<int>& d)

{

    d.push_back(7);

    d.push_back(6);

    d.push_back(5);

    d.push_back(4);

    d.push_back(0);

    d.push_back(1);

    d.push_back(3);

    d.push_back(8);

    d.push_back(2);

}

void test_expand()

{

    std::vector<int> s;

    CreateNode1(s);

    std::vector<int> d;

    CreateNode4(d);

   

    Node source(s);

    Node dest(d);

    source.Display();

    Search search(&source);

    std::cout << source.Expand(dest, search);

}

void test_search()

{

    std::vector<int> s;

    CreateNode1(s);

    std::vector<int> d;

    CreateNode4(d);

   

    Node source(s);

    Node dest(d);

    source.Display();

    dest.Display();

    Search search(&source);

    search.Find( & dest);

    search.DisplayRoute();

}

void test_search2level()

{

    std::vector<int> s;

    CreateNode1(s);

    std::vector<int> d;

    CreateNode8(d);

   

    Node source(s);

    Node dest(d);

    source.Display();

    dest.Display();

    Search search(&source);

    search.Find( & dest);

    search.DisplayRoute();

}

void test_search_lab1()

{

    std::vector<int> s;

    CreateNode1(s);

    std::vector<int> d;

    CreateNode27(d);

   

    Node source(s);

    Node dest(d);

    source.Display();

    dest.Display();

    Search search(&source);

    search.Find( & dest);

    search.DisplayRoute();

}

int main(int argc, char** argv)

{

    // test_expand();

    // test_search();

    // test_search2level();

    // test_search_lab1();

    std::vector<int> s;

    CreateNode1(s);

    std::vector<int> d;

    CreateNode27(d);

   

    Node source(s);

    Node dest(d);

    source.Display();

    dest.Display();

    Search search(&source);

    search.Find( & dest);

    search.DisplayRoute();

    return 0;

}

Node函数：

#include <iostream>

#include <math.h>

#include "Node.h"

bool IsOpposite(OP opa, OP opb)

{

    if (LEFT==opa && RIGHT == opb)

        return true;

    if (RIGHT==opa && LEFT == opb)

        return true;

    if (UP==opa && DOWN == opb)

        return true;

    if (DOWN==opa && UP == opb)

        return true;

    return false;

}

Node::Node(std::vector<int> const& state)

:   m_state(state)

,   m_pParent(NULL)

,   m_children()

,   m_op(EMPTY)

{

}

void ShowOP(OP op)

{

    switch (op)

    {

    case EMPTY:

        std::cout << "EMPTY";

        break;

    case UP:

        std::cout << "UP";

        break;

    case DOWN:

        std::cout << "DOWN";

        break;

    case LEFT:

        std::cout << "LEFT";

        break;

    case RIGHT:

        std::cout << "RIGHT";

        break;

    default:

        exit(-1);

    }

}

void ShowOPs(std::vector<OP> const& ops)

{

    for (int id=0; id<ops.size(); ++id)

    {

        ShowOP(ops[id]);

        std::cout << " ";

    }

    std::cout << std::endl;

}

bool Node::Expand(Node const& destNode, Search& search)

{

    int spaceId = FindEmptySpaceId();

    std::cout << "space is at " << spaceId << std::endl;

    std::vector<OP> legalOPs = GenerateLegalOperators(spaceId);

    ShowOPs(legalOPs);

    while ( legalOPs.size() > 0 )

    {

        OP op = legalOPs[ legalOPs.size() - 1 ];

        legalOPs.pop_back();

        Node* pChild = CreateChild(op);

        if ( *pChild == destNode )

        {

            search.SetDestPt(pChild);

            return true;

        }

        search.GetQueue().EnQueue(pChild);

    }

    return false;

}

void Node::Display() const

{

    for(int i=0; i<m_state.size(); ++i)

    {

        std::cout << m_state[i] << " ";

    }

    std::cout << std::endl;

    std::cout << "  pParent: " << m_pParent << std::endl;

    std::cout << "  op: ";

    ShowOP(m_op);

    std::cout << std::endl;

    std::cout << "  ";

    for(int j=0; j<m_children.size(); ++j)

    {

        std::cout << m_children[j] << " ";

    }

    std::cout << std::endl;

}

void Node::DisplayRoute() const

{

    std::vector<OP> routeOps;

    Node const* pNode = this;

    while ( NULL != pNode )

    {

        routeOps.push_back(pNode->m_op);

        pNode = pNode->m_pParent;

    }

    for(int id=routeOps.size()-2; id>=0 ; --id)

    {

        ShowOP( routeOps[id] );

        std::cout << " ";

    }

    std::cout << std::endl;

}

bool Node::operator==(Node const& v) const

{

    for (int id=0; id<m_state.size(); ++ id)

    {

        if ( m_state[id] != v.m_state[id] )

            return false;

    }

    return true;

}

Node* Node::CreateChild(OP op)

{

    std::vector<int> childState = m_state;

    int exchangePos1 = FindEmptySpaceId();

    int exchangePos2 = CalIdBasedOP(op, exchangePos1);

    int temp = childState[exchangePos1];

    childState[exchangePos1] = childState[exchangePos2];

    childState[exchangePos2] = temp;

    Node* child = new Node(childState);

    child->m_pParent = this;

    child->m_op = op;

    m_children.push_back(child);

    return child;

}

int Node::FindEmptySpaceId() const

{

    for (int id=0; id<m_state.size(); ++id)

    {

        if ( 0 == m_state[id] )

        {

            return id;

        }

    }

    return -1;

}

std::vector<OP> Node::GenerateLegalOperators(int spaceId) const

{

    std::vector<OP> allPossibleOps;

    allPossibleOps.push_back(UP);

    allPossibleOps.push_back(DOWN);

    allPossibleOps.push_back(LEFT);

    allPossibleOps.push_back(RIGHT);

   

    std::vector<OP> ops;

    for (int id=0; id<allPossibleOps.size(); ++id)

    {

        OP op = allPossibleOps[id];

        if( IsOpposite(op, m_op) )

        {

            continue;

        }

        if ( IsWithinRange(op, spaceId) )

        {

            ops.push_back(op);

        }

    }

    return ops;

}

int Node::CalIdBasedOP(OP op, int spaceId) const

{

    switch (op)

    {

    case UP:

        spaceId -= int( sqrt( m_state.size() ) );

        break;

    case DOWN:

        spaceId += int( sqrt( m_state.size() ) );

        break;

    case LEFT:

        --spaceId;

        break;

    case RIGHT:

        ++spaceId;

        break;

    default:

        return -1;

    }

    return spaceId;

}

bool Node::IsWithinRange(OP op, int spaceId) const

{

    spaceId = CalIdBasedOP(op, spaceId);

    if (spaceId >= 0 && spaceId < m_state.size())

    {

        return true;

    }

    return false;

}

Queue函数：#include "Queue.h"

void Queue::EnQueue(Node* pNode)

{

    m_queue.push_back(pNode);

}

Node* Queue::DeQueue()

{

    if ( m_queue.size() == 0 )

    {

        return NULL;

    }

    Node* pNode = m_queue[0];

    m_queue.pop_front();

    return pNode;

}

Search函数：

#include "Search.h"

#include "Node.h"

Search::Search(Node* root)

:   m_queue()

,   m_pDestNode( NULL )

{

    m_queue.EnQueue(root);

}

Node* Search::Select()

{

    return m_queue.DeQueue();

}

void Search::Find(Node* destNode)

{

    bool isFound = false;

    while ( !isFound )

    {

        Node* pNode = Select();

        pNode->Display();

        isFound = pNode->Expand(*destNode, *this);

    }

}

void Search::DisplayRoute() const

{

    m_pDestNode->DisplayRoute();

}

Heard files：

Node：#ifndef PROGECT_1_NODE

#define PROGECT_1_NODE

#include <vector>

#include "Search.h"

enum OP

{

    EMPTY,

    UP,

    DOWN,

    LEFT,

    RIGHT

};

bool IsOpposite(OP opa, OP opb);

class Node

{

public:

    Node(std::vector<int> const& state);

    bool Expand(Node const& destNode, Search& search);

    void Display() const;

    void DisplayRoute() const;

    bool operator==(Node const& v) const;

private:

    Node* CreateChild(OP op);

    int FindEmptySpaceId() const;

    std::vector<OP> GenerateLegalOperators(int spaceId) const;

    int CalIdBasedOP(OP op, int spaceId) const;

    bool IsWithinRange(OP op, int spaceId) const;  

    std::vector<int> m_state;

    Node *m_pParent;

    std::vector<Node*> m_children;

    OP m_op;

};

#endif // PROGECT_1_NODE

Queue：

#ifndef PROGECT_1_QUEUE

#define PROGECT_1_QUEUE

#include <deque>

class Node;

class Queue

{

public:

    void EnQueue(Node* pNode);

    Node* DeQueue();

private:

    std::deque<Node*> m_queue;

};

#endif // PROGECT_1_QUEUE

Search：#ifndef PROGECT_1_SEARCH

#define PROGECT_1_SEARCH

class Node;

class Search

{

public:

    Search(Node* root);

    Queue& GetQueue()

    {

        return m_queue;

    }

    void Find(Node* destNode);

    Node* Select();

    void SetDestPt(Node* pDestNode)

    {

m_pDestNode = pDestNode;

    }

    void DisplayRoute() const;

private:

    Queue m_queue;

    Node* m_pDestNode;

};

#endif // PROGECT_1_SEARCH

Tree：

#ifndef PROGECT_1_TREE

#define PROGECT_1_TREE

#endif // PROGECT_1_TREE

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

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

通过本次试验，我对于宽度优先算法的内涵有了一定的了解；通过仔细研读老师给的程序，我对于其中大部分程序代码都有了较为全面的认知；但是部分代码，还是难以理解。

这个实验还可以推广到其他很多的方面，例如：只要是初态进行变化，寻找末态的；都能通过宽度优先算法来实现。

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