〈〈人工智能〉〉
题目：15数码问题
实验1：
要求：
采用广度优先算法解决15数码问题，输出扩展结点，步数和最终结果
算法描述：
广度优先搜索,即BFS(Breadth First Search),常常深度优先并列提及。这是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的近邻加入搜索队列（而深度优先搜索则是栈），循环搜索过程直到队列为空。
广度优先搜索算法的基本思想：从初始状态出发，按照给定的结点产生式规则（算符、结点扩展规则）生产第一层结点，每生成一个结点就检查是不是目标结点，如果是目标结点就搜索结束，如果不是目标结点并且前面没出现过就保存该结点（入队列）；再用产生式规则将所有第
一层的结点依次扩展，得到第二层结点，同时检查是否为目标结点，是目标搜索停止，不是并且没出现过保存（入队）；再把第二层的结点按产生规则扩展生产第三层结点，直至到目标或所有的状态完但不到目标（队列空）。
特点：先生成深度为1的所有结点，再生产深度为2的所有结点，依次类推。先横向，再纵向。这种方法到目标，需要的步数一定最少。
程序算法流程图：
描述：
(1).把起始结点放到OPEN表中。
(2).如果OPEN表是个空表，则没有解，失败退出；否则继续。
(3).把第一个结点从OPEN表中移出，并把它放入CLOSE表的扩展节点表中。
(4).扩展结点N。如果没有后继结点，则转向步骤（2）。
(5).把N的所有后继结点放到OPEN表的末端，并提供从这些后继结点回到N的指针。
(6).如果N的任意个后继结点是个目标结点，则到一个解答，成功退出；否则转向步骤（2）.
流程图：
输入：初始态int A[N][N]={
            {1,2,3,4},
            {5,10,6,8},
            {0,9,7,12},
            {13,14,11,15}
            };
目标状态：int B[N][N]={
            {1,2,3,4},
            {5,6,7,8},
            {9,10,11,12},
            {13,14,15,0}
            };
输出截图：
由于输出的路径节点很多 这里只是显示最终结果和步数。
实验2：
要求：
采用深度优先算法实现15数码问题。
算法描述：
怎么用printf输出bool函数值设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
流程图：
描述：
(1).把起始结点放到OPEN表中。如果此结点为一目标结点，则得到一个解。
(2).如果OPEN表是个空表，则没有解，失败退出；否则继续。
(3).把第一个结点从OPEN表中移出，并把它放入CLOSE表中。
(4).如果结点N的深度等于最大深度，则转向步骤（2）。
(5).扩展结点N,产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向步骤（2）。
(6).如果N的任意个后继结点是个目标结点，则到一个解答，成功退出；否则转向步骤（2）.
流程图：
输入：初始态int A[N][N]={
            {1,2,3,4},
            {5,10,6,8},
            {0,9,7,12},
            {13,14,11,15}
            };
目标状态：int B[N][N]={
            {1,2,3,4},
            {5,6,7,8},
            {9,10,11,12},
            {13,14,15,0}
            };
输出截图：
由于输出的路径节点很多 这里只是显示最终结果和步数
实验3：
要求：
采用启发式的A星算法实现15数码问题。
算法描述：
启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f，对当前的搜索状态进行评估，出一个最有希望的节点来扩展。
评价函数的形式如下：
f（n）＝g（n）＋h（n）
其中n是被评价的节点。
f（n）、g（n）和h（n）各自表述什么含义呢？我们先来定义下面几个函数的含义，它们与f（n）、g（n）和h（n）的差别是都带有一个"*"号。
g*(n)：表示从初始节点s到节点n的最短路径的耗散值；
h*(n)：表示从节点n到目标节点g的最短路径的耗散值；
f*(n)=g*(n)+h*(n)：表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。
  而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。是一种预测。A算法就是利用这种预测，来达到有效搜索的目的的。它每次按照f(n)值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。
流程图：
描述：
(1).把起始结点放到OPEN表中。计算F（S），并把其值与结点S联系起来。
(2).如果OPEN表是个空表，则没有解，失败退出；否则继续。
(3).从OPEN表中选择一个F值最小的结点I。如果有几个结点合格，当其中有一个为目标结点时，则选择此目标结点，否则就选择其中任一个结点为结点I。
(4).把结点I从OPEN表中移出，并把它放入CLOSE的扩展结点表中。
(5).如果I是目标结点，则成功退出，求得一个解。
(6).扩展结点I，生成其全部后继结点。对于I的每一个后继结点J：
(a).计算F(J).

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。