人工智能及其应用。
大作业。宋洋 02115089
徐晓雅 02115090
八数码难题。
一. 题目。
八数码难题的宽度优先搜索。
二. 实验目的。
在3×3组成的九宫格棋盘上,摆有八个将牌,每一个将牌都刻有1-8八个数码中的某一个数码。棋盘中留有一个空格,允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不断改变将牌的布局。给定一种初始的将牌布局或结构(称初始状态)和一个目标的布局(称目标状态),如何移动将牌,实现从初始状态到目标状态的转变。
三. 实验设备及软件环境。
实验设备:个人计算机win7 64位。
软件环境:microsoft visual c++ 6.0
四. 实验方法:宽度优先搜索。
算法描述。1) 把起始节点放到open表中(如果该起始节点为一目标节点,则求得一个解答)。
2) 如果open表是个空表,则没有解,失败退出;否则继续。
3) 把第一个节点(节点n)从open表移出,并把它放入closed的扩展节点表中。
4) 扩展节点n。如果没有后继节点,则转向步骤(2)
5) 把n的所有后继节点放到open表的末端,并提供从这些后继节点回到n的指针。
6) 如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向步骤(2)。
算法流程图。
程序**。#include <>
#include <>
#include <>
#include
#include
using namespace std;
#define hashtablesize 362881
#define not !
#define up 0
#define down 1
#define left 2
#define right 3
#define bit char
typedef struct maps
bit detail[9];
int myindex记录自己节点在hash表中的位置
bit position记录空格(0)在序列中的位置
map,*pmap;
map org初始状态
int endindex目标,上移 ,下移 , 左移 ,右移
int const derection[4] =
/ 可移动的四个方向
int const factorial[9] =
int hashtable[hashtablesize]=;
/hash表,其中记录的是上一个父节点对应的位置
***八数码的输入(在这里不做任何输入检查,均认为输入数据是正确的)**
void input()
int i,j;
int sum , count ,index ;
for(i = 0 ; i < 9 ; i ++
scanf("%1d", i ]
i ] i) ;
for(i = 0 ; i < 9 ; i计算逆序
if( 0 ==i ]
continue;
for(j = 0 ; j < i; j ++
sum +=0 !=j ] j ] i ]
for( i = 0 , index = 0 ; i < 9 ; i ++
// 计算初始状态的hash值
for(j = 0 , count = 0 ; j < i ; j ++
count +=j ] i ]
index +=factorial[ i ] count;
= index + 1 ;
endindex = sum%2 ? 161328:322561; /目标状态的hash值。
return;
***hash值的计算*parent:父状态的hash值*direct:移动的方向**/
inline int hashvalue(map& parent , int& direct )
int i =
int newindex =
bit *p =
switch(direct)
return newindex;
广度优先搜索***
void bfs()
queue queue;
hashtable[ ]1;
while( not )
return ;
***通过hash表中记录的进行查找路径***
void findpath()
int nowindex;
int count =0 ;
int nixu[9], result[9];
int i, j , k ;
stack stack;
nowindex = endindex;
while( -1 !=hashtable[ nowindex ]
nowindex ])
nowindex = hashtable[ nowindex ];
智能传感技术大作业
全天候 监控系统。目录。一 系统概述 3 二 系统功能图 4 三 组成设备 4 四 ccd摄像机的工作原理简介 5 简介 5摄像机的工作方式 6 3.分辨率的选择 6 4.成像灵敏度 7 5.电子快门 7 6.外同步与外触发 7 五 光谱响应特性 8 ccd芯片的尺寸 8 彩色ccd摄像机 9 1,...
智能传感技术大作业
综述。随着科技发展,监控系统的应用越来越广泛,很多场所都需要一套 监控系统来代替人监控一些重要的地点,如此可以有效的节约人力成本还可以获得更好的监控效果。比如银行 档案室等重要的场所,需要利用各种光电成像系统构建一套全天候的 监控系统,以有效对其进行监控。因为需要监控的主要对象是人,所以我认为使用红...
人工智能大作业
目录。摘要2一 问题描述2 二 遗传算法特点介绍2 三 使用基本遗传算法解决0 1背包问题3 四 基本遗传算法解决0 1背包问题存在的不足4 五 改进的遗传算法解决0 1背包问题6 六 心得体会9 七 参考文献10 八 程序 10 摘要 研究了遗传算法解决0 1背包问题中的几个问题 1 对于过程中不...