大连海事大学《现代优化技术》第4讲：算法及其设计与评价PPT课件.ppt

现代优化技术
第4讲:算法设计与算法评价
主要内容
算法
算法特征
算法分类
算法设计
算法分析与评价
近似算法的应用
算法实践之一:求解最短路问题的
Dijkstra Algorithm
算法的概念
算法(Algorithm)是一组明确的、可以执行步骤的有序集合。
一个有穷的规则序列;解决某一问题的一系列运算;程序设计的第一步。
一系列解决问题的清晰指令,即能够对符合一定规范的输入,在有限时间内获得所要求的输出
分析问题
算法设计
程序设计
解决方案
算法的特征
算法反映了求解问题的方法和步骤,不同的问题需要用不同的算法来解决,同一个问题也可能有多种不同的算法。一个算法必须具有以下特性:
1. 有穷性(可终止性)
一个算法必须在有限的操作步骤内以及合理的时间内执行完成。
2. 确定性
算法中的每一个操作步骤都必须有明确的含义,不允许存在二义性。
算法的特征
3. 有效性(可行性)
算法中每一个步骤必须能够实现,如在算法中不允许出现分母为0的情况。
算法执行的结果要能够达到预期的目的,实现预定的功能。
4. 输入数据与输出数据的要求
一个算法应该有0个或多个输入数据、有1个或多个输出数据。
算法的特征示例
配送
中心
配送问题的扫描算法
算法设计
算法是要通过程序才能加以实现的。常用的算法描述方式:
1. 自然语言
自然语言就是人们日常使用的语言,可以是中文、英文等。
例如,求3个数中最大者的问题,可以描述为:
①比较前两个数。
②将①中较大的数与第三个数进行比较。
③步骤②中较大的数即为所求。
算法的描述工具
算法设计
2. 流程图
流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。
(1) 顺序结构。程序执行完A语句后接着执行B语句,如图所示。

(2) 选择结构。当条件P成立时,则执行A语句,否则执行B语句,如图所示。
P
成立
A
B
不成立
算法的描述工具