遗传算法应用的分析与研究
福州八中钱自强
【摘要】
随着科技水平的不断发展，人们在生产生活中遇到的问题也日益复杂，这些问题常常需要在庞大的搜索空间内寻找最优解或近似解，应用传统算法求解已经显得相当困难。而近年来，生物学的进化论被广泛地应用于工程技术、人工智能等领域中，形成的一类有效的随机搜索算法——进化算法，有效的解决了诸多生产生活中的难题而显得越来越流行。
本文的首先将介绍进化算法的原理以及历史使大家对进化算法有一个初步的了解，其次将详细介绍应用遗传算法解题的步骤，并提出有效改进和应用建议。紧接着通过一个NP难题的优化实例让大家对遗传算法有更深刻的了解，最后通过数据分析证明其方法的有效性。
【关键词】
人工智能；进化算法；遗传算法（GA）；多目标最小生成树
目录
一、进化算法理论
1．1进化算法概述－ 2－
1．2遗传算法介绍－ 2－
二、遗传算法
2．1遗传算法基本流程－ 3－
2．2遗传算法中各重要因素分析－ 3－
2．3重要参数设置－ 6－
三、遗传算法在多目标最小生成树问题中的应用
3．1多目标最小生成树－ 7－
3．2应用遗传算法解决多目标最小生成树－ 9－
3．3测试－11－
四、结束语－15－
附录－16－
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
一. 进化算法理论
1．1进化算法概述
从远古时代单细胞开始，历经环境变迁的磨难，生命经历从低级到高级，从简单到复杂的演化历程。生命不断地繁衍生息，产生出具有思维和智能的高级生命体。人类得到生命的最佳结构与形式，它不仅可以被动地适应环境，更重要的是它能够通过学习，模仿与创造，不断提高自己适应环境的能力。
进化算法就是借鉴生物自然选择和遗传机制的随机搜索算法。进化算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。作为随机优化与搜索算法，进化算法具有如下特点：进化算法不是盲目式的乱搜索，也不是穷举式的全面搜索，它根据个体生存环境即目标函数来进行有指导的搜索。进化算法只需利用目标的取值信息而不需要其他信息，因而适用于大规模、高度非线性的不连续、多峰函数的优化，具有很强的通用性；算法的操作对象是一组个体，而非单个个体，具有多条搜索轨迹。
1．2遗传算法
遗传算法（Genetic Algorithm）是进化算法的一个重要分支。它由John Holland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行。
遗传算法的主要特点是群体搜索策略和群体中个体之间的信息互换,它实际上是模拟由个体组成的群体的整体学习过程,其中每个个体表示问题搜索空间中的一个解点.遗传算法从任一初始的群体出发,通过随机选择，交叉和变异等遗传操作,使群体一代代地进化到搜索空间中越来越好的区域,直至抵达最优解点.
遗传算法和其它的搜索方法相比,其优越性主要表现在以下几个方面：首先,遗传算法在搜索过程中不易陷入局部最优,即使在所定义的适应度函数非连续.不规则也能以极大的概率找到全局最优解,其次,由于遗传算法固有的并行性,使得它非常适合于大规模并行分布处理,此外,遗传算法易于和别的技术(如神经网在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
络.模糊推理.混沌行为和人工生命等)相结合,形成性能更优的问题求解方法.
二. 遗传算法
2．1遗传算法的基本流程
一个串行运算的遗传算法通常按如下过程进行：
(1) 对待解决问题进行编码；t:=0
(2) 随机初始化群体X(0):=()n x
,
,
x,
x
；
1
2
(3) 对当前群体X(t)中每个染色体
x计算其适应度F ()i x，适应度表示了
i
该个体对环境的适应能力，并决定他们在遗传操作中被抽取到的概
率；
(4) 对X(t)根据预定概率应用各种遗传算子，产生新一代群体X(t+1)，
这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想；
(5) t:=t+1(新生成的一代群体替换上一代群体)；如果没有达到预定终止
条件则继续(3)。
2．2 遗传算法中各重要因素分析
▲编码理论
遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、实数、有序串）。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，在具体问题中，
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
根据问题的不同，采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操作，从而更易于引入相关启发式信息，往往可以取得比二进制编码更高的效率。
▲染色体
每个编码串对应问题的一个具体的解，称为染色体或个体。一个染色体可以通过选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群体。群体中染色体可重复。
▲随机初始化
随机或者有规律（如从一个已知离解较近的单点，或者等间隔分布地生成可行解）生成第一代群体。一次遗传算法中有目的采用多次初始化群体会使算法拥有更强的搜索全局最有解的能力
▲适应度
一个染色体的适应度是对一个染色体生存能力的评价，它决定了该染色体在抽取操作中被抽取到的概率。估价函数是评价染色体适应度的标准，常见的估价函数有：直接以解的权值（如01背包问题以该方案装进背包物品的价值作为其适应度），累计二进制串中1/0的个数（针对以二进制串为编码理论的遗传算法），累加该染色体在各个目标上的得分（针对多目标最优化问题，另外，对于此类问题，本文提出了一种更有效的估价函数）。
▲遗传算子
遗传算子作为遗传算法的核心部分，其直接作用于现有的一代群体，以生成下一代群体，因此遗传算子的选择搭配，各个算子所占的比例直接影响遗传算法的效率。一个遗传算法中一般包括多种遗传算子，每种算子都是独立运行，遗传算法本身只指定每种算子在生成下一代过程中作用的比例。算子运行时从当前这代群体中抽取相应数量的染色体，经过加工，得到一个新的染色体进入下一代群体。
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
下面列出几种常见的遗传算子：
● 保持算子：抽取1个染色体，直接进入下一代。该算子使算法能够收敛。 ● 交配算子：抽取2个染色体，交换其中的某些片段，选择适应度高的（或
者都选），进入下一代群体。该算子使得遗传算法能够利用现有的解寻求更优的解。
● 变异算子：抽取1个染色体，对其进行随机的改变，进入下一代群体。
该算子使得算法可以跳出局部最优解，拥有更强搜索全局最有解的能力，防止陷入局部搜索，该算子的概率不可过高，否则将引起解的发散，使得算法无法收敛。
▲ 抽取
抽取操作是遗传算法中一个重要基本操作，作用是按照“优胜劣汰”的原则根据各个染色体的适应度从当前这代群体中挑选用于遗传算子的染色体。通常采用的手段是偏置转盘：
设算法中群体数量为population ，首先计算当代群体的各染色体适应度之
和∑==
population
i i
x F t S 1
)()(。将
1～)(t S 内的整数划分成population 个区间段，每个
染色体所占的区间段的长度既是它的适应度。这样，随机产生一个1～
)(t S 的整数，抽取该点所属区间段
相对应的染色体，就可以保证任意一个染色体x i 在抽取操作中被抽取到的概率为)
()
(t S x F i 。
▲ 终止条件
遗传算法的终止条件用于防止遗传算法无止境的迭代下去，一般限制条
F(x1)
F(x2)F(x3)F(x4)F(x5)F(x6)
件可以设为达到指定的迭代次数后终止，或当解的收敛速度低于一定值时自动终止。当遗传算法达到终止条件时，遗传算法结束，并按照要求返回中途最优的一个染色体（或所有满足条件的非劣最优解）
2．3重要参数设置
在应用遗传算法解决问题的时候，往往需要根据实际情况的不同，对不同问题使用不同的遗传参数。在大规模的问题上，一次遗传算法的不同时期也可以设置不同的遗传参数。对遗传算法效率影响较大的参数如下：
群体大小：一代群体中染色体的数量，群体大小越大所能容纳的染色体品种也越多，越有利于搜索全局最有解，但是会下降收敛的速度，所
需的时间也更多。
迭代次数：最多更新群体的次数，迭代次数的增加可以使得解收敛更精确但是所需的时间也越多，如果时间允许，采用多次初始化群体的操
作要比设置很大的迭代次数来得更高效些。
保持率：保持算子所占的比例，通常不超过70%
交配率：交配算子所占的比例，通常不超过50%
变异率：变异算子所占的比例，通常不超过1%
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
三. 遗传算法在多目标最小生成树问题中的应用
生活中的很多问题，例如道路铺设，电网架设，网络构设等，其实都可以归结到最小生成树模型，经典的Prim 算法和Kruskal 算法都可以解决该问题，算法的时间复杂度都是线形的，但是现实生活中的问题往往没有那么简单，一条边上可能不只带一个权，例如一条公路的铺设道路长度还要考虑环境和人文因素，电网架设时除了考虑线路费用还要考虑架设难度，一个网络连接除了考虑网络延时还要考虑传输稳定性和安全性等，于是问题就转化为求解多目标的最小生成树问题的非劣最优解，这个问题是NP 难的，Prim 算法，Kruskal 算法等常规算法就显得无能为力，搜索算法的复杂度却又过高。
3．1多目标最小生成树问题
3．1．1 最小生成树
在图论中，一个无回路（圈）的连通子图称为树。设T ＝（N ，E T ）是|N |≥3的一个图，则下列关于树的6个定义是等价的：①T 连通且无回路；②T 有|N |－1条边且无回路；③T 连通且有|N |－1条边；④T 连通且每条边都是割边；⑤T 的任两点间都有唯一的路相连；⑥T 无回路，但在任一对不相邻的点之间加连一条边则构成唯一的回路。
设有一无向图),,(W E N G =，其中∑=∈E
e e w W 为权函数，若树
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
),,(T T W E N T =包含了图G 的所有顶点，则树T 为G 的一个生成树，其中
∑=∈T
E e e T w W 为树T 的权。图G 的生成树不唯一，权和最小的生成树称为G 的最小
生成树。
3．1．2 多目标最小生成树
而当图中每个边的权值有多个时，相应的问题称为多目标最小生成树问题。该类问题的目标是找出问题的所有非劣最优生成树，显然该类问题即使不加任何约束条件也属于NP 问题。
设有一个连通的无向图G=（V ，E ），其中V ＝｛v 1,v 2,…,v n ｝是一个有限集合，代表图G 的顶点，},,...,,...,,{,1,3,12,1n n j i e e e e E -= ，之间有边
???=otherwise
v v e j i j
i ,0, ,1, ),...,1;1,...,2,1( n i j n i +=-=为图G 的边的集合，
若边e i ,j 存在则该边有m 个值为正数的属性与之对应，用},...,,{,2,1,,m
j i j i j i j i w w w =w 表示，实际问题中),...,2,1(,m k w k j i =可以是距离、代价等等。
令
),
......(,1,3,12,1n n j i x x x x -=x
, 0 1 ,1,,?
??==otherwise e if x j i j i ，被选中且 ;1,...,2,1-=n i n i j ,...,1+=，表示图G 的一棵生成树。X 为所有x 的集合，则
多目标最小生成树问题描述如下：
n i j n i x w f x w f x w f j i m j i m j i j i j i j i ,...,1,1,...2,1
;)( min ...
)( min ;)( min ,,,2,2,1,1+=-====∑∑∑x x x ；
其中)(x i f 为问题中需要最小化的第i 个目标。
与一般的最小生成树问题相比，多目标最小生成树问题只是目标函数不止一
个，然而正是因为目标不止一个而且这多个目标之间是经常是相互冲突的，因此无法使用经典的最小生成树算法通过找出具有最小权值的边逐步生成最小树，而如果将多个目标转换成单个目标再应用经典算法，则只能求出一个解，而不是找到问题的一组非劣最优解，而且多目标到单目标之间的转换对决策者来也是一个难题。
3．2 应用遗传算法解决多目标最小生成树问题
3．2．1 编码设计
Cayley证明了对于一个完全图G，连接所有n个顶点的树有n n-2棵。为此Prüfer建立了一个这些树与从n个数取n-2个数的所有组合之间的一一对应关系，即如果对完全图中所有顶点从1到n开始编号，则任意一个在从1到n的n个数中取n-2个数的组合都与唯一的一棵生成树相对应。
本文对生成树的编码采用基于以上的一一对应建立起来的Prüfer数编码机制，把每一棵树与一个长度为n-2的数字串对应，而对于任意一个长度为n-2的数字串也与唯一的一棵生成树相对应，生成树到数字串的编码与数字串到生成树的解码的详细证明可参考相关文献，本文这里只作简要描述。
★编码过程
▲编码串初始为空串
▲令j为树中编号最小的叶节点；
▲找到唯一于j相邻的点i，把i加入编码串的最右端
▲把j以及连接i和j的边从树中删除，这时候树只有n-1个顶点
▲重复以上3个步骤直到树中只剩下一条边这时候得到的编码串即为相应树的Prüfer编码
★解码过程
▲设P为编码串，P为图的顶点编号不出现在P中的顶点的集合；
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
▲设i 为P 中编号最小的顶点，j 为P 中最左端的顶点，则将连接i 和j 的边加入到树中，然后分别把i 和j 从P 和P 中删除，如果P 中不在出现顶点
j 则把j 加入到P 中
▲重复以上步骤，直到P 为空；
▲当P 为空串时，P 中刚好剩下两个顶点，将连接这两个顶点的边加入到树中，最后构成的树即为与最初P 对应的生成树。
例如，图3-1则为一棵生成树以及其相对应的Prüfer 编码图3-2。
显然Prüfer 编码是生成树的一个有效表示方式，应用该编码方式，可以很容易地随机生成一棵生成树，而且Prüfer 数编码串的每个位置的信息量又相对均匀因此很适合遗传操作。
3．2．2 估价函数设置
定义估价函数g(x)为???
?
???????? ???∑=k i i x f i 12
100)(]min[，
)(x f i 表示当前的染色体在目标i 的费用情况，min[i]表示截止到上一代为止，产生的所有染色体在目标i 的费用的最小值。
本文提出的这样定义比起常见的直接累加各目标上的权值的好处在于，其不仅很好的体现了一个染色体在各个目标上的优势，与此同时还避免了由于每个目标的取值范围不同或者取值的整体趋势不同而造成的某些个体在某些目标的优势无法被体现，使得算法能够适应现实生活中各类问题。
图3-1
图3-2
3．2．3 遗传操作定义
★交配算子
交叉算子我们使用的是小片段等位交叉算子，随机在两个染色体中抽取等位的，长度不超过2的片段进行互换，然后选择适应度较高的进入下一代，具体操作方法如下图3-3所示：
Parent 1 2 5 6 8 2 5
Parent 2 8 4 5 2 8 7
Offspring 1 2 5 5 2 2 5
Offspring 2 8 4 6 8 8 7
图3-3 小片段等位交叉算子示意图
★变异算子
变异算子采用常规的单点变异，即随机生成一个1到n之间的数替换Prüfer 数编码串中的某一位，如图3-4所示。
Parent 2 5 6 8 4 5
Offspring 2 5 6 2 4 5
图3-4单点变异示意图
可以看出单点变异也可以很大程度上保留了原染色体的性质。
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
3．3测试
我们将保持率定为54%，交配率定为45%，变异率定为1%，并且根据数据不同对迭代次数和群体大小进行调整，将其于原始搜索算法进行对比（注：为了能够直观看出遗传算法的近似程度，所有数据采用2目标）。
测试环境：P4 2.0GhzA 256MDDR WinXp Delphi 7.0
3．3．1小规模经典测试数据列表
数据文件编号数据信息
搜索算法表现遗传算法表现
耗时正确性参数选择耗时正确性E1 N=3 K=2 Ans=2 0s 完全正确L=20 P=10 0s 完全正确
E2 N=4 K=2 Ans=6 0s 完全正确L＝100 P=30 0s 完全正确
E3 N=5 K=2 Ans=12 0s 完全正确L=1000 P=100 2s 完全正确3．3．2大中规模随机测试数据列表
数据文件编号H1 H2
数据规模N=10 K=2 N=11 K=2
搜索算法表现22分钟6小时20分钟
遗传算法表现参数选择L=20000 P=400 L=30000 P=400 耗时116s 296s
正确性
算法得到了
一组十分近
似的解，参见
图示
算法得到了一组
比较近似的解，参
见图示
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
00.511.522.533.544.50
1
2
3
4
最优解答
遗传算法得到的解
测试数据h1的解答分析
0510*******
10
20
30
40
最优解答
遗传算法得到的解
测试数据h2的解答分析
3．3．3特殊测试数据分析
对于2目标最优化考虑到现实生活中问题的2个目标的费用之间可能具有的一些关系，例如当设备相似时某个网络链接的速度相对较高，那么它的稳定性一定较低，因此我们对正相关和反相关两种特殊情况进行了测试，在这里先给出正
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html, 1.51, 1.23
0.2
0.40.60.811.21.4最优解答
遗传算法得到的解答
相关与反相关的简单定义：
【正相关】
如果对于图中的任意两条边2,21,1,j i j i e e 满足如果1
2,211,1j i j i W W ≥成立，那么2
2,221,1j i j i W W ≥成立，则称这张图的权为正相关的。
【反相关】
类似的定义，如果对于图中的任意两条边2,21,1,j i j i e e 满足如果1
2,211,1j i j i W W ≥成立，那么2
2,221,1j i j i W W ≤成立，则称这张图的权为反相关的。
特殊数据测试表
数据文件编号
S1
S2
S3
数据信息
规模 N=10 K=2 N=10 K=2 N=15 K=2 特殊性
正相关 反相关 正相关 搜索算法表现
15分钟
28分钟
600年（估计）
遗传
算法
表现
参数选择 L=2000 P=400 L=20000 P=400
L=20000 P=400 耗时
11秒
304s
114秒*15 (15次运行) 正确性
该算法在5次
执行有内80％
（4次）的概率得到该最优解
算法得到了一组
比较相似的解，参
见图示
该程序在第12次运行的时候得到了
我们的最优解(3.11,3.83)，并且值
得一提的是在第3次运行时就得到
一个相当接近的近似解(3.14
3.86)，并且在第6次和第9次都出
现了(3.18,3.99)这个不错的解
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
00.511.522.533.5400.5
1 1.5
2 2.5
3 3.54
最优解答
遗传算法得到的解答No.12遗传算法得到的解答No.3遗传算法得到的解答No.6&9
测试数据S1的解答分析
测试数据S3的解答分析
四．结束语
本文主要介绍了遗传算法时的一些基本知识和一些使用心得，以及通过测试
结果让大家看到了遗传算法在解决组合优化类问题有着和其他算法无法比拟的强大优势。它的特点就是可以在较短的时间内，得到比较令人满意的解，而且算法相对简明。对于现实生活中的大量常规算法无法解决问题，遗传算法都有着良
024********
160
5
10
1520
最优解答
遗传算法得到的解
测试数据S2的解答分析
好的应用前景。
遗传算法不仅一种算法，更是一种思想。在搜索中通过灵活的运用进化的思想来解决问题，往往能够收到事半功倍的效果。目前遗传算法在信息学竞赛中还不是那么普遍。本文的目的就是希望越来越多的信息学爱好者了解遗传算法，了解进化算法的思想。
由于作者能力有限，文中难免有所疏漏，欢迎来信指正。
参考文献
陈志平徐宗本《计算机数学》科学出版社
周明孙树栋《遗传算法原理及应用》国防工业出版社
邵军力张景魏长华《人工智能基础》电子工业出版社
附录：
遗传算法求解多目标最小生成树问题程序源代码：
Program Ga;
const
MaxN = 50;
MaxK = 5;
PopulationMax = 1000;
Maxans = 1000;
Population = 40;
Live = 2000;
Change = 45;
Suddenly = 1;
type code=array[1..MaxN]of integer;
vector=array[1..Maxk]of real;
note=record
v :vector;
data :code;
power:longint;
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
end;
Group=array[1..PopulationMax]of note;
var
inf,ouf:text;
d:array[1..MaxK,0..MaxN,0..MaxN]of real;
ans,ans2:array[1..Maxans]of vector;
ansb,ansb2:array[1..maxans]of code;
sn,n,k:longint;maxv:vector;
population,live,change,suddenly:longint;
function Genetic_Uncode(s:code):vector;
var temp:vector;uu:boolean;
i,j,l,r:longint;
s2:code;Se:set of 1..maxn;
function get:integer;
var i:longint;
begin
for i:=1 to n do
if i in Se then begin Se:=Se-[i];get:=i;exit;end; end;
begin
Se:=[1..n];
FOR I:=1 to k do temp[i]:=0;
for i:=1 to n-2 do Se:=Se-[s[i]];
for i:=1 to n-2 do
begin
l:=get;
for j:=1 to k do
begin
if (l<=0)or(l>n) or (s[i]<=0 )or(s[i]>n) then 在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
begin L:=L+1; end;
temp[j]:=temp[j]+d[j,l,s[i]];
end;
uu:=true;
for j:=i+1 to n-2 do if s[j]=s[i] then begin uu:=false;break;end;
if uu then Se:=Se+[s[i]];
end;
l:=get;r:=get;
for j:=1 to k do
temp[j]:=temp[j]+d[j,l,r];
Genetic_Uncode:=temp;
end;
procedure Input_Initial;
var s,i,j:longint;tempcode:code;
begin
readln(inf,n,k);
for s:=1 to k do
for i:=1 to n do
for j:=1 to n do
read(inf,d[s,i,j]);
for i:=1 to n-2 do tempcode[i]:=random(n)+1;
maxv:=Genetic_uncode(tempcode);randomize;
sn:=1;ans[1]:=maxv;ansb[1]:=tempcode;
close(inf);
end;
function find(v1,v2:vector):longint;
var i:longint;
check:boolean;
在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html,
begin
check:=true;
for i:=1 to k do
if v1[i] if check then begin find:=1;exit;end; check:=true; for i:=1 to k do if v1[i]>v2[i] then begin check:=false;break;end; if check then begin find:=-1;exit;end; find:=0; end; procedure insert(v:vector;vcode:code); var i,sn2:longint; begin sn2:=0; if (v[1]=2) then begin end; for i:=1 to sn do case find(v,ans[i]) of 0:begin inc(sn2);ans2[sn2]:=ans[i];ansb2[sn2]:=ansb[i];end; 1:exit; end; inc(sn2);ans2[sn2]:=v;ansb2[sn2]:=vcode;sn:=sn2;ans:=ans2;ansb:=a nsb2; end; procedure Genetic; var S,S0:Group; i:longint;all:int64; 在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html, procedure Genetic_Initial; var i,j:longint; begin for i:=1 to Population do for j:=1 to n-2 do s[i].data[j]:=random(n)+1; end; function Genetic_Compute(v:vector;vcode:code):longint; var i,mark:longint;nowv:vector; begin nowv:=maxv;mark:=0;insert(v,vcode); for i:=1 to k do begin mark:=mark+sqr(round((nowv[i]/v[i])*100)); if v[i] end; Genetic_Compute:=mark; end; procedure Genetic_Start; var i:longint; begin all:=0; for i:=1 to Population do begin s[i].v:=Genetic_Uncode(s[i].data); s[i].power:=Genetic_Compute(s[i].v,s[i].data); all:=all+s[i].power; end; end; 在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html, 1 建设物流实训室的必要性 在社会需求的推动下，20xx年起，全国部分学校开始试办“物流管理”等相关专业，为企业培养和输送物流专业人才。这在一定程度上对物流知识和思想的传播起到了很好的作用，也的确培养了一些物流人才。他们在相关的物流岗位上发挥了作用，有效地促进了企业物流运作的变革和进步。 但是，其中反映出的问题也不少，主要体现在以下几个方面： 1.1 偏重理论培训，缺少实践环节 目前在各种认证体系中，基本上以知识性学习为主，只有少量的实际操作环节。 现代物流业很注重实际操作经验，仅有理论知识难以解决企业的实际业务问题，物流培训也必须以此为重要原则，加强实训功能，注重对实际业务的理解和对实际操作技能的掌握，才能培养出符合企业需求的人才。 1.2 教学手段单一，感性认识与理性认识不能有机结合 目前无论是高校的物流学历教育还是职业培训，普遍存在一个问题，就是教学主要以教师分散授课为主，辅以少量甚至没有参观。学员们无法全面系统地了解物流运作的整个过程，除少量悟性较高的学员外，大多数学员的物流知识结构比较凌乱。 1.3 传统实训方式已不能满足学生和企业的需要 学生实训要求在类似企业实际的环境下，并且实训的设备、软件必须是企业实际应用的，或在企业实际应用基础上改造过来。 随着国内教育教学改革的深入，实训方式创新层出不穷，旧有的实训方式尤其是模拟仿真远远不能满足现有教学的需要。 2 物流实训室设计理念 通过实训室对各节点模拟，从而展现货物的入库、仓储、流通加工、配送、出库等第三方物流企业的供应链流程。在此模拟的供应链上，配备一系列模块化的现代物流设施，如：全自动立体仓库、电子标签辅助拣货系统、电子看板，RF手持设备等，它们各自独立，又互为联系，充分体现了传统的物流运行过程通过信息化实现其战略决策系统化，管理现代化和作业自动化这一现代物流的时代特征，从而在学校实训室内营造了一个类似真实的集物资流和信息流于一体的实训教学环境。 3 实训室方案规划设计 物流实训室平面布局 主要组成部分： 全自动立体仓库及自动分拣：立体货架、全自动堆垛机及输送装置等； 普通仓储货架：重型及轻型货架； 电子标签拣货系统：重力式货架、电子标签分拣系统及拣货台等； 打包封装：多种款式的打包设备； 条码及射频系统：RF手持终端、条码打印机及多种条码阅读设备； 管理岗位：物流软件、PC及桌椅。 4 实训系统功能 之所以要在学校实训室条件下，构建一个类似真实的以第三方物流服务单元为核心的供应链仿真系统，其真实目的是想以此为学校进行现代供应链物流运作管理等相关课程的课堂理论教学提供一个有效的辅助教学手段，并为学生掌握各种现代化，自动化的物流设施设备的操作技能，提供一个实实在在的实训平台。 所以从这个意义上说，我们这套实训系统应具有以下教学实训功能： 4.1 了解和学习物流管理的内容和技术 1、仓储管理系统的操作训练 《算法分析与设计》试卷(A) （时间90分钟满分100分） 一、填空题（30分,每题2分）。 1．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法2．在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( B ). A.回溯法 B.分支限界法 C.回溯法和分支限界法 D.回溯法求解子集树问题 3．实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法4．.广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法5．衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 6．Strassen矩阵乘法是利用（ A）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7. 使用分治法求解不需要满足的条件是（ A ）。 A 子问题必须是一样的 B 子问题不能够重复 C 子问题的解可以合并 D 原问题和子问题使用相同的方法解 8．用动态规划算法解决最大字段和问题，其时间复杂性为( B ). A.logn B.n C.n2 D.nlogn 9.解决活动安排问题，最好用（ B ）算法 A.分治 B.贪心 C.动态规划 D.穷举 10.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A．递归函数 B.剪枝函数C。随机数函数 D.搜索函数11. 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( C )之外都是最常见的方式. A.队列式分支限界法 B.优先队列式分支限界法 C.栈式分支限界法 D.FIFO分支限界法 12. .回溯算法和分支限界法的问题的解空间树不会是( D ). A.有序树 B.子集树 C.排列树 D.无序树 13.优先队列式分支限界法选取扩展结点的原则是（ C ）。 A、先进先出 B、后进先出 C、结点的优先级 D、随机14．下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解15．回溯法在解空间树T上的搜索方式是( A ). A.深度优先 B.广度优先 C.最小耗费优先 D.活结点优先 二、填空题（20分,每空1分）。 1.算法由若干条指令组成的又穷序列，且满足输入、输出、 确定性和有限性四个特性。 2.分支限界法的两种搜索方式有队列式(FIFO)分支限界法、优先队列式分支限界法，用一个队列来存储结点的表叫活节点表。 遗传算法合集 遗传算法简介 遗传算法是一类模拟生物进化的智能优化算法，它是由J.H.Holland于六十年代提出的。目前，遗传算法已成为进化计算研究的一个重要分支。 与传统优化方法相比，遗传算法的优点是： ·群体搜索 ·不需要目标函数的导数 ·概率转移准则 遗传算法研究热点 ·收敛性证明 ·新型高效的遗传算子设计 ·遗传算法与局部优化算法的结合 ·遗传算法在各领域的应用研究 ·软计算与计算智能中的遗传算法 遗传算法著作 1.陈国良等，遗传算法及其应用，国防出版社 2.J.H.Holland,Adaptation in Natural and Artificial Systems, Ann Arbor: Univ. of Michigan Press, 1975 3.D.E.Goldberg,Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989 4.L.D.Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold 5.Z.Michalewicz, Genetic Algorithms + Data Structures=Evolution Programs, Spinger Press,1996 6.M.Gen,R.Cheng,Genetic Algorithms & Engineering Design, 1997 7.Wiely,Genetic Algorithms in Engineering and Computer Science,1995 8.M.Mitchell,An Introducion to Genetic Algorithms,1996 9.Davis,Genetic Algorithms and Simulated Annealing,1987 10.Davidor,Genetic Algorithms and Robotics,1991 11.Koza,Genetic Programming,1992 12.Bauer,Genetic Algorithms and Investiment Strategies,1994 遗传算法站点 1.The Genetic Algorithms Archive https://www.doczj.com/doc/559521008.html,/galist/ 2.Genetic Adaptive Systems LAB (GASLAB) GASLAB is hosted by the Computer Science Department of the University of Nevada-Reno. https://www.doczj.com/doc/559521008.html,/~sushil/papers/conference/conf.html https://www.doczj.com/doc/559521008.html,/ 3.http://www.mat.sbg.ac.at/~uhl/GA.html 4.https://www.doczj.com/doc/559521008.html,/research/gag/ email:kdejong@https://www.doczj.com/doc/559521008.html, publications: (downloading website) https://www.doczj.com/doc/559521008.html,/research/gas/pubs.html 5.Illinois Genetic Algorithms Laboratory Prof. David E. Goldberg, Director https://www.doczj.com/doc/559521008.html,./illigal.home.html 6.Michigan State University Genetic Algorithms Research and Applications Group (GARAGE) Bill Punch (punch@https://www.doczj.com/doc/559521008.html,,517-353-3541) Erik Goodman (goodman@https://www.doczj.com/doc/559521008.html,,517-355-6453) https://www.doczj.com/doc/559521008.html,/ 左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (6) 3.1 左偏树的合并 (6) 3.2 插入新节点 (8) 3.3 删除最小节点 (9) 3.4 左偏树的构建 (9) 3.5 删除任意已知节点 (10) 3.6 小结 (13) 四、左偏树的应用 (15) 4.1 例——数字序列（Baltic 2004） (15) 五、左偏树与各种可并堆的比较 (18) 5.1 左偏树的变种——斜堆 (18) 5.2 左偏树与二叉堆的比较 (19) 5.3 左偏树与其他可并堆的比较 (19) 六、总结 (22) 在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html, 【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。 在线代理|网页代理|代理网页|https://www.doczj.com/doc/559521008.html, 算法设计与分析考试题 及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】 一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分，衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ，先求解_子问题 ，然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。 步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}； 最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为： 该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj 设计方案范文合集八篇 设计方案范文合集八篇 为了确保事情或工作有序有力开展，常常需要预先准备方案，方案属于计划类文书的一种。方案应该怎么制定呢？以下是收集整理的设计方案8篇，仅供参考，希望能够帮助到大家。 设计方案篇1 一、活动目的 1、培养学生合作探究的精神与分析问题、解决问题的能力。 2、培养和增强学生的地理学习兴趣，关注身边的地理知识。 3、懂得多渠道收集课外资料。 二、活动时间及地点 三、活动方式 根据课室座位安排情况，以小组为单位，每两排组成一组，共分为四大组。以“野外考察员的困难”为主要内容，展开几个阶段的小组间的地理知识竞赛。 四、参与人员 全体同学 五、活动流程 活动刚开始，教师以一名“地理野外考察员”的身份登场，讲述他一天所遇到的困难。困难一：迷失了方向 1、活动准备 在活动前的地理课，向学生提出“当你迷失野外，你该如何来辨别方向”这一问题，让学生课后根据自己的生活经验或向有经验的长辈请教等各类方式收集有关方法，并以作业形式上交。 2、活动过程 学生以小组为单位，全组成员上交一份解决方法，教师当场逐一宣读，答对1个得1分，答错不得分。 3、活动小结 教师讲解野外辨别方向常用的几种方法。 附： 1）平时参考地图和指南针，同时积极观察周围的地形以及身边的植物来判断正确位置。 2）利用太阳 ①冬季日出位置是东偏南，日落位置是西偏南；夏季日出位置是东偏北，日落位置是西偏北；春分、秋分前后，日出正东，日落正西。 ②只要有太阳，就可以使用手表来辨别方向。按24小时制读出当时的时刻，将小时数除以二，将得到一个小时数。把手表水平放在手上或者地上，让手表的这个时刻对准太阳所在的方位，这时手表表面12点所指的方向是北方，6点所指的方向是南方。 设计方案篇2 1、幼儿园的功能组成 包括幼儿生活用房、服务用房、和供应用房三部分。 2、幼儿园的功能分析 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 参考答案 一、填空 1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、正确的 三、简答题 1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、解：① 因为：;01 -10n n )1-10n n (lim 22 2=+-+→∞n n 由渐近表达式的定义易知： 1-10n n 2 2+是n ;的渐近表达式。 ② 因为：;0n 1/ 5/n 1414)n 1/ 5/n 14(lim 22=++-++∞→n 由渐近表达式的定义易知： 14是14+5/n+1/ n 2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 四、算法设计题 1、按照单位效益从大到小依次排列这7个物品为：FBGDECA 。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】 5x =6x =7x = 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 计划方案合集10篇 计划方案合集10篇 为了确保我们的努力取得实效，通常会被要求事先制定方案，方案是在案前得出的方法计划。那么什么样的方案才是好的呢？下面是小编帮大家整理的计划方案10篇，仅供参考，大家一起来看看吧。计划方案篇1 各林场(所)：为进一步深入贯彻《甘肃省自然保护区条例》及《XX市人民政府关于进一步加强封山禁牧工作的通知》和《XX林业总场封山禁牧管理暂行办法》精神，巩固XX林区近年来的封山禁牧成果，加快生态环境建设步伐，现就我场XX年封山禁牧工作安排如下：一、明确指导思想我场的封山禁牧工作，坚持统筹规划，以封为主，禁牧与圈养、恢复生态和保护林农利益相结合的指导思想，按照《森林法》、《森林法实施条例》及市局、总场关于封山禁牧工作的总体部署和要求，坚持把加强封山禁牧工作作为恢复植被、改善生态、提高林木尽快成林的重要措施，作为改善人居环境，促进人与自然和谐相处，构建和谐林区的重要保障。各林场（所）要从促进林区经济社会可持续发展的大局出发，切实增强责任感和紧迫感，采取切实有效的措施，加大工作力度，真正把封山禁牧工作抓紧抓好，确保取得实效。二、细化工作任务一要提高认识，统筹安排，强化责任，分解任务。各林场（所）主要领导要切实提高认识，将封禁工作放在同林业生产同等重要的位置上，同安排同部署，并根据市局、总场封禁工作会议精神，延伸签订封禁工作目标管理责任书，确保封禁工作责任分解到站，细化到人。二要广泛宣传动员，营造良好舆论氛围。各林场（所）要采取召开干部会、群众大会、养殖户专题会、管护人员工作会、发放宣传资料、刷写宣传标语、悬挂横幅、制做固定宣传碑等多种形式，广泛宣传《森林法》、《森林法实施条例》、《XX 市人民政府关于进一步加强封山禁牧工作的通知》《XX、林业总场封山禁牧管理暂行办法》等有关政策法规文件，教育林区群众充分认识封山禁牧的重大意义，明确封山禁牧的范围、措施和责任，引导群众正确处理长远利益与当前利益、整体利益与局部利益、封山禁牧与畜牧养殖的关系，真正把封山禁牧工作变为广大群众的自觉行动，为封山禁牧创造良好的舆论氛围。三要详细调查摸底，掌握 《算法分析与设计》试题库 （一） 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B.分支限界法 C.分治法 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move( n, a,b); hanoi(n-1, C, B, A); 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座 B 上，并 D.动态规划算法 3. 动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C.最优子结构性质与重叠子问题性质 D.预排序与递归调用 4. 算法分析中，记号0表示(B),记号0表示(A),记号。表示(D) A. 渐进下界 B. 渐进上界 C. 非紧上界 D. 紧渐进界 E. 非紧下界 5. 以下关于渐进记号的性质是正确的有：(A) A. f(n) - P(g(n)),g(n) - 心(h(n))二f(n) - P(h(n)) B. f(n) =0(g(n)),g(n) =0(h(n))二h(n) =0(f(n)) C. O(f(n ))+0(g( n)) = O(mi n{f(n ),g( n)}) D. f(n) =0(g(n)) = g(n) -0(f (n)) 6?能采用贪心算法求最优解的问题，一般具有的重要性质为：(A) A. 最优子结构性质与贪心选择性质 B ?重叠子问题性质与贪心选择性质 C. 最优子结构性质与重叠子问题性质 D. 预排序与递归调用 7.回溯法在问题的解空间树中，按(D)策略，从根结点出发搜索解空间树。 A. 广度优先 B.活结点优先 C.扩展结点优先 D.深度优先 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则。由此设计出解Hanoi 塔问题的递归算确的为：（B ） 3. 动态规划算法的基本要素为（C ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O 表示（B ）， 记号Ω表示（A ）， 记号Θ表示（D ）。 A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A ） A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ?=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f (n)O(g(n))g(n)O(f (n))=?= 6. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（A ） A. 最优子结构性质与贪心选择性质B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质D. 预排序与递归调用 7. 回溯法在问题的解空间树中，按（D ）策略，从根结点出发搜索解空间树。 A ． 广度优先 B. 活结点优先 C.扩展结点优先 D. 深度优先 Hanoi 塔 B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 计算智能 习题总集 习题一： 空缺 习题二： 1、在反馈型神经网络中，有些神经元的输出被反馈至神经元的（ ） A ．同层 B ．同层或前层 C ．前层 D ．输出层 2、在神经网络的一个节点中，由激励函数计算得到的数值是该节点的（ ） A ．实际输出 B ．实际输入 C ．期望输出 D ．期望值 3、在神经网络的一个节点中，由激励函数计算得到的数值，是与该节点相连的下一个节点的（ ） A ．实际输出 B ．实际输入 C ．期望输出 D ．期望值 4、下面的学习算法属于有监督学习规则的是（ ） A ．Hebb 学习规则 B ．Delta 学习规则 C ．概率式学习规则 D ．竞争式学习规则 E ．梯度下降学习规则 F ．Kohonen 学习规则 5、BP 算法适用于（ ） A ．前馈型网络 B ．前馈内层互联网络 C ．反馈型网络 D ．全互联网络 6、BP 神经网络采用的学习规则是（ ） A ．联想式Hebb 学习规则 B ．误差传播式Delta 学习规则 C ．概率式学习规则 D ．竞争式学习规则 习题三： 1、设论域U ={u 1, u 2, u 3, u 4, u 5}, 5 432118.06.04.02.0u u u u u A ++++＝， 5 43214.06.016.04.0u u u u u B ++++＝， 求 B A B A , , , 。 2、设X ={1, 5, 9, 13, 20}, Y ={1, 5, 9, 13, 20}, ~ R 是模糊关系“x 比y 大得多”。 隶属度函数： 求模糊关系矩阵~ R 3、 4、Zadeh 教授提出了著名的不相容原理，是指复杂系统的那两种矛盾（ ） A ．精确性和有效性 B ．精确性和模糊性 C ．模糊性和有效性 D ．复杂性和模糊性 5、在模糊推理得到的模糊集合中取一个最能代表这个集合的单值的过程称为（ ） A ．去模糊 B ．模糊化 C ．模糊推理 D ．模糊集运算 6、判断 1．一个模糊集合可以被其隶属度函数唯一定义（ ） 2．隶属度越大表示真的程度越高；隶属度越小表示真的程度越低（ ） 3．当隶属度函数有若干点取值为1，其余点取值为0时，该隶属度函数对应的模糊集 合可以看作一个经典集合（ ） 7、简答题：试述模糊计算的主要模块及其操作内容。 ???????≥-<-<-≤-=101100100 0),(~y x y x y x y x y x R ，，， 《算法分析与设计》期末复习题(一) 一、 选择题 1.应用Johnson 法则的流水作业调度采用的算法是（D ） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi 塔问题如下图所示。现要求将塔座A 上的的所有圆盘移到塔座B 上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi 塔问题的移动规则。由此设计出解Hanoi 塔问题的递归算法正确的为：（B ） Hanoi 塔 A. void hanoi(int n, int A, int C, int B) { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); } B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } D. void hanoi(int n, int C, int A, int B) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } 3.动态规划算法的基本要素为（C） A. 最优子结构性质与贪心选择性质 B．重叠子问题性质与贪心选择性质 精选方案策划合集5篇 方案策划篇1 一、日本寿司店的总体目标 2. 产品定价及收入目标 产品定价寿司：甜鸡蛋寿司 12元加州反卷寿司12元烤鳗鱼寿司 12元樱花反卷寿司12元香辣牛肉寿司12元鱼松蟹棒寿司12元鱼松火腿寿司12元金枪鱼寿司8元球生菜寿司8元紫薯红薯寿司8元鱼松寿司 8元红心蛋黄寿司 8元飞鱼子寿司8元什锦色拉寿司 7元水果寿司 7元果冻寿司 6元火腿寿司 6元手卷：黄瓜手卷 5元／2个鱼松手卷 7元／2个金枪鱼手卷7元／2个色拉手卷 7元／2个烤鳗鱼手卷7元／2个饭团：红心蛋黄饭团 5元／2个紫薯饭团 5元／2个鱼松饭团 7元／2个金枪鱼饭团7元／2个火腿饭团 7元／2个预计每日将会有50份订单，每份订单平均10元，平均每份订单成本3元利润7元。每日将获得利润10x50=500元每日将获纯利润7x50=350元 收入目标 月收入：20190.00元年收入：240000.00元 员工工资以及支出经费：40000.00元年净收入：201900.00元 3. 发展目标 将日本寿司店发展成特色小资情调的店子。主要顾客为情侣、中 高消费水平学生、喜爱日韩的女生等。 本店以优雅的环境，日本特色的风味为主打。在提供就餐的同时能享受到不一样的优质服务。且寿司分为中高档，既能满足高消费水平学生的消费欲望，同时满足一般学生的购买能力。 立志将日本寿司店在我校附近立足，并以优质传统的特色服务收揽各新老顾客。 二、市场状况分析 1. 市场需求 自然生长的稻米和最新鲜的鱼生，用极致简单又饶有趣味的生食方式组合在一起，寿司已经迅速发展成为全世界都无法抗拒的美味新宠。寿司风潮正全面来袭。走进店堂，就可以看到一碟碟的寿司由传送带传送着，从眼前回转而过。自己伸手从传送带上取下自己爱吃的寿司，最后根据所吃的碟数来结账，这就是寿司。因其价格低廉、轻松随意，已经越来越受到普通消费者的欢迎。 作为全世界正越来越风行的日本寿司，正被越来越多追求品位和健康的人所钟爱。纽约、巴黎、伦敦、悉尼、香港，时髦都市中的寿司店，门前永远不缺时髦男女耐心排长队。寿司经营店也在中国不断增长。什么原因呢？它的魅力在于：第一、口味鲜美, 而且丰富多样的品种满足了不同口味、不同喜好的人们。寿司的制作原料可谓包罗万象, 不拘一格，从鱼类、贝类到牛肉、禽蛋甚至蔬菜、瓜果都可以制成风味各异的寿司。 第二、寿司符合人们健康饮食的标准。日本饮食在养生方面具有 算法分析与设计复习题及答案一、单选题 1．D 2．B 3．C 4．D 5．D 6．D 7．C 8．D 9．B 10．C 11．D 12．B 13．D 14．C 15．C 16．D 17．D 18．D 19．D 20．C 1．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 2．根据执行算法的计算机指令体系结构，算法可以分为（）。 Ａ精确算法与近似算法Ｂ串行算法语并行算法 Ｃ稳定算法与不稳定算法Ｄ３２位算法与６４位算法 3．具有１0个节点的完全二叉树的高度是（）。 Ａ６Ｂ５Ｃ3Ｄ 2 4．下列函数关系随着输入量增大增加最快的是（）。 Ａlog2n B n2 C 2n D n! 5．下列程序段的S执行的次数为( )。 for i ←0 to n-1 do for j ←0 to i-1 do s //某种基本操作 A.n2 B n2/2 C n*(n+1) D n(n+1)/2 6．Fibonacci数列的第十项为( )。 A 3 B 13 C 21 D 34 7．4个盘子的汉诺塔，至少要执行移动操作的次数为( )。 A 11次 B 13次 C 15次 D 17次 8．下列序列不是堆的是（）。 A 99，85，98，77，80，60，82，40，22，10，66 B 99，98，85，82，80，77，66，60，40，22，10 C 10，22，40，60，66，77，80，82，85，98，99 D 99，85，40，77，80，60，66，98，82，10，22 9．Strassen矩阵乘法的算法复杂度为（）。 ＡΘ(n3)ＢΘ(n2.807) ＣΘ(n2) ＤΘ(n) 10．集合A的幂集是（）。 A．A中所有元素的集合 B. A的子集合 C． A 的所有子集合的集合 D. 空集 11．与算法英文单词algorithm具有相同来源的单词是（）。 A logarithm B algiros C arithmos D algebra 12．从排序过程是否完全在内存中显示，排序问题可以分为（）。 Ａ稳定排序与不稳定排序Ｂ内排序与外排序 Ｃ直接排序与间接排序Ｄ主排序与辅助排序 13．下列（）不是衡量算法的标准。 Ａ时间效率Ｂ空间效率 Ｃ问题难度Ｄ适应能力 14．对于根树，出度为零的节点为（）。 Ａ０节点Ｂ根节点Ｃ叶节点Ｄ分支节点 15．对完全二叉树自顶向下，从左向右给节点编号，节点编号为１0的父节点编号为（）。 Ａ０Ｂ２Ｃ４Ｄ６ 16．下列程序段的算法时间的复杂度为（）。 for i ←0 to n do for j ←0 to m do 【实用】工作计划合集六篇 工作计划篇1 为了贯彻落实“安全第一，预防为主，综合治理”的方针，强化安全生产目标管理。结合工厂实际，特制定20xx年安全生产工作计划，将安全生产工作纳入重要议事日程，警钟长鸣，常抓不懈。 一、下半年目标 实现下半年无死亡、无重伤、无重大生产设备事故，无重大事故隐患，工伤事故发生率低于厂规定指标，综合粉尘浓度合格率达80%以上（如下表）。 二、指导思想 要以公司对20xx年安全生产目标管理责任为指导，以工厂安全工作管理制度为标准，以安全工作总方针“安全第一，预防为主。”为原则，以车间、班组安全管理为基础，以预防重点单位、重点岗位重大事故为重点，以纠正岗位违章指挥，违章操作和员工劳动保护穿戴为突破口，落实各项规章制度，开创安全工作新局面，实现安全生产根本好转。 三、牢固树立“安全第一”的思想意识 各单位部门要高度重视安全生产工作，把安全生产工作作为重要的工作来抓，认真贯彻“安全第一，预防为主”的方针，进一步增强安全生产意识，出实招、使真劲，把“安全第一”的方 针真正落到实处，通过进一步完善安全生产责任制，首先解决领导意识问题，真正把安全生产工作列入重要议事日程，摆到“第一”的位置上，只有从思想上重视安全，责任意识才能到位，才能管到位、抓到位，才能深入落实安全责任，整改事故隐患，严格执行“谁主管，谁负责”和“管生产必须管安全”的原则，力保安全生产。 四、深入开展好安全生产专项整治工作 根据工厂现状，确定出20xx年安全生产工作的重点单位、重点部位，完善各事故处理应急预案，加大重大隐患的监控和整改力度，认真开展厂级月度安全检查和专项安全检查，车间每周进行一次安全检查，班组坚持班中的三次安全检查，并要求生产科、车间领导及管理人员加强日常安全检查，对查出的事故隐患，要按照“三定四不推”原则，及时组织整改，暂不能整改的，要做好安全防范措施，尤其要突出对煤气炉、锅炉、硫酸罐、液氨罐等重要部位的安全防范，做好专项整治工作，加强对易燃易爆、有毒有害等危险化学品的管理工作，要严格按照《安全生产法》、《危险化学品安全管理条例》强化专项整治，加强对岗位现场的安全管理，及时查处违章指挥，违章操作等现象，限度降低各类事故的发生，确保工厂生产工作正常运行。 五、继续加强做好员工安全教育培训和宣传工作 工厂采取办班、班前班后会、墙报、简报等形式，对员工进行安全生产教育，提高员工的安全生产知识和操作技能，定期或 《算法分析与设计》期末试题及参考答案 一、简要回答下列问题： 1.算法重要特性是什么？ 1.确定性、可行性、输入、输出、有穷性 2. 2.算法分析的目的是什么？ 2.分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法。 3. 3.算法的时间复杂性与问题的什么因素相关？ 3. 算法的时间复杂性与问题的规模相关，是问题大小n的函数。 4.算法的渐进时间复杂性的含义？ 4．当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。 5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？ 5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的 算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度： W(n) = max{ T(n，I) } , I∈Dn 平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和： A(n) =∑P(I)T(n，I) I∈Dn 6.简述二分检索（折半查找）算法的基本过程。 6. 设输入是一个按非降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x比较， 如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]最新设计方案范文合集6篇
算法分析与设计试卷
遗传算法合集
算法合集之《左偏树的特点及其应用》
算法设计与分析考试题及答案
设计方案范文合集八篇
算法设计与分析试卷A及答案
算法设计与分析考试题及答案
计划方案合集10篇
5.《算法设计与分析》试题库
算法分析期末试题集答案
计算智能习题合集
算法分析期末试题集规范标准答案(6套)
精选方案策划合集5篇
算法分析与设计复习题及答案
【实用】工作计划合集六篇
《算法分析与设计》期末试题及参考答案
相关主题
文本预览