数字水印技术
一、引言
随着互联网广泛普及的应用，各种各样的数据资源包括文本、图片、音频、视频等放在网络服务器上供用户访问。但是这种网络资源的幵放也带了许多弊端，比如一些用户非法下载、非法拷贝、恶意篡改等，因此数字媒体内容的安全和因特网上的侵权问题成为一个急需解决的问题。数字水印作为一项很有潜力的解决手段，正是在这种情况下应运而生。
数字水印（技术是将一些代表性的标识信息，一般需要经过某种适合的变换，变换后的秘密信息（即数字水印），通过某种方式嵌入数字载体（包括文档、音频、软件等）当中，但不影响原载体的使用价值，也不容易被人的知觉系统（如视觉或听觉系统）觉察或注意到。通过这些隐藏在载体中的信息，可以达到确认内容创建者、购买者、传送隐秘信息或者判断载体是否被篡改等目的。在发生产权和内容纠纷时，通过相应的算法可以提取该早已潜入的数字水印，从而验证版权的归属和内容的真伪。
二.算法原理
2.1、灰度图像水印
2.1.1基本原理
处理灰度图像数字水印，采用了LSB（最低有效位）、DCT变换域、DWT变换域三种算法来处理数字水印。在此过程中，处理水印首先将其预处理转化为二值图像，简化算法。
（1）LSB算法原理：最低有效位算法(Least Sig nificant Bit , LSB)是很常见的空间域信息隐藏算法, 该算法就是通过改变图像像素最不重要位来达到嵌入隐秘信息的效果, 该方法隐藏的信息在人的肉眼不能发现的情况下, 其嵌入方法简单、隐藏信息量大、提取方法简单等而获得广泛应用。LSB 信息嵌入过程如下:
S′=S+f S ,M
其中,S 和S′分别代表载体信息和嵌入秘密信息后的载密信息;M为待嵌入的秘密信息, 而隐写分析则是从S′中检测出M以至提取M 。
（2）DCT算法原理：DCT 变换在图像压缩中有很多应用，它是JPEG，MPEG 等数据
压缩标准的重要数学基础。在压缩算法中，先将输入图像划分为 8×8 或 16×16,的图像块，对每个图像块作DCT 变换；然后舍弃高频的系数，并对余下的系数进行量化以进一步减少数据量；最后使用无失真编码来完成压缩任务。解压缩时首先对每个图像块做 DCT 反变换，然后将图像拼接成一副完整的图像。
DCT 变换利用傅立叶变换的性质，采用图像边界褶翻将图像变换为偶函数形式，然后对图像进行二维傅立叶变换，变换后仅包含余弦项，所以称之为离散余弦变换。
二维离散余弦变换DCT(Discrete Cosine Transform)的定义为,假设矩阵A 的大小为M ×N 。
N
q
n M
p
m M m N n mn q p q p A B 2)12(cos
2)12(cos
101
.++=∑∑----ππαα
?
??-≤≤==11,/20,/1M p M p M p α
其中,B p ,q 称为矩阵A 的DCT 系数。DCT 是一种可逆变换，离散反余弦变换定义如下：
N
q
n M
p
m B A pq q M p N q p 2)12(cos
2)12(cos
101
mn ++=∑∑----ππαα
10,10-≤≤-≤≤N n M m
上式的含义是任何M ×N 的矩阵A 都可以表示为一系列具有下面形式的函数的和：
1
0,102)12(cos
2)12(cos
-≤≤-≤≤++N q M p N
q
n M
p
m B pq q p ππαα
这些函数称为 DCT 变换的基函数。这样,B p ,q 就可以看成是应用于每个基函数的加权。Matlab 中直接调用dct2函数对图像的分块进行离散余弦变换。
（3）DWT 嵌入算法原理:小波变换是时间(空间)频率的局部化分析，它通过伸缩平移运算对信号(函数)逐步进行多尺度细化，最终达到高频处时间细分，低频处频率细分，
?
??-≤≤==11,/20
,/1N q N q N q α
能自动适应时频信号分析的要求，从而可聚焦到信号的任意细节，解决了Fourier 变换的困难问题，成为继Fourier 变换以来在科学方法上的重大突破。
假定j l i s ,为J 尺度空间的剩余尺度系数序列，并且令0h 和1h 分别为小波函数的低通和高通滤波器，则二维小波变换的快速分解公式为
j
l
i ,α
l
j m k m
k s l m h i k h ---=∑,0,)2()2(1
l
j m k m
k j l i s l m h i k h ---=∑,1,0,)2()2(β
l j m k m
k j l i s l m h i k h ---=∑,,11,)2()2(γ
l j m k m
k j l i s l m h i k h s ---=∑,0,0,)2()2(
其中j l i s ,为尺度空间的剩余尺度系数序列，它是1,-j l i s 经过行列两个方向低通滤波后的输出，对应原始图像信号在下一个尺度上的低频概貌，属于LL 频带；
j l
i ,α经过行方向高
通，列方向低通，对应水平方向的细节信号在垂直方向的概貌，属于HL 频带；j l i ,β包含了水平方向低通、垂直方向低通滤波后所保留的细节信息，对应LH 频带，j l i ,γ包含了水平和垂直方向都经过高通滤波后的细节信息，表示对角线的细节信息，属于HH 频带。图像的两层多分辨率小波分解如图1所示。
图2.1 两层多分辨率小波分解示意图
每一级分解都把图像分解为四个频带水平（HL ）、垂直(LH)、对角(HH) 和低频，其中低频(LL)部分还可以进行下一级的分解，从而构成了小波的塔式分解。一幅图像经过分解之后，图像的主要能量主要集中于低频部分，图像的高频部分即图像的细节部分所含能量较少，分布在三个子图中，主要包含了原图的边缘和纹理部分信息。
小波变换的这些性质为数字图像的局部特性(如边缘，纹理等)提供了很好的空间一尺度定位，同时由于其多分辨率的表示，可以直接对图像进行分级处理，这一特性更可以实现水印的渐进解码和传输。
上述快速算法，是在已知原始二维函数在某一尺度空间的展开系数矩阵基础之
上进行计算的。初始矩阵的选取是二维快速算法中的一个重要问题，严格的讲，初始矩
阵应使用公式：
dxdy y x y x f s m j m j R
j
n m )()(),(,,,2φφ??=
其中，上标表示尺度，下标表示两个方向的位移，)(x φ为小波函数计算获得。对于初始矩阵的选取，工程上有一种简化的方法，即直接将原始二维函数的离散矩阵看作为
初始矩阵),(,,y n x m f f s n m j
n m ??==，
本文采用db 小波函数进行了一级分解，在小波变换高频系数中进行嵌入。 2.1.2、设计方法和实施过程 （1）水印的嵌入
图2.2 水印嵌入流程图
（2）水印的提取
图2.3 水印提取流程图
)
2()2()2()2()
2()2()2()2(11,,10,,0,1,00,,1,l m h k h l m h i k h l m h i k h l m h i k h s s j
i j j i j
i j j i j
i j j i j
i j j i j m k --+--+--+--=∑∑∑∑-γβαj
n
m s ,
（3）攻击方式
①高斯噪声攻击
使用matlab自带函数：
nosie=fspecial('gaussian',3,indensity);
embedImage=filter2(nosie,Image);
②椒盐噪声攻击
使用matlab自带函数：
embedImage=imnoise(Image,'salt & pepper',indensity) ;
③图像剪切攻击
利用矩阵运算对图像进行剪切。
（4）指标评价
①峰值信噪比（PSNR）
峰值信噪比，如以下公式。用来作为评价水印算法嵌入的平均指标
MSE=1
I i,j?K(i,j)2
n?1
j=0
m?1
i=0
PSNR=10?log10MAX I2
MSE
=20?log10(
MAX
MSE
)
②相似度（NC）
相似度即归一化相似系数，如以下公式。用来对比水印与提取水印的相关性，作为水印算法提取的评价指标。
d c y1,y2=
y1T y2 y1y2
2.2、彩色图像水印
2.2.1基本原理
彩色水印嵌入的原理具体步骤：
（1）分别对彩色的宿主图像和水印图像进行降维处理，提取各自的RGB值，这样原来的三维数组就变成了三个独立的二维数组；
（2）设定嵌入强度alpha值，利用DCT变换对提取的RGB三个分量在变换域进行分块嵌入；
（3）对各块进行IDCT变换，然后对图像进行重构，得到RGB三个分量上的嵌入水印之后的图片；
（4）对得到的RGB三个分量上的嵌入水印之后的图片进行合成得到带水印的彩色图片。彩色水印提取的具体步骤：
（1）对嵌有水印的彩色图片降维得到RGB三个分量上的水印图片；
（2）对RGB三个分量上的水印图片在变换域进行分块提取；
（3）对水印图像进行重构，得到RGB三个分量上的水印图片；
（4）对得到的RGB三个分量上的水印图片进行合成得到彩色水印图片。
2.2.2、设计方法和实施过程
（1）水印的嵌入
（2）水印的提取
图 2.5 彩色图像数字水印提取流程图
三、灰度图像实验结果
3.1 LSB算法嵌入提取水印
（1）无攻击下的提取
图3.1 LSB无攻击下水印提取
从实验结果可以看出最低有效位算法的PSNR偏高，说明图像透明性非常好，但是相似度较低，说明LSB算法很容易受到干扰，鲁棒性差。
（2）噪声攻击下的提取
图3.2 LSB噪声攻击下水印提取(左：高斯噪声，右：椒盐噪声) 通过实验结果，可以知道高斯噪声下提取的水印并没有在椒盐噪声下提取的清晰，但依然能够获取水印信息，说明LSB算法具备一定的抗噪效果。
（3）剪切攻击下的提取
剪切攻击是一种空间上的攻击手段，一般采用剪切嵌入水印图像的一部分，然后再利用残缺的图像来还原嵌入的信息。
图3.3 LSB剪切攻击下的提取
从结果来看，剪切攻击使得水印完全提取不出来，由此可以看出LSB抗剪切能力较差，像素的丢失使得最低有效位信息丢失，从而导致了水印丢失。
3.2 DCT算法嵌入提取水印
（1）无攻击下的提取
图3.4 DCT无攻击下的提取
DCT变换域下的水印嵌入与提取，从实验结果来看，鲁棒性比LSB算法明显提高。（2）噪声攻击下的提取
图3.5 DCT噪声攻击下的提取（左:高斯噪声，右：椒盐噪声）
从实验结果来看，DCT变换域下的水印算法在抗低强度高斯噪声攻击下能力很强。DCT变换域下的水印算法在椒盐噪声攻击下水印失真，但信息还可以辨别。（3）图像剪切攻击下的提取
图3.6 DCT剪切攻击下的提取
从实验结果来看，DCT变换域下的水印算法抗剪切攻击能力很强。在64*64的剪切攻击下，并不受影响。
3.3 DWT算法嵌入提取水印
（1）无攻击下的提取
通过离散小波变换得嵌入的水印在没有任何攻击手段的提取下，能够很好的提取出水印信息，同时隐蔽性也很强。可以说DWT变换域下的水印算法鲁棒性较好，相似能够达到100%。如图3.6所示。
图3.7 DWT无攻击下的提取
（3）高斯噪声攻击下的提取
图3.8 DWT噪声攻击下的提取（左:高斯噪声，右：椒盐噪声）
从结果得出，离散小波变换的数字水印抗高斯噪声能力很强，在受到0.2强度的高斯噪声下，相似度依然能够达到99%。但是抗椒盐噪声却没有那么好的效果。（3）置换加密效果图
图3.9 置换加密处理
通过matlab中的随机数函数给水印嵌入与提取置换加密处理，需要输入正确的密钥才能成功提取水印，从而提高了水印的安全性。
四、彩色图像实验结果
4.1不同嵌入强度系数的水印效果
（1）嵌入强度系数（alpha）等于1/3000时，如图4.1
图4.1 alpha等于1/3000
（2）嵌入强度系数（alpha）等于1/10000时，如图
图4.2 alpha等于1/10000
当alpha=1/3000时，峰值信噪比为29.969，相似度为0.95663，提取的水印失真程度小；
当alpha=1/10000时，峰值信噪比为40.3485，相似度为0.86473，提取的水印失真程度大；因此提取的水印嵌入强度越大，透明性越差，鲁棒性越好；嵌入强度越小，透明性越好，鲁棒性越差。
4.2高斯噪声攻击下的水印提取
图4.3 高斯攻击下的提取
该彩色图像分三层使用DWT算法嵌入水印。如图4.3，DWT算法依然对高斯噪声有着较强的鲁棒性，提取的水印并没有受到噪声影响。
五、总结
本文在水印的嵌入、提取和攻击时，分别采用了空域LSB算法，变换域中的DCT算法，DWT算法；选择评价指标时，为了确保结果的准确性，选择了不同的指标。在嵌入中使用PSNR峰值信噪比来体现透明性，在提取中使用NC相似度来体现鲁棒性；在GUI 中将参数（攻击强度参数和嵌入强度参数）设置为可变的，使设计更加灵活；在安全性方面利用MATLAB中随机数函数加入了置乱和水印嵌入及提取的密钥，大大提高水印安全性。在攻击性方面，采用了高斯噪声攻击，椒盐噪声攻击以及图像剪切等多种攻击手段。从实践中可以看出并没有一种完美的水印手段，每一算法都具有针对性，不具有普遍性。
参考文献
[1] 阮秋琦. 数字图像处理学[M]. 北京：电子工业出版社，2001.
[2] 龚声蓉，刘纯平，王强等. 数字图像处理与分析[M]. 北京：清华大学出版社，2006.
[3] 王炳锡、陈琦、邓峰森.数字水印技术[M].西安：西安电子科技大学，2004.
[4] 陈桂明. 应用MATLAB语言处理数字信号与图像处理[M]. 北京：科学出版社，2000.
[6]胡德明、杨杰、王明照.基于DCT的视频数字水印技术研究[J].武汉理工大学学报（交通科学与工程版），2004-08(第28卷第4期)：600-603.
通信原理大作业 班级： 学号： 姓名：
2PSK信号的调制与解调 分析： 调制： 随机产生一段码元，设：码元个数为60，载波频率采用8KHz，每个周期8个采样点，信号波特率为1000，所以每个码元内有64数据，对这60*64个数据，得出2PSK信号。对原始信号和2PSK信号画图比较。 解调： 采用相干解调，通过混频器后可以得到带有载波的信号，通过滤波器后就可以得到基带信号。对原始信号和解调后的基带信号画图比较。 程序： clc close all clear all codn=60; % 仿真的码元个数 fc=8e+3; % 载波频率 fs=fc*8; %数据采样率 bode=1000; %信号波特率 code=round(rand(1,codn)); %产生随机信码 code_len=round(1/bode/(1/fs)); %得到一个码元周期的数据长度 for i=1:codn %产生双极性数字基带信号 x0((i-1)*code_len+1:code_len*i)=code(i); end x=2*x0-1; %x中有code_len(一个码元中的数据个数)*codn(码元个数) car=cos(2*pi*fc/fs*(0:length(x0)-1)); %产生载波 y=x.*car; %2PSK信号等于双极性数字基带信号乘以载波figure subplot(2,1,1) plot(x) axis([0 length(x0) -1.5 1.5]) grid on zoom on title('原始基带信号') subplot(2,1,2) plot(y)
人工智能大作业 学生：021151** 021151** 时间：2013年12月4号
一．启发式搜索解决八数码问题 1.实验目的 问题描述：现有一个3*3的棋盘，其中有0-8一共9个数字，0表示空格，其他的数字可以和0交换位置（只能上下左右移动）。给定一个初始状态和一个目标状态，找出从初始状态到目标状态的最短路径的问题就称为八数码问题。 例如：实验问题为
到目标状态： 从初始状态： 要求编程解决这个问题，给出解决这个问题的搜索树以及从初始节点到目标节点的最短路径。 2.实验设备及软件环境 利用计算机编程软件Visual C++ 6.0，用C语言编程解决该问题。 3.实验方法 (1).算法描述： ①.把初始节点S放到OPEN表中，计算() f S，并把其值与节点S联系 起来。 ②.如果OPEN表是个空表，则失败退出，无解。 ③.从OPEN表中选择一个f值最小的节点。结果有几个节点合格，当其 中有一个为目标节点时，则选择此目标节点，否则就选择其中任一节点作为节点i。 ④.把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中。 ⑤.如果i是目标节点，则成功退出，求得一个解。 ⑥.扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： a.计算() f j。 b.如果j既不在OPEN表中，也不在CLOSED表中，则用估价函数f
把它添加入OPEN表。从j加一指向其父辈节点i的指针，以便一旦 找到目标节点时记住一个解答路径。 c.如果j已在OPEN表或CLOSED表上，则比较刚刚对j计算过的f 值和前面计算过的该节点在表中的f值。如果新的f值较小，则 I.以此新值取代旧值。 II.从j指向i，而不是指向它的父辈节点。 III.如果节点j在CLOSED表中，则把它移回OPEN表。 ⑦转向②，即GO TO ②。 (2).流程图描述： (3).程序源代码： #include
过去几年，全球的互联网公司包括谷歌、微软、Facebook以及中国的百度、阿里巴巴都在加强人工智能领域的投资，设立自己的人工智能研究院。vivo是第一家设立专攻人工智能方向研究院的中国手机公司。此举是vivo内部已经确立的一份3-5年的中长期发展的战略规划，未来对人工智能的发展研究是必然趋势，vivo公司创始人兼CEO沈炜曾表示“人工智能和5G的结合将会是5G时代手机发展的趋势”。 今年我们看到vivo在产品上不少创新，比如AI拍照、商用屏下指纹技术等等，这些都是基于生物特征(biometrics)的鉴别技术，除此之外还有对人脸、虹膜、指纹、声音等特征上的识别，这些大多涉及到视觉信息，正是体现了计算机视觉的应用性，那什么是计算机视觉呢? 计算机视觉技术的概念 正像其它学科一样，一个大量人员研究了多年的学科，却很难给出一个严格的定义，模式识别如此，目前火热的人工智能如此，计算机视觉亦如此。与计算机视觉密切相关的概念有视觉感知(visual perception),视觉认知(visual cognition),图像和视频理解( image and video understanding)。这些概念有一些共性之处，也有本质不同。 从广义上说，计算机视觉就是“赋予机器自然视觉能力”的学科。自然视觉能力，就是指生物视觉系统体现的视觉能力。一则生物自然视觉无法严格定义，在加上这种广义视觉定义又“包罗万象”，同时也不太符合40多年来计算机视觉的研究状况，所以这种“广义计算机视觉定义”，虽无可挑剔，但也缺乏实质性内容，不过是一种“循环式游戏定义”而已。 实际上，计算机视觉本质上就是研究视觉感知问题。视觉感知，根据维科百基(Wikipedia)的定义, 是指对“环境表达和理解中，对视觉信息的组织、识别和解释的过程”。根据这种定
射频大作业 基于PSpice仿真的振幅调制电路设计数字调制与解调的集成器件学习
目录 题目一：基于PSpice仿真的振幅调制电路设计与性能分析 一、实验设计要求 (3) 二、理论分析 1、问题的分析 (3) 2、差动放大器调幅的设计理论 (4) 2.1、单端输出差动放大器电路 2.2、双端输出差动放大器电路 2.3、单二极管振幅调制电路 2.4、平衡对消二极管调幅电路 三、PSpice仿真的振幅调制电路性能分析 (10) 1、单端输出差动放大器调幅电路设计图及仿真波形 2、双端输出差动放大器调幅电路设计图及仿真波形 3、单二极管振幅调制电路设计图及仿真波形 4、平衡对消二极管调幅电路设计图及仿真波形 四、实验总结 (16) 五、参考文献 题目二数字调制与解调的集成器件学习 一、实验设计要求 (17) 二、概述 (17) 三、引脚功能及组成原理 (18) 四、基本连接电路 (20) 五、参考文献 (21) 六、英文附录 (21)
题目一基于PSpice仿真的振幅调制电路设计 摘要 随着大规模集成电路的广泛发展,电子电路CAD及电子设计自动化（EDA）已成为电路分析和设计中不可缺少的工具。此次振幅调制电路仿真设计基于PSpice，利用其丰富的仿真元器件库和强大的行为建模工具，分别设计了差分对放大器和二极管振幅调制电路，由此对线性时变电路调幅有了更进一步的认识；同时，通过平衡对消技术分别衍生出双端输出的差分对放大器和双回路二极管振幅调制电路，消除了没用的频率分量，从而得到了更好的调幅效果。本文对比研究了单端输出和双端输出的差分对放大器调幅电路及单二极管和双回路二极管调幅电路，通过对比观察时域和频域波形图，可知平衡对消技术可以很好地减小失真。 关键词：PSpice 振幅调制差分对放大器二极管振幅调制电路平衡对消技术 一、实验设计要求 1.1 基本要求 参考教材《射频电路基础》第五章振幅调制与解调中有关差分对放大器调幅和二极管调幅的原理，选择元器件、调制信号和载波参数，完成PSpice电路设计、建模和仿真，实现振幅调制信号的输出和分析。 1.2 实践任务 (1) 选择合适的调制信号和载波的振幅、频率，通过理论计算分析，正确选择晶体管和其它元件；搭建单端输出的差分对放大器，实现载波作为差模输入电压，调制信号控制电流源情况下的振幅调制；调整二者振幅，实现基本无失真的线性时变电路调幅；观察记录电路参数、调制信号、载波和已调波的波形和频谱。 (2) 参考例5.3.1，修改电路为双端输出，对比研究平衡对消技术在该电路中的应用效果。 (3) 选择合适的调制信号和载波的振幅、频率，通过理论计算分析，正确选择二极管和其它元件；搭建单二极管振幅调制电路，实现载波作为大信号，调制信号为小信号情况下的振幅调制；调整二者振幅，实现基本无失真的线性时变电路调幅；观察记录电路参数、调制信号、载波和已调波的波形和频谱。 (4) 参考例5.3.2，修改电路为双回路，对比研究平衡对消技术在该电路中的应用效果。 1.3 写作报告 (1) 按论文形式撰写，包括摘要、正文和参考文献，等等。 (2) 正文包括振幅调制电路的设计原理、理论分析结果、实践任务中各阶段设计的电路、参数、波形和频谱，对观察记录的数据配以图像和表格，同时要有充分的文字做分析和对比，有规律性认识。 (3) 论文结构系统、完备、条理清晰、理论正确、数据翔实、分析完整。 1.4 相关提示 (1) 所有电路和信号参数需要各人自行决定，各人有不同的研究结果，锻炼学生的独立研究和实验分析能力。 (2) 为了提高仿真精度和减小调试难度，可以将调制信号和载波的频率设置得较低。 二、理论分析 1、问题的分析 根据题目的要求，差分对放大器和二极管振幅调制电路目的都是实现基本无
第一章 1、3 什么就是人工智能？它的研究目标就是什么？ 人工智能(Artificial Intelligence),英文缩写为AI。它就是研究、开发用于模拟、延伸与扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。 研究目标:人工智能就是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的研究包括机器人、语言识别、图像识别、自然语言处理与专家系统等。 1、7 人工智能有哪几个主要学派？各自的特点就是什么？ 主要学派:符号主义,联结主义与行为主义。 1.符号主义:认为人类智能的基本单元就是符号,认识过程就就是符号表示下的符号计算, 从而思维就就是符号计算; 2.联结主义:认为人类智能的基本单元就是神经元,认识过程就是由神经元构成的网络的信 息传递,这种传递就是并行分布进行的。 3.行为主义:认为,人工智能起源于控制论,提出智能取决于感知与行动,取决于对外界复 杂环境的适应,它不需要只就是,不需要表示,不需要推理。 1、8 人工智能有哪些主要研究与应用领域？其中有哪些就是新的研究热点？ 1、研究领域:问题求解,逻辑推理与定理证明,自然语言理解,自动程序设计,专家系统,机器 学习,神经网络,机器人学,数据挖掘与知识发现,人工生命,系统与语言工具。 2、研究热点:专家系统,机器学习,神经网络,分布式人工智能与Agent,数据挖掘与知识发 现。 第二章 2、8 用谓词逻辑知识表示方法表示如下知识: (1)有人喜欢梅花,有人喜欢菊花,有人既喜欢梅花又喜欢菊花。 三步走:定义谓词,定义个体域,谓词表示 定义谓词 P(x):x就是人
目录 1立体视觉 (1) 1.1计算机视觉技术 (1) 2立体视觉技术 (3) 2.1双目立体视觉技术 (3) 致谢 (8) 附录： (9)
立体视觉 我的毕业论文排版样文 1立体视觉 1.1计算机视觉技术 计算机视觉既是工程领域也是科学领域中的一个富有挑战性的重要研究领域。计算机视觉是一门综合性的学科，它已经吸引了来自各个学科的研究者参加到对它的研究之中，其中包括计算机科学和工程、信号处理、物理学、应用数学和统计学、神经生理学和认知科学等[18]。 视觉是各个应用领域，如制造业、检验、文档分析、医疗诊断和军事等领域中各种智能自主系统中不可分割的一部分。由于它的重要性，一些先进国家，例如美国把对计算机视觉的研究列为对经济和科学有广泛影响的科学和工程中的重大基本问题，即所谓的重大挑战。“计算机视觉的挑战是要为计算机和机器人开发具有与人类水平相当的视觉能力。机器视觉需要图像信号，纹理和颜色建模，几何处理和推理，以及物体建模。一个有能力的视觉系统应该把所有这些处理都紧密地集成在一起[19]。”作为一门学科，计算机视觉开始于60 年代初，但在计算机视觉的基本研究中的许多重要进展是在80 年代取得的。现在计算机视觉已成为一门不同于人工智能、图象处理、模式识别等相关领域的成熟学科[20]。 不少学科的研究目标与计算机视觉相近。这些学科包括图像处理、图像识别、景物分析、图像理解等。由于历史发展或领域本身的特点这些学科互有差别，但又有某种程度的相互重叠。为了清晰起见，把这些与计算机视觉有关的学科从研究目标和方法角度加以归纳[21]。 （1）图像处理 图像处理技术把输入图像转换成具有所希望特性的另一幅图像。例如，可通过处理使输出图像有较高的信噪比，或通过增强处理突出图像的细节，以便于操作员的检验。在计算机视觉研究中经常利用图像处理技术进行预处理和特征抽取。 （2）图像识别 图像识别技术根据从图像抽取的统计特性或结构信息，把图像分成预定的类别。在计算机视觉中图像识别技术经常用于对图像中的某些部分(例如分割区域)的识别和分类。 第 1 页（共9页）
第二章 2.25 已知线性时不变系统的差分方程为 若系统的输入序列x(x)={1,2,3,4,2,1}编写利用递推法计算系统零状态响应的MATLAB程序，并计算出结果。 代码及运行结果： >> A=[1,-0.5]; >> B=[1,0,2]; >> n=0:5; >> xn=[1,2,3,4,2,1]; >> zx=[0,0,0];zy=0; >> zi=filtic(B,A,zy,zx); >> yn=filter(B,A,xn,zi); >> figure(1) >> stem(n,yn,'.'); >> grid on;
2.28图所示系统是由四个子系统T1、T2、T3和T4组成的，分别用单位脉冲响应或差分方程描述为 T1： 其他 T2: 其他 T3： T4: 编写计算整个系统的单位脉冲响应h(n)，0≤n≤99的MATLAB程序，并计算结果。 代码及结果如下： >> a=0.25;b=0.5;c=0.25; >> ys=0; >> xn=[1,zeros(1,99)]; >> B=[a,b,c]; >> A=1; >> xi=filtic(B,A,ys); >> yn1=filter(B,A,xn,xi); >> h1=[1,1/2,1/4,1/8,1/16,1/32]; >> h2=[1,1,1,1,1,1]; >> h3=conv(h1,h2); >> h31=[h3,zeros(1,89)]; >> yn2=yn1+h31; >> D=[1,1];C=[1,-0.9,0.81]; >> xi2=filtic(D,C,yn2,xi); >> xi2=filtic(D,C,ys); >> yn=filter(D,C,yn2,xi); >> n=0:99; >> figure(1) >> stem(n,yn,'.'); >> title('单位脉冲响应'); >> xlabel('n');ylabel('yn');
西安电子科技大学 考试时间 120 分钟 试题（A） 班级学号姓名任课教师 一、选择（请将答案填写到下面表格中）（每题2分，共2×10=20分） 1、多路信号复用方式中不含以下哪一种？（） A. 频分复用 B. 时分复用 C. 码分复用 D. 相分复用 2、以下属于全双工通信的是：（） A. 广播 B. 对讲机 C. 电话 D.无线寻呼 3、根据香农公式可知为了使信道容量趋于无穷大，不可以采取下列措施：（ ) A、噪声功率为零 B、噪声功率谱密度始终为零 C、信号发射功率为无穷大 D、系统带宽为无穷大 4、设某随参信道的最大多径时延差等于2ms，为了防止出现频率选择性衰落，该信道的相关带宽为：（） A、500Hz B、>500Hz C、<500Hz D、2KHz 5、即使在“0”、“1”不等概率出现情况下，以下哪种码仍然不包含直流成分：( ) 第1页共6页
第2页 共6页 A 、AMI 码 B 、双极性归零码 C 、单极性归零码 D 、差分码 6、二进制数字基带传输系统的误码率计算公式为：( ） A 、()()0/11/0P P P e += B 、()()()()1/010/10P P P P P e += C 、()()10P P P e += D 、()()()()0/111/00P P P P P e += 7、功率利用率最低调制方式是：（ ） A 、2ASK B 、2FSK C 、2PSK D 、2DPSK 8、对二进制频带传输系统而言，下列说法错误的是：（ ） A 、FSK 、PSK 、DPSK 的抗衰落性能均优于ASK ； B 、ASK 、PSK 、DPSK 的最佳判决门限比FSK 容易设置； C 、接收机的输入信噪比增加，解调的误码率一定下降； D 、ASK 、PSK 、DPSK 的频带利用率均高于FSK 。 9、为了防止ΔM 编码过程的过载现象出现，不可以采取以下哪种措施：（ ） A 、减小量化台阶 B 、增大量化台阶 C 、增大采样速率 D 、减小采样周期 10、按照A 律13折线编码实现PCM 编码时,第7段落的段落码为：（ ） A 、011 B 、110 C 、101 D 、 111 二、填空（每空2分，共2×10=20分） 1、 频谱从零频附近开始的信号是 基带信号 。 2、16进制码元速率若为1300B ，则信息速率为 5200b/s 。 3、信道中的干扰和噪声可以简化为乘性干扰和加性噪声，若乘性干扰随时 间快速变化，则对应的信道称为 随参信道 。 4、在地面微波无线中继传输系统中，若A 站和B 站相距50公里，不考虑大 气折射率的影响，则收发天线的架设高度需要大于 50米 。
1.（该题目硕士统招生做）请用框架法和语义网络法表示下列事件。（10分） 2015年2月20日上午11点40分，广东省深圳市光明新区柳溪工业园附近发生山体滑坡，经初步核查，此次滑坡事故共造成22栋厂房被掩埋，涉及公司15家，截至目前已安全撤离900人，仍有22人失联。 答：框架表示法（5分）：（给分要点：确定框架名和框架槽，根据报道给出的相关数据填充，主要内容正确即可给分，不必与参考答案完全一致） <山体滑坡> 时间：2015年2月20日上午11点40分 地点：广东省深圳市光明新区柳溪工业园附近 掩埋厂房：22栋 涉及公司数目：15家 安全撤离人数：900人 失联人数：22人 语义网络表示法（5分）：（给分要点：确定语义网络的节点及其连接关系，根据报道内容进行填充，主要内容正确即可给分，不必与参考答案完全一致） 1. （该题目全日制专业学位硕士做）请用一种合适的知识表示方法来表示下面知识。（10分） How Old Are YOU是微软推出的一款测年龄应用，该应用架设在微软服务平台Azure上，该平台具有机器学习的开发接口，第三方开发者可以利用相关的接口和技术，分析人脸照片。
（给分要点：采用合适的知识表示方法，正确即可给分，不必与参考答案完全一致） 答：
人机交互中的计算机视觉技术 基于视觉的接口概念 计算机视觉是一门试图通过图像处理或视频处理而使计算机具备“ 看” 的能力的计算学科。通过理解图像形成的几何和辐射线测定, 接受器(相机的属性和物理世界的属性, 就有可能 (至少在某些情况下从图像中推断出关于事物的有用信息, 例如一块织物的颜色、一圈染了色的痕迹的宽度、火星上一个移动机器人面前的障碍物的大小、监防系统中一张人脸的身份、海底植物的类型或者是 MRI 扫描图中的肿瘤位置。计算机视觉研究的就是如何能健壮、有效地完成这类的任务。最初计算机视觉被看作是人工智能的一个子方向, 现在已成为一个活跃的研究领域并长达 40年了。 基于视觉的接口任务 至今,计算机视觉技术应用到人机交互中已取得了显著的成功,并在其它领域中也显示其前景。人脸检测和人脸识别获得了最多的关注, 也取得了最多的进展。第一批用于人脸识别的计算机程序出现在 60年代末和 70年代初,但直到 90年代初,计算机运算才足够快,以支持这些实时任务。人脸识别的问题产生了许多基于特征位置、人脸形状、人脸纹理以及它们间组合的计算模型, 包括主成分分析、线性判别式分析、 Gabor 小波网络和 .Active Appearance Model(AAM . 许多公司,例如Identix,Viisage Technology和 Cognitec System,正在为出入、安全和监防等应用开发和出售人脸识别技术。这些系统已经被部署到公共场所, 例如机场、城市广场以及私人的出入受限的环境。要想对人脸识别研究有一个全面的认识,见。 基于视觉的接口技术进展 尽管在一些个别应用中取得了成功,但纵使在几十年的研究之后,计算机视觉还没有在商业上被广泛使用。几种趋势似乎表明了这种情形即将会发生改变。硬件界的摩尔定律的发展, 相机技术的进步, 数码视频安装的快速增长以及软件工具的可获取性(例如 intel 的 OpenCV libraray使视觉系统能够变得小巧、灵
西电人工智能大作业
八数码难题 一.实验目的 八数码难题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如： (a) 初始状态 (b) 目标状态 图1 八数码问题示意图 请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析，得出合理的结论。 本实验选择宽度优先搜索：选择一个起点，以接近起始点的程度依次扩展节点，逐层搜索，再对下一层节点搜索之前，必先搜索完本层节点。 二.实验设备及软件环境 Microsoft Visual C++，（简称Visual C++、MSVC、VC++或VC）微软公司的C++开发工具，具有集成开发环境，可提供编辑C语言，C++以及C++/CLI 等编程语言。 三.实验方法 算法描述： （1）将起始点放到OPEN表； （2）若OPEN空，无解，失败；否则继续； （3）把第一个点从OPEN移出，放到CLOSE表； （4）拓展节点，若无后继结点，转（2）； （5）把n的所有后继结点放到OPEN末端，提供从后继结点回到n的指针； （6）若n任意后继结点是目标节点，成功，输出；否则转（2）。
流程图：
代码： #include
题目：数据结构上机报告学院：电子工程学院 专业：信息对抗技术 学生姓名：甘佳霖 学号：14020310092
西安电子科技大学 数据结构课程实验报告实验名称线性表 电子工程学院 1402031 班Array姓名甘佳霖学号 14020310092 同作者 实验日期 2017 年 3 月 18 日
实验一线性表 一、实验目的 1．熟悉线性表的顺序和链式存储结构 2．掌握线性表的基本运算 3．能够利用线性表的基本运算完成线性表应用的运算 二、实验要求 1.设有一个线性表E={e1, e2, … , e n-1, e n}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ e n, e n-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 2.已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。 三、设计思路 1.顺序表做逆置操作时将对应的首尾元素位置交换，单链表的指针end指向链表的末尾，指针start指向链表头结点，指针s用来找到指向end节点的节点，将指向链表末尾和头结点的存储内容交换，然后头结点指针指向下一节点，s指针从start节点开始遍历寻找指向end 指针的节点，并将end指针赋值为s指针，就完成了单链表的逆置，可以看出单链表和顺序表都可以完成线性表的逆置。 2.分解单链表的实现思路是首先新建3个循环链表，然后顺序遍历单链表，ASCII码判断链表中的元素属于哪一类元素，然后将这个元素添加到对应的循环链表中，从而实现分解单链表的功能。 四、运行结果 1.单链表逆置：
人们常说：眼睛是心灵的窗户，通过眼睛人们可以轻易地交流情感，眼睛也是与外界交流的窗口，这些都是通过“看”来完成的。 人们可以很容易“看到”一幅画，但这一“简单”过程并不如此简单，大致上它可以分为以下几个阶段：首先是通过眼睛将图成像在视网膜上；其次大脑对图像进行理解；最后根据处理的结果做出反应。用比较专业一点的语言来描述，该过程包括了识别、描述与理解三个层次；这其中还隐含了边缘检测（各物体的轮廓等）、图像的分割（各物体区域的划分）等阶段。以上实际上概述了视觉系统的三个层次，即低层阶段：基于图像特征提取及分割阶段；中层阶段：基于物体的几何模型与图像特性表达阶段；高层阶段：基于景物知识的描述、识别与理解阶段，这是根据先验知识介入的程度划分的，且实现起来也越来越困难。 毫无疑问，如何人工实现这一过程是极具挑战性和应用前景的一项工作，计算机视觉也因此而应运而生。计算机视觉是研究用计算机和成像设备来模拟人和生物视觉系统功能的技术学科，其目标是从图像或图像序列中获取对外部世界的认知和理解，即利用二维图像恢复三维环境中物体的几何信息，比如形状、位置、姿态、运动等，并能描述、识别与理解。 计算机视觉的基础是各种成像设备，例如CCD(Charge Coupled Device )摄像机（数码相机属于此类型）、红外摄像机、医学上常用的核磁共振成像、X射线成像等，这些设备不仅可以成像，还可以获取比人眼更丰富的图像，人们可以形象地把摄像机看成计算机视觉的视网膜部分。可以说从人类拍摄出第一幅图像开始，就为计算机视觉的诞生奠定了基础。 而计算机视觉的核心是数字电子计算机，其发展可谓突飞猛进，在计算和存储能力上，人脑已经无法与之相比，人们的目标就是利用计算机非凡的计算处理能力来代替人脑实现对图像的理解，而计算机日新月异的发展也使得这一愿望越来越成为可能。 用于指导“计算机”这个大脑运作的核心是计算机视觉的理论方法，计算机视觉使用的理论方法主要基于几何、概率和运动学计算与三维重构的视觉计算理论，它的基础包括射影几何学、刚体运动力学、概率论与随机过程、图像处理、人工智能等理论。在20世纪70年代，视觉研究大多采用模式识别的方法；80年代，开始采用空间几何的方法以及物理知识进行视觉研究；90年代以后，随着智能机器人视觉研究的发展，引入了许多新的理论与技术如主动视觉理论、不变量理论、融合技术等，并应用于许多计算机视觉系统中。 研究计算机视觉，不得不提的是英国已故科学家戴维·马尔（David Marr），他在计算机视觉发展史上可谓写下了浓重的一笔。在20世纪70年代末，他提出了第一个
Adaptive Evolutionary Artificial Neural Networks for Pattern Classification 自适应进化人工神经网络模式分类 Abstract—This paper presents a new evolutionary approach called the hybrid evolutionary artificial neural network (HEANN) for simultaneously evolving an artificial neural networks (ANNs) topology and weights. Evolutionary algorithms (EAs) with strong global search capabilities are likely to provide the most promising region. However, they are less efficient in fine-tuning the search space locally. HEANN emphasizes the balancing of the global search and local search for the evolutionary process by adapting the mutation probability and the step size of the weight perturbation. This is distinguishable from most previous studies that incorporate EA to search for network topology and gradient learning for weight updating. Four benchmark functions were used to test the evolutionary framework of HEANN. In addition, HEANN was tested on seven classification benchmark problems from the UCI machine learning repository. Experimental results show the superior performance of HEANN in fine-tuning the network complexity within a small number of generations while preserving the generalization capability compared with other algorithms. 摘要——这片文章提出了一种新的进化方法称为混合进化人工神经网络(HEANN),同时提出进化人工神经网络(ANNs)拓扑结构和权重。进化算法(EAs)具有较强的全局搜索能力且很可能指向最有前途的领域。然而,在搜索空间局部微调时，他们效率较低。HEANN强调全局搜索的平衡和局部搜索的进化过程，通过调整变异概率和步长扰动的权值。这是区别于大多数以前的研究，那些研究整合EA来搜索网络拓扑和梯度学习来进行权值更新。四个基准函数被用来测试的HEANN进化框架。此外,HEANN测试了七个分类基准问题的UCI机器学习库。实验结果表明在少数几代算法中，HEANN在微调网络复杂性的性能是优越的。同时，他还保留了相对于其他算法的泛化性能。 I. INTRODUCTION Artificial neural networks (ANNs) have emerged as a powerful tool for pattern classification [1], [2]. The optimization of ANN topology and connection weights training are often treated separately. Such a divide-and-conquer approach gives rise to an imprecise evaluation of the selected topology of ANNs. In fact, these two tasks are interdependent and should be addressed simultaneously to achieve optimum results. 人工神经网络(ANNs)已经成为一种强大的工具被用于模式分类[1],[2]。ANN 拓扑优化和连接权重训练经常被单独处理。这样一个分治算法产生一个不精确的评价选择的神经网络拓扑结构。事实上,这两个任务都是相互依存的且应当同时解决以达到最佳结果。
计算机视觉 计算机视觉是一门研究如何使机器“看”的科学，更进一步的说，就是是指用摄影机和电脑代替人眼对目标进行识别、跟踪和测量等机器视觉，并进一步做图形处理，用电脑处理成为更适合人眼观察或传送给仪器检测的图像。作为一个科学学科，计算机视觉研究相关的理论和技术，试图建立能够从图像或者多维数据中获取‘信息’的人工智能系统。这里所指的信息指Shannon定义的，可以用来帮助做一个“决定”的信息。因为感知可以看作是从感官信号中提取信息，所以计算机视觉也可以看作是研究如何使人工系统从图像或多维数据中“感知”的科学。 目录 1定义 2解析 3原理 4相关 5现状 6用途 7异同 8问题
9系统 10要件 11会议 12期刊 1定义 计算机视觉是使用计算机及相关设备对生物视觉的一种模拟。它的主要任务就是通过对采集的图片或视频进行处理以获得相应场景的三维信息，就像人类和许多其他类生物每天所做的那样。 计算机视觉是一门关于如何运用照相机和计算机来获取我们所需的，被拍摄对象的数据与信息的学问。形象地说，就是给计算机安装上眼睛（照相机）和大脑（算法），让计算机能够感知环境。我们中国人的成语"眼见为实"和西方人常说的"One picture is worth ten thousand words"表达了视觉对人类的重要性。不难想象，具有视觉的机器的应用前景能有多么地宽广。 计算机视觉既是工程领域，也是科学领域中的一个富有挑战性重要研究领域。计算机视觉是一门综合性的学科，它已经吸引了来自各个学科的研究者参加到对它
的研究之中。其中包括计算机科学和工程、信号处理、物理学、应用数学和统计学，神经生理学和认知科学等。 2解析 视觉是各个应用领域，如制造业、检验、文档分析、医疗诊断，和军事等领域中各种智能/自主系统中不可分割的一部分。由于它的重要性，一些先进国家，例如美国把对计算机视觉的 计算机视觉与其他领域的关系 研究列为对经济和科学有广泛影响的科学和工程中的重大基本问题，即所谓的重大挑战（grand challenge）。计算机视觉的挑战是要为计算机和机器人开发具有与人类水平相当的视觉能力。机器视觉需要图象信号，纹理和颜色建模，几何处理和推理，以及物体建模。一个有能力的视觉系统应该把所有这些处理都紧密地集成在一起。作为一门学科，计算机视觉开始于60年代初，但在计算机视觉的基本研究中的许多重要进展是在80年代取得的。计算机视觉与人类视觉密切相关，对人类视觉有一个正确的认识将对计算机视觉的研究非常有益。为此我们将先介绍人类视觉。 3原理 计算机视觉就是用各种成象系统代替视觉器官作为输入敏感手段，由计算机来代替大脑完成处理和解释。计算机视觉的最终研究目标就是使计算机能象人那样通过视觉观察和理解世界，具有自主适应环境的能力。要经过长期的努力才能达到的目标。因此，在实现最终目标以前，人们努力的中期目标是建立一种视觉系统，这个系统能依据视觉敏感和反馈的某种程度的智能完成一定的任务。例如，计算机视觉的一个重要应用领域就是自主车辆的视觉导航，还没有条件实现象人那样能识别和理解任何环境，完成自主导航的系统。因此，人们努力的研究目标是实现在高速公路上具有道路跟踪能力，可避免与前方车辆碰撞的视觉辅助驾驶系统。这里要指出的一点是在计算机视觉系统中计算机起代替人脑的作用，但并不意味
通信原理大作业 1、说明 在通信原理课程中，介绍了通信系统的基本理论，主要包括信道、基带传输、调制 / 解调方法等。为了进一步提高和改善学生对课程基本内容的掌握，进行课程作业方法的改革的试点，设立计算机仿真大作业。成绩将计入平时成绩。 2、要求 参加的同学3~5人一组，选择1?2个题目，协作和共同完成计算机编程和仿真，写出计算机仿真报告。推荐的计算机仿真环境为MATLAB也可以 选择其它环境。 3、大作业选题 (1) 信道噪声特性仿真产生信道高斯白噪声，设计信道带通滤波器对高斯白噪 声进行滤波， 得到窄带高斯噪声。对信道带通滤波器的输入输出的噪声的时域、频域特性进行统计和分析，画出其时域和频域的图形。 (2) 基带传输特性仿真利用理想低通滤波器作为信道，产生基带信号，仿真验证奈氏第一准则的给出的关系。改变低通滤波器的特性，再次进行仿真，验证存在码间干扰时的基带系统输出，画出眼图进行观察。加入信道噪声后再观 察眼图。 (3) 2ASK言号传输仿真 按照2ASK产生模型和解调模型分别产生2ASK言号和高斯白噪声，经过信道传
输后进行解调。对调制解调过程中的波形进行时域和频域观察，并且对解调结果进行误码率测量。2ASK信号的解调可以选用包络解调或者相干解调法。(4) 2FSK信号传输仿真 按照2FSK产生模型和解调模型分别产生2FSK信号和高斯白噪声，经过信道传输后进行解调。对调制解调过程中的波形进行时域和频域观察，并且对解调结果进行误码率测量。2FSK信号的解调可以选用包络解调或者相干解调法。(5) 2PSK信号传输仿真 按照2PSK产生模型和解调模型分别产生2PSK言号和高斯白噪声，经过信道传输后进行解调。对调制解调过程中的波形进行时域和频域观察，并且对解调结果进行误码率测量。2PSK信号的解调选用相干解调法。 ⑹2DPSK言号传输仿真 按照2DPSK产生模型和解调模型分别产生2DPSK言号和高斯白噪声，经过信道传输后进行解调。对调制解调过程中的波形进行时域和频域观察，并且对解调结果进行误码率测量。2DPSK信号的解调可以选用非相干解调或者相干解调法。 (7) 模拟信号的数字传输 产生模拟语音信号，进行PCM编码过程的计算机仿真。仿真发送端采样、 量化编码的过程、仿真接收端恢复语音信号的过程。按照有或者无信道噪 声两种情况分别进行仿真。
人工智能基础 大作业 —－－－八数码难题 学院：数学与计算机科学学院 班级：计科14—1 姓名:王佳乐 学号：１2 2０1６、12、20 一、实验名称 八数码难题得启发式搜索 二、实验目得 八数码问题:在3×3得方格棋盘上,摆放着1到８这八个数码,有1个方格就是空得，其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移与空格下移这四个操作使得棋盘从初始状态到目标状态. 要求：1、熟悉人工智能系统中得问题求解过程; 2、熟悉状态空间得启发式搜索算法得应用； 3、熟悉对八数码问题得建模、求解及编程语言得应用。 三、实验设备及软件环境 1.实验编程工具：VC＋+ 6、0 2.实验环境：Wｉndoｗs7 64位 四、实验方法：启发式搜索 1、算法描述 1.将Ｓ放入open表,计算估价函数f(ｓ)
2.判断oｐeｎ表就是否为空，若为空则搜索失败,否则，将opeｎ表中得第 一个元素加入cｌｏse表并对其进行扩展（每次扩展后加入ｏpen表中 得元素按照代价得大小从小到大排序，找到代价最小得节点进行扩展） 注:代价得计算公式ｆ(n)=d（ｎ）+ｗ（n)、其中f（n)为总代价，d(n）为节点得度,w（ｎ)用来计算节点中错放棋子得个数. 判断i就是否为目标节点,就是则成功，否则拓展i，计算后续节点f（j），利用f（j)对oｐeｎ表重新排序 2、算法流程图： 3、程序源代码： ＃ｉncluｄｅ＜stdｉｏ、ｈ> # iｎclude＜strｉng、h> # include
题目作业调度问题及算法分析 学院名称：计算机与信息工程学院 专业名称：计算机科学与技术
目录 《算法设计与分析》课程大作业.................................................................... 错误!未定义书签。一．动态规划算法解决流水作业调度. (4) 1、问题描述 (4) 2、算法分析 (4) 3. 算法的描述 (5) 4、部分算法实现 (6) 5. 运行结果 (8) 6、时空效率分析 (8) 二．贪心算法解多机调度问题 (8) 1、问题描述 (8) 2、算法分析 (9) 3.部分算法实现 (9) 4.计算复杂性分析 (11) 5. 运行结果 (12) 三．回溯法解决批作业调度问题 (12) 1.问题描述 (12) 2.算法思想 (13) 3. 部分算法实现 (14) 4.运行结果 (15) 5.时间复杂性分析 (15) 四．作业调度算法比较 (16) 五．课程学习总结 (16)
摘要： 在现代企业中，作业调度已成为提高资源利用率、从而提高企业运行效益的关键环节之一。把各个作业分配到车间现有的设备上，并确定它们的先后次序，这是一项复杂的工作本文就作业调度排序问题进行了研究，通过对几个经典作业调度算法的分析讨论，总结了各个算法对作业调度的求解过程，并给出了每个算法的复杂度及性能分析。 关键词：作业调度；动态规划；贪心算法；回溯法；
一．动态规划算法解决流水作业调度 1、问题描述 给定n 个作业，每个作业有两道工序，分别在两台机器上处理。一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。一个作业只有在机器1上的处理完成以后才能由机器2处理。假设已知作业i 在机器j 上需要的处理时间为t[i,j]。流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。 2、算法分析 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 在一般情况下，机器M1开始加工S 中作业时，机器M2还在加工其他作业，要等时间t 后才可利用。将这种情况下完成S 中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 由流水作业调度问题的最优子结构性质可知， )}},{({min )0,(1i i n i b i N T a N T -+=≤≤（1）