当前位置:文档之家› 遗传算法设计与实现----上机大作业201504

遗传算法设计与实现----上机大作业201504

遗传算法设计与实现----上机大作业201504
遗传算法设计与实现----上机大作业201504

算法设计与分析(作业三)

算法设计与分析实验报告 学院信息科学与技术学院 专业班级软件工程3班 学号 20122668 姓名王建君 指导教师尹治本 2014年10月

实验四 矩阵相乘次序 一、问题提出 用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n },其中A i 与A i+1是可乘的,i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为: (1)单个矩阵是完全加括号的; (2)矩阵连乘积A 是完全加括号的,则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号,即A=(BC)。 例如,矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式:(A 1(A 2(A 3A 4))),(A 1((A 2A 3)A 4)),((A 1A 2)(A 3A 4)),((A 1(A 2A 3))A 4),(((A 1A 2)A 3)A 4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序,这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵,B 是一个q ×r 矩阵,则计算其乘积C=AB 的标准算法中,需要进行pqr 次数乘。 (3)为了说明在计算矩阵连乘积时,加括号方式对整个计算量的影响,先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100,100×5,5×50。加括号的方式只有两种:((A 1A 2)A 3),(A 1(A 2A 3)),第一种方式需要的数乘次数为10×100×5+10×5×50=7500,第二种方式需要的数乘次数为100×5×50+10×100×50=75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见,在计算矩阵连乘积时,加括号方式,即计算次序对计算量有很大的影响。于是,自然提出矩阵连乘积的最优计算次序问题,即对于给定的相继n 个矩阵{A 1,A 2,…,A n }(其中矩阵Ai 的维数为p i-1×p i ,i =1,2,…,n ),如何确定计算矩阵连乘积A 1A 2…A n 的计算次序(完全加括号方式),使得依此次序计算矩阵连乘积需要的数乘次数最少。 二、求解思路 本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是: 1)计算最优值算法MatrixChain():建立两张表(即程序中的**m 和**s ,利用二维指针存放),一张表存储矩阵相乘的最小运算量,主对角线上的值为0,依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量,其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得,最后一次求得的值即为n 个矩阵相乘的最小运算量;另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback():矩阵结合即是给矩阵加括号,打印出矩阵结合方式,由递归过程Traceback()完成。分三种情况: (1)只有一个矩阵,则只需打印出A1; (2)有两个矩阵,则需打印出(A1A2); (3)对于矩阵数目大于2,则应该调用递归过程Traceback()两次,构造出最优加括号方式。 三、算法复杂度 该算法时间复杂度最高为)(n 3 O 。 四、实验源代码

遗传算法

基于新的混合遗传算法的订单生产工序顺序相关的流水车 间调度问题研究 A novel hybrid genetic algorithm to solve the make-to-order sequence-dependent flow-shop scheduling problem Mohammad Mirabi ?S. M. T. Fatemi Ghomi ?F. Jolai 2013年5月29号收到该文献,2014年3月18号录取,2014年4月9日出版.作者(2014).这篇文章在开放存取的https://www.doczj.com/doc/e67055515.html, 网站发表 摘要流水车间调度问题(FSP)用于处理m台机器n个工序的流水作业。尽管FSP是典 型的NP-hard问题,依然没有有效的算法以找到这个问题的最优解。为了减少库存,延迟和安装成本,在工作时间一定,序列相关的每台机器上解决流水车间调度排序问题,在这提出了一种有三个遗传算子的新型混合遗传算法(HGA)。该算法应用一种改进的方法来生成初始种群,并使用一种应用迭代交换过程改进初始解的改进启发式算法。我们认为订单式生产方式,工序间隔时间是基于最大安装成本的禁忌搜索算法的解。此外,与最近开发的启发式算法通过计算实验结果比较表明,该算法在解\的精度和效率方面表现出非常强的竞争力。 关键词:混合遗传算法流水作业调度序列相关 引言 流车间调度问题(FSP)作为在制造业研究的主要问题已经近七十年。在一个有M台机器的流水作业车间中有m个工位,每个工序又有一台或几台机器。此外,有n个工件在m个工位上依次加工。在经典的流水作业问题里,每个工位都有一台机器,这一领域的研究吸引了最多的人次。FSP的两个主要子问题是序列独立时间设置(SIST)和顺序相关时间设置(SDST)。SDST流水作业问题更具有现实意义,但是吸引的注意力却少得多,特别是2000年以前(Allahverdi等,2008) 在流水车间调度问题的目标是找到一个序列的机器加工的作业,以便一个给定的标准进行了优化。这里有n个工件在每台机器上操作的可能的顺序,以及(N!)*M个的可能处理顺序。流水作业调度的研究通常只参加置换序列,其中操作的处理顺序是所有机器。在这里,我们也采用这种限制。 最小化所有最大完工时间作业(成为完工期并通过的Cmax表示)是公知的,也是在文献M. Mirabi (&) Group of Industrial Engineering, Ayatollah Haeri University of Meybod, P.O. Box 89619-55133, Meybod, Iran e-mail: M.Mirabi@https://www.doczj.com/doc/e67055515.html, S. M. T. Fatemi Ghomi Department of Industrial Engineering, Amirkabir University of Technology, P.O. Box 15916-34311, Tehran, Iran e-mail: Fatemi@aut.ac.ir F. Jolai Department of Industrial Engineering, College of Engineering, University of Tehran, P.O. Box 14395-515, Tehran, Iran

算法分析与设计作业及参考答案样本

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成 绩记入课程总成绩。 客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接 调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )

A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、 形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定 长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优 先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策 有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的 解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:

北航数值分析大作业第一题幂法与反幂法

《数值分析》计算实习题目 第一题: 1. 算法设计方案 (1)1λ,501λ和s λ的值。 1)首先通过幂法求出按模最大的特征值λt1,然后根据λt1进行原点平移求出另一特征值λt2,比较两值大小,数值小的为所求最小特征值λ1,数值大的为是所求最大特征值λ501。 2)使用反幂法求λs ,其中需要解线性方程组。因为A 为带状线性方程组,此处采用LU 分解法解带状方程组。 (2)与140k λλμλ-5011=+k 最接近的特征值λik 。 通过带有原点平移的反幂法求出与数k μ最接近的特征值 λik 。 (3)2cond(A)和det A 。 1)1=n λλ2cond(A),其中1λ和n λ分别是按模最大和最小特征值。 2)利用步骤(1)中分解矩阵A 得出的LU 矩阵,L 为单位下三角阵,U 为上三角阵,其中U 矩阵的主对角线元素之积即为det A 。 由于A 的元素零元素较多,为节省储存量,将A 的元素存为6×501的数组中,程序中采用get_an_element()函数来从小数组中取出A 中的元素。 2.全部源程序 #include #include void init_a();//初始化A double get_an_element(int,int);//取A 中的元素函数 double powermethod(double);//原点平移的幂法 double inversepowermethod(double);//原点平移的反幂法 int presolve(double);//三角LU 分解 int solve(double [],double []);//解方程组 int max(int,int); int min(int,int); double (*u)[502]=new double[502][502];//上三角U 数组 double (*l)[502]=new double[502][502];//单位下三角L 数组 double a[6][502];//矩阵A int main() { int i,k; double lambdat1,lambdat2,lambda1,lambda501,lambdas,mu[40],det;

AI人工智能的几种常用算法概念

一、粒子群算法 粒子群算法,也称粒子群优化算法(Particle Swarm Optimization),缩写为PSO,是近年来发展起来的一种新的进化算法((Evolu2tionary Algorithm - EA)。PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的交叉(Crossover) 和变异(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性。 优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题.为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度.爬山法精度较高,但是易于陷入局部极小.遗传算法属于进化算法(EvolutionaryAlgorithms)的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解.遗传算法有三个基本算子:选择、交叉和变异.但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995年Eberhart博士和kennedy博士提出了一种新的算法;粒子群优化(ParticalSwarmOptimization-PSO)算法.这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性. 粒子群优化(ParticalSwarmOptimization-PSO)算法是近年来发展起来的一种新的进化算法(Evolu2tionaryAlgorithm-EA).PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价

最新算法分析与设计作业(一)及参考答案讲课讲稿

《算法分析与设计》作业(一) 本课程作业由两部分组成。第一部分为“客观题部分”,由15个选择题组成,每题1分,共15分。第二部分为“主观题部分”,由简答题和论述题组成,共15分。作业总分30分,将作为平时成绩记入课程总成绩。 客观题部分: 一、选择题(每题1分,共15题) 1、递归算法:(C ) A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题,这些子问题:(D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是:(C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的:(A ) A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是:( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是:(B) A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是:(A) A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序可以不满足如下性质:(D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是:(A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题:( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是:(A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法:( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到:(C ) A、全局最优解 B、0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是:(A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:( A ) A、舍伍德算法 B、蒙特卡罗算法 C、拉斯维加斯算法 D、数值随机化算法 主观题部分: 二、写出下列程序的答案(每题2.5分,共2题) 1、请写出批处理作业调度的回溯算法。 #include #include using namespace std; class Flowing { friend int Flow(int ** ,int ,int []); private: //int Bound(int i); void Backtrack(int t); int **M;// int *x;//当前解

(整理)遗传算法作业

作业 土规1101班刘迈克2011306200521 求下面加权有向图中从A到G的最短路径。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 5 8 3 3 3 8 4 2 2 2 1 3 3 3 5 5 2 6 6 4 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 5 3 1 3 6 8 7 6 6 5 8 3 3 3 8 4 2 2 2 1 3 3 3 5 5 2 6 6 4 3

解: 基本思路: 第一步:确定决策变量及其约束条件。 第二步:建立优化模型。 第三步:确定编码方法。 第四步:确定解码方法。 第五步:确定个体评价方法。 第六步:设计遗传算子。 选择运算使用比例选择算子; 交叉运算使用单点交叉算子; 变异运算使用基本位变异算子。 第七步:确定遗传算法的运行参数。 程序: % n ---- 种群规模 % ger ---- 迭代次数 % pc ---- 交叉概率 % pm ---- 变异概率 % v ---- 初始种群(规模为n) % f ---- 目标函数值 % fit ---- 适应度向量 % vx ---- 最优适应度值向量 % vmfit ---- 平均适应度值向量 clear all; close all; clc; tic; % 生成初始种群 %power=[0 5 3 100 100 100 100 100; % 100 0 100 1 3 6 100 100; % 100 100 0 100 8 7 6 100; % 100 100 100 0 100 100 100 8; % 100 100 100 100 0 100 100 5; % 100 100 100 100 100 0 100 3; % 100 100 100 100 100 100 0 3; % 100 100 100 100 100 100 100 0]; power=[0 5 3 100 100 100 100 100 100 100 100 100 100 100 100 100; 100 0 100 1 3 6 100 100 100 100 100 100 100 100 100 100; 100 100 0 100 8 7 6 100 100 100 100 100 100 100 100 100;

软件系统分析与设计大作业

《软件系统分析与设计》 期末大作业 选题名称:游戏平台管理系统设计人:徐文豪刘青海 赖超宇甘智宏 班级:软工143班 南昌大学软件学院 2016.6.1

目录 一、整体描述 (2) 二、需求分析 (3) 三、系统功能概况 (4) 四、类的属性与方法 (5) 五、系统界面界限 (11) 六、设计模型 (13) 七、设计原则 (17) 八、设计模式······················

一、整体描述 随着移动通讯的发展,手机应用也越来越多,其中,游戏应用占据了很大的比重,游戏平台管理系统是整合了大量游戏应用,以及玩家线上交流的平台。 主要受众群:拥有移动端或电脑端的人群。 应用前景:移动互联的发展为游戏平台的发展提供了很大的生存空间,应用前景十分广阔 盈利方式:向平台中游戏的开发商收取一定的费用,游戏玩家向游戏中注入资金时,收取一定比例的游戏收入。 面临的困难:游戏平台前期的推广,提高游戏平台本身对开发商和游戏玩家的吸引力,游戏平台能否适应大部分游戏玩家的要求。 玩家首先要注册账号,然后就可以在上面下载游戏应用,上传自己的游戏资源。同时,根据玩家的活跃程度获取相应积分,用积分可以兑换游戏礼包,也会根据玩家等级在游戏装备上给与相应的优惠和等级奖励。玩家在每一款游戏的评论区都可以交流游戏经验,提出意见和建议,以便游戏及时更新,弥补相应不足。玩家也可以建立游戏工会,不同游戏的玩家都可以加入,分享自己的游戏心得或者转赠游戏装备或积分。

二、需求分析 时间when:游戏厂商:随时;注册用户:随时;管理人员:正常工作时间。 地点Where:游戏厂商,管理人员:工作地点;注册用户:随地 人员who:游戏厂商,管理人员,注册用户, What:游戏厂商:推广游戏,管理人员:扩大服务,盈利;注册人员:玩游戏。 Why:游戏厂商:推广力度不大,效果不好,管理人员:方便管理,注册用户:良好的游戏环境。 性能Performance:系统提供服务的效率,响应时间快,由于是手机端的APP吞吐量不需要太大。 成本Cost:实现系统需要付出的代价,耗费****元 时间Time:2016年6月3日 可靠性Reliability: 需要系统长时间正确运行的能力 安全性Security: 由于该平台会涉及资金的流动,所以需要对信息安全的保护能力。 合规性Compliance: 需要符合各种行业的标准,法律法规,规范。技术性Technology:要求基于安卓平台开发。 兼容性Compatibility:需要与一些支付平台进行兼容能力。还有对游戏的兼容性。

人工智能遗传算法实验报告

人工智能实验报告 学号: 姓名: 实验名称:遗传算法 实验日期:2016.1.5

【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理,熟悉遗传算法的运行机制,学会用遗传算法来求解问题。 【实验原理】 遗传算法( Genetic Algorithm )是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化, 如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来 越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学 的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。 遗传算法程度流程图为:

【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理,熟悉遗传算法的运行机制,学会用遗传算法来求解问题。 【实验原理】 遗传算法( Genetic Algorithm )是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化, 如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来 越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学 的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。 遗传算法程度流程图为:

软件设计大作业

一需求分析 此系统是一个类似于淘宝网的在线衣服销售系统,相当于淘宝网上的一个专门买衣服的网店,它具有用户注册,用户登录,修改密码,显示系统功能,查看订购历史以及订货。 1.1需求列表: (1)用户管理:用户管理的需求包括用户注册,用户登录以及修改密码。 用户注册是添加一个我们网上衣店的新用户;用户登录是用户想要进 入系统时必须采取验证身份的步骤;修改密码是为了用户的安全性考 虑,当密码存在不安全的因素时,适时修改密码。 (2)商品衣服的管理:商品管理包括订购衣服和查看订购衣服的历史。订购衣服是当我们衣店的库存数量不足时必须采取的;查看订购衣服的 历史有助于我们更好地了解衣服的订购情况。 (3)显示系统功能:此功能是用来让用户能很清楚地了解此系统所实现的各种功能。 1.2系统用例图:

1.3用例分析及场景描述: 用户注册用例: 这部分主要是新用户进行注册的过程,首先用户进入到注册页面,填写注册信息并提交,如果无误的话系统会给予注册成功的提示,如果注册失败会提示注册失败信息。 用户登录用例: 此功能模块针对的对象是本网站的会员既已经注册的会员,会员首先填写用户名和密码,然后点击登录按钮,如果网站数据库中存在此会员并且密码正确则提示登录成功提示,如果网站不存在此用户或密码不正确,系统会提示用户登录失败。 修改密码用例: 此用例针对注册会员进行操作。用户登录成功会可以进入网站主页面,如果用户想修改密码的话可以单击修改密码按钮,进行密码修改,用户输入新密码单击修改按钮即可完成密码修改。

显示系统功能用例: 此功能针对注册会员,会员首先登录到网站,进入主页,主页会有相关操作的按钮,显示系统所提供给会员操作的功能,用户可以针对自己的需要选择系统提供的功能。 订货衣服用例: 此功能针对注册登录会员,网站提供两种订购方案:单件订购和定制套装。用户可以根据自己的需求来选择。 单件订购方案:用户选择是上衣还是裤子,并填写订购的数量,确认无误后单击订购按钮即可,如果订购成功,系统会提示订购成功,失败则会提示订购失败。 定制套装方案:用户选择定制套装的档次(高、中、低),并填写订购的数量,确认无误后单击订购按钮即可,如果订购成功,系统会提示订购成功,失败则会提示订购失败。 显示订购历史用例: 此功能针对注册会员,用户登录到系统后,主页显示系统功能中包括历史查看选项,用户可以单击进入历史交易记录页面,页面将显示用户所有的交易记录。 二设计模式 2.1单件模式 2.1.1单件模式的定义

《算法分析与设计》作业参考答案

《算法分析与设计》作业参考答案 作业一 一、名词解释: 1.递归算法:直接或间接地调用自身的算法称为递归算法。 2.程序:程序是算法用某种程序设计语言的具体实现。 二、简答题: 1.算法需要满足哪些性质?简述之。 答:算法是若干指令的有穷序列,满足性质: (1)输入:有零个或多个外部量作为算法的输入。(2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法的每条指令清晰、无歧义。 (4)有限性:算法中每条指令的执行次数有限,执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。 答:分析分治法能解决的问题主要具有如下特征: (1)该问题的规模缩小到一定的程度就可以容易地解决; (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; (3)利用该问题分解出的子问题的解可以合并为该问题的解; (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。 答:将递归算法转化为非递归算法的方法主要有: (1)采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强,但本质上还是递归, 只不过人工做了本来由编译器做的事情,优化效果不明显。(2)用递推来实现递归函数。 (3)通过Cooper 变换、反演变换能将一些递归转化为尾递归,从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善,但其适用范围有限。 三、算法编写及算法应用分析题: 1.冒泡排序算法的基本运算如下: for i ←1 to n-1 do for j ←1 to n-i do if a[j]

算法分析大作业动态规划方法解乘法表问题和汽车加油行驶问题#精选.

算法分析大作业 动态规划方法解 乘法表问题和汽车加油行驶问题目录 1.动态规划解乘法表问题 1.1问题描述------ 1.2算法设计思想------ 1.3设计方法------ 1.4源代码------ 1.5最终结果------ 2.动态规划解汽车加油行驶问题 2.1问题描述------ 2.2算法设计思想------ 2.3设计方法------ 2.4源代码------ 2.5最终结果------ 3.总结

1.动态规划解决乘法表问题 1.1问题描述 定义于字母表∑{a,b,c)上的乘法表如表所示: 依此乘法表,对任一定义于∑上的字符串,适当加括号表达式后得到一个表达式。 例如,对于字符串x=bbbba,它的一个加括号表达式为(b(bb))(ba)。依乘法表,该表达式的值为a。 试设计一个动态规划算法,对任一定义于∑上的字符串x=x1x2…xn,计算有多少种不同的加括号方式,使由x导出的加括号表达式的值为a。 1.2算法设计思想 设常量a,b,c 分别为 1, 2 ,3 。n 为字符串的长度。 设字符串的第 i 到第 j 位乘积为 a 的加括号法有result[i][j][a] 种, 字符串的第 i 到第 j 位乘积为 b 的加括号法有result[i][j][b] 种, 字符串的第 i 到第 j 位乘积为 c 的加括号法有 result[i][j][c] 种。 则原问题的解是:result[i][n][a] 。 设 k 为 i 到 j 中的某一个字符,则对于 k 从 i 到 j :result[i][j][a] += result[i][k][a] * result[k + 1][j][c] + result[i][k][b] * result[k + 1][j][c] + result[i][k][c] * result[k + 1][j][a]; result[i][j][b] += result[i][k][a] * result[k + 1][j][a] + result[i][k][a] * result[k + 1][j][b] + result[i][k][b] * result[k + 1][j][b]; result[i][j][c] += result[i][k][b] * result[k + 1][j][a] + result[i][k][c] * result[k + 1][j][b] + result[i][k][c] * result[k + 1][j][c];

人工智能遗传算法实验报告

WORD格式 人工智能实验报告 学号: 姓名: 实验名称:遗传算法 实验日期:2016.1.5

【实验名称】遗传算法 【实验目的】 掌握遗传算法的基本原理,熟悉遗传算法的运行机制,学会用遗传算法来求解问题。【实验原理】 遗传算法(GeneticAlgorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法是从代表问题可能潜在的解集的一个种群开始的,而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,我们往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度大小选择个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码,可以作为问题近似最优解。 遗传算法程度流程图为:

【 实】 :已知f(x)=x*sin(x)+1,x[0,2],求f(x)的最大值和最小值。 数据结构: structpoptype { doublegene[length];//染色体 doublerealnumber;//对应的实数x doublefitness;//适应度 doublerfitness;//相对适应度 doublecfitness;//累计适应度 }; structpoptypepopulation[popsize+1];//最后一位存放max/min structpoptypenewpopulation[popsize+1];// 染色体编码: x [ 因此 ,染色体由2 3位字节的二进制矢X 与二进)2之 间的映射如下: 22 i bb......bb2x '; 222102i i010 xx' 2 23 21 适应度函数: 由于要求f (x )的最值,所以适应 度函数即可为f (x )。但为了确保每个个体都有被选中的可能性,因此需要将所有适应为大于0的值。因此,设计 求最大值的适应度函数如下: eval max f(x)5xsinx6; 将最小化为求-f(x)的最大值,同理,设计最小值的适应度函数如下: evalfxxx min()5sin4; 种群大小: 本50,再进行种群初始化。 实验参数: 主要有迭代数,交叉概率,变异概率这三个参数。一般交叉概率在0.6-0.9范围内, 变异概率在0.01-0.1范主要代码如下: voidinitialize()//种群初始化 { srand(time(NULL));

算法分析与设计(线下作业二)

《算法分析与设计》 学习中心: 专业: 学号: 姓名:

作业练习二 一、名词解释 1、MST性质 2、子问题的重叠性质 递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次,这种性质称为子问题的重叠性质。 二、简答题 1、简述动态规划算法求解的基本要素。 答:动态规划算法求解的基本要素包括: 1)最优子结构是问题能用动态规划算法求解的前提; 2)动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果,即重叠子问题。 2、备忘录方法和动态规划算法相比有何异同简述之。 答:备忘录方法是动态规划算法的变形。与动态规划算法一样,备忘录方法用表格保存已解决的子问题的答案,在下次需要解此问题时,只要简单地查看该子问题的解答,而不必重新计算。备忘录方法与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的,而动态规划算法则是自底向上递归的。因此,备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同的子问题的重复求解,而直接递归方法没有此功能。

3、贪心算法求解的问题主要具有哪些性质简述之。 答:贪心算法求解的问题一般具有二个重要的性质: 一是贪心选择性质,这是贪心算法可行的第一个基本要素; 另一个是最优子结构性质,问题的最优子结构性质是该问题可用贪心算法求解的关键特征。 三、算法编写及算法应用分析题 1、设计求解如下最大子段和问题的动态规划算法。只需给出其递推计算公式即可。 最大子段和问题:给定由n 个整数(可能为负整数)组成的序列a1a2 … an,求该序列形如Σi≤k≤j ak的子段和的最大值。当所有整数均为负整数时定义其最大子段和为0。依次定义,所求的最优值为max{0, max1≤i≤j≤n Σi≤k≤j ak }。

算法分析大作业 寻找变位词

深圳大学研究生课程论文 题目大作业:变位词实验成绩 专业计算机与软件学院软件工程 课程名称、代码 年级2015 姓名文成 学号2150230509 时间2015 年12 月任课教师杨烜

一、大作业要求与内容 大作业内容: 在下列问题中挑选一个问题,选用适当的算法进行实现,在课堂上,针对该问题完成一个10分钟的论文演讲与演示,并提交演讲PPT。(30分) 在一个类似英语词典的大文件中找出变位词的所有集合,例如,tea和eat是变位词,同属一个集合,找出所有这种集合。 大作业要求:(70分) (1)要求演示算法解决问题的完整过程,如果我对解这个问题一无所知,看了你的解决过程,就要能理解算法是如何解决问题的; (2)要求交互界面活泼生动,演示速度可控; (3)尽可能提供丰富的功能让我理解你是如何解决这个问题的; (4)提交源程序、大作业报告(介绍详细的算法设计说明和使用说明); (5)以论文、报告等形式考核专用答题纸写大作业,大作业报告中要分析算法效率,并给出实测效率和理论效率图表; (6)大作业用5号字体,总页数不得少于8页,否则视为无效。 二、大作业步骤 Introduction: 给定一本英语单词词典,找出所有的变位词集。所谓的变位词是指,组成各个单词的字母完全相同,只是字母排列的顺序不同。例如,tea和eat是变位词,同属一个集合,找出所有这种集合。 Motivating idea: 1.如何判断两个单词是否为变位词。 思路一: 如果两个单词是变位词,那么它们具有相同的长度,且每个英语字母的个数是一样的。我们只需要挨个对各个单词进行比较即可。这个思路容易想,但时间效率太低,还可以继续改进一下,且看下面的思路二。 思路二: 将两个字符串按照字母表顺序排序,看排序后的字符串是否相等,如果相等则是兄弟字符串(变位词)。这种方法的时间效率根据你使用的排序算法不同而不同。这里我采取思路二,我使用的是快速排序。但是依旧有个问题,单词与单词一个一个比较的话效率还是太低了,我们可以再做改进。 2.如何从字典中找出所有变位词的集合。 思路一: 对于这个问题,最快想到的最直接的方法就是针对每一个单词跟字典中的其他单词进行比较。然而,假设一次比较至少花费1微秒的时间,则拥有二十万单词的字典将花费:200000

遗传算法与机器人路径规划

遗传算法与机器人路径规划 摘要:机器人的路径规划是机器人学的一个重要研究领域,是人工智能和机器人学的一个结合点。对于移动机器人而言,在其工作时要求按一定的规则,例如时间最优,在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下,机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法,利用地图中的信息进行路径规划,实际应用中效率比较高。 关键词:路径规划;移动机器人;避障;遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers(e.g time optimal),and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 (1)根据机器人对环境信息掌握的程度和障碍物的不同,移动机器人的路径规划基本上可分为以下几类: 1,已知环境下的对静态障碍物的路径规划; 2,未知环境下的对静态障碍物的路径规划; 3,已知环境下对动态障碍物的路径规划; 4,未知环境下的对动态障碍物的路径规划。 (2)也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型: 1,基于环境先验完全信息的全局路径规划; 2,基于传感器信息的局部路径规划。 (第二种中的环境是未知或部分未知的,即障碍物的尺寸、形状和位置等信息必须通过传感器获取。) 1.2路径规划步骤 无论机器人路径规划属于哪种类别,采用何种规划算法,基本上都要遵循以下步骤: 1, 建立环境模型,即将现实世界的问题进行抽象后建立相关的模型; 2, 路径搜索方法,即寻找合乎条件的路径的算法。 1.3路径规划方法

遗传算法作业

遗传、蚁群算法作业 1、利用遗传算法求出下面函数的极小值:z=2-exp[-(x2+y2)], x,y∈[-5,+5] 解: 第一步确定决策变量及其约束条件:x,y∈[-5,+5] 第二步建立优化模型:min z(x,y)=2-exp[-(x2+y2)] 第三步确定编码方法。用长度为50位的二进制编码串来表示决策变量x,y。第四步确定解码方法。解码时将50位长的二进制编码前25位转换为对应的十进制整数代码,记为x,后25位转换后记为y。 第五步确定个体评价方法。 第六步设计遗传算子。选择运算用比例选择算子,交叉运算使用单点交叉算子,变异运算使用基本位变异算子。 第七步确定遗传算法的运行参数。 实现代码: % n ---- 种群规模 % ger ---- 迭代次数 % pc ---- 交叉概率 % pm ---- 变异概率 % v ---- 初始种群(规模为n) % f ---- 目标函数值 % fit ---- 适应度向量 % vx ---- 最优适应度值向量 % vmfit ---- 平均适应度值向量 clear all; close all; clc; tic; n=30; ger=200; pc=0.65; pm=0.05; % 生成初始种群 v=init_population(n,50); [N,L]=size(v); disp(sprintf('Number of generations:%d',ger)); disp(sprintf('Population size:%d',N)); disp(sprintf('Crossover probability:%.3f',pc)); disp(sprintf('Mutation probability:%.3f',pm));

相关主题
相关文档 最新文档