Y11 Wij Y12 Wjk Y13 ?j ?k 输入层 隐含层 输出层
图1 三层前向神经网络拓扑结构图
说明：Yi1为输入层结点i的输入，Yk3为输出层结点k的输出，Yj2为隐含层结点j的输出，Tk为输出层结点k对应的教师信号，Wij为结点i和结点j间的连接权值，Wjk为结点j和结点k间的连接权值，?k为输出层结点k的阀值，?j为隐含层结点j的阈值。
BP算法的主要思想是，学习过程由信号的正向传播与误差的逆向传播两个过程组成，正向传播时，模式作用于输入层，经隐含层处理后，传向输出层。若输出层未能得到期望的输出，则转入误差的逆向传播阶段，将输出误差按某种形式，通过隐含层向输入层逐层返回，并“分摊”给各层的所有单元，从而获得各层单元的参考误差（称误差信号），以作为修改各单元间权值的依据。这种信号正向传播与误差逆向传播的各层权矩阵的修改过程，是周而复始地进行的，权值不断修改的过程也就是网络的学习(或称训练)过程。此过程一直进行到网络输出的误差逐渐减小到可接受的程度或达到设定的学习次数为止。
设隐含层和输出层的激活采用S型函数；
f(x)?1
1?e?x由于BP算法要求网络的输入输出函数具有可微分性，而S型函数具有此特性。从形式上看，S型函数的输出曲线两端平坦，中间部分变化激烈；从生理学角度看，一个人对远远低于或高于他智力和知识水平的问题，往往很难产生强烈的思维反应；从数学角度看，S型函数具有可微分性，且具有饱和非线性，可以增加网络的非线性映射能力，因此S型函数更接近于生物神经元的信号输出形式，所以选用S型函数作为BP网络的输出函数。
误差函数（网络的实际输出向量Yk与教师信号向量Tk的误差）采用二乘误差函数；
1NE??(Tk?Yk)2
2K?1BP算法的一般框架如下：
21
1． 初始化网络权值W(t)和阈值?(t)；
其中，W(t)和?(t)为较小的随机数，t为学习次数，初始值为0；
2．输入一个学习样本(Xk, Tk)，其中k＝(1, 2,?, n)，n为样本数；
3．计算隐含层各结点的输出值；
4．计算输出层结点的输出值；
5．计算输出层结点和隐含层结点之间权值的修正量；
6．计算隐含层结点和输入层结点之间权值的修正量；
7．基于步骤5的修正量来修正输出层和隐含层连接权值矩阵和阈值向量；
8．基于步骤6的修正量来修正隐含层和输入层连接权值矩阵和阈值向量；
9．判断全部学习样本是否未取完，若取完，则转步骤2，否则 9.1 计算误差函数； 9.2 若小于规定的误差上限，则算法结束； 9.3 若已达到学习次数，则算法结束；否则t＝t＋1，转步骤2； 人工神经网络具有以分布方式存储知识、并行方式处理、较强的容错能力，并且它具有可以逼近任意的非线性函数以及有很强的自学习、自适应及联想记忆功能等特征，吸引了众多研究人员的兴趣，并在相关领域取得了显著的进展。例如：自动化领域中的系统识别和神经控制器以及智能检测，经济领域中的市场预测和信贷分析，工程领域中的汽车工程、军事工程、水利工程、化学工程，信息领域中的信号处理、模式识别、数据压缩，医学领域中的生物活动分析、医学专家系统等。
参考文献
[1]周春光等.计算智能.吉林大学出版社,2001
[2]李晓峰.人工神经网络BP算法的改进与应用.四川大学学报.2000（2）
习题1
1．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法。 2. 图论诞生于七桥问题。出生于瑞士的伟大数学家A 欧拉（Leonhard Euler，1707—1783）提出并解决了
D 该问题。七桥问题是这样描述的：一个人是否能在
C 一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在
波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，右面是这条河以及河上的两个B 岛和七座桥的草图。请将该问题的图模型抽象出来，第2题图 并判断此问题是否有解。
3．计算π值的问题能精确求解吗？设计求解π值的算法。
4．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代
22
码和C++描述。
5．对于下列函数，请指出当问题规模增加到4倍时，函数值会增加多少？
（1）log2n （2）n （3）n （4）n2 （5）n3 （6）2n
6．考虑下面的算法，回答下列问题： //n （1）该算法求的是什么？ int Stery(int n) 为非负整数 { （2）该算法的基本语句是什么？
S=0;
（3）基本语句执行了多少次？ for (i=1; i<=n; i++) （4）该算法的效率类型是什么？ S=S+i*i;
return S; （5）对该算法进行改进，分析改进算法的效率；
} （6）如果算法不能再改进了，请证明这一点。 7．使用扩展递归技术求解下列递推关系式：
（1）T(n)??4n?11n?1?? （2）T(n)??
3T(n?1)n?12T(n3)?nn?1??8．考虑下面的递归算法，回答下列问题：
int Q(int n) //n 为正整数 （1）该算法求的是什么？ { （2）写出n=3时的执行过程；
if (n= =1) return 1; else return Q(n - 1)+2*n - 1; （3）建立该算法的递推关系式并求解； } （4）将该算法转换为非递归算法。 9．欧几里德算法在输入规模为n时的平均效率，是根据算法执行的平均除法次数Davg(n)来度量的，Davg(n)是gcd(n, 1)，gcd(n, 2)，?，gcd(n, n-1)和gcd(n, n)的除法次数的平均值。例如：Davg(5)=(1+2+3+2+1)/5=1.8。画出Davg(n)的散点图，并指出可能的效率类型。
10．如果T1(n)=O(f (n))，T2(n)=O(g(n))，证明： （1）T1(n)＋T2(n)=max{O(f (n)), O(g(n))} （2）T1(n)×T2(n)=O(f (n))×O(g(n))
11．国际象棋是很久以前由一个印度人Shashi发明的，当他把该发明献给国王时，国王很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些粮食：棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒，??，以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢？ 12. 有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？
13．欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动？为什么？
23