最佳路径算法

最佳路径算法（精选7篇）

最佳路径算法 篇1

0 引言

在虚拟现实技术和网络技术飞速发展下, 三维地理信息系统在城市规划和房产应用等领域的应用优势明显, 其中最佳路径分析功能更显得尤为重要。

Skyline是目前国际上应用最广泛、技术最领先的三维GIS平台, 在海量数据方面功能尤其强大。由于数据计算量大, Skyline的最佳路径分析时间较长并且对硬件要求较高。本文旨在从算法上改进Skyline的最佳路径分析功能, 使该软件日臻完美。

1 基本原理

1.1 最佳路径

Skyline中的最佳路径, 是指在地形坡度基础上两点之间的最短空间距离。

1.2 遗传算法

遗传算法是一种基于自然遗传和进化而形成的自适应全局优化搜索算法, 具有鲁棒性强、并行性强、应用性强等显著特点。

遗传算法的操作算法主要有:

1) 选择算子

把优化的个体直接遗传到下一代或者通过交叉产生新的个体再遗传到下一代。判断个体优良与否的标准就是各自的适应值。这符合达尔文适者生存的原则。

2) 交叉算子

把2个父代个体的部分优秀结构进行重组而生成新个体的操作。交叉能使遗传算法的搜索能力飞跃提高, 是算法中的核心。

3) 变异算子

对群体中的个体串的某些基因值进行改动, 变异概率不能大于0.5, 否则退化为随机搜索。变异提高了局部搜索能力, 也保持了种群多样性。

2 算法设计

本文使用遗传算法进行最佳路径分析, 首先对分析空间进行栅格化, 其次用栅格排列初始化种群, 最后用遗传算子进行操作, 最终得到最佳路径。

2.1 空间栅格化

将不可通过区域用凸多边形描述, 根据坡度的梯度单调性变化和不可通过区域进行栅格划分, 其中包含不可通过区域的栅格为障碍栅格, 反之则为自由栅格。本文只对自由栅格进行编号, 如图1所示。

2.2 初始化种群

2.2.1 个体编码方法

由起始位置A到终点位置B的路径就表示一个个体, 以图1中红色路径为例为例, 则该个体用栅格序号法表示为:

每次最佳路径分析的区域不同, 选择可变长度的染色体进行编码。

2.2.2 初始种群的产生

本文选取一系列随机产生并且不一定连续的栅格连接A和B。这样既可以降低初始种群的困难。根据初始种群产生原则, 如图1所示, 以下路径都可以作为初始种群的个体编码示例:

2.2.3 适应度函数设计

最佳路径分析是以基于坡度的空间最短距离作为个体适应度函数:

式中, n为该个体的栅格总和, 表示第i个栅格直线距离, 表示第i个i栅格的坡度。i

2.3 遗传算子设计

1) 选择算子。本文个体选择概率基于排序的适应度分配, 采用轮盘赌选择法。

2) 交叉算子。本文选择重合点交叉, 随机选取两个个体, 栅格序号相同点进行交叉。

这种交叉方式不会产生间断路径。

3) 变异算子。本文采用单点变异操作, 这样既能降低了计算量, 又保证最佳路径的求解。

3 结果测试与分析

为了验证算法合理性, 本文以某区域的FLY为例 (Skyline软件特有的三维影像文件) 。区域包括1 765个坡度区域、1 204个路段和132个三维模型。

测试参数中, 种群大小为50, 遗传代数为100, 变异概率为0.002。

经测试基于遗传算法的的最佳路径更加优化, 而且在相同的硬件条件下分析时间比单纯使用Skyline软件少2~3s。如图2, 为基于遗传算法的Skyline最佳路径分析测试图, 其中红色矩形区域为起始位置, 黑色路径为最优路径。

摘要：本文介绍了遗传算法的操作和特点并使用遗传算法对skyline最佳路径分析进行改进, 并通过实验测试证明算法的可行性和合理性。

关键词：遗传算法,最佳路径

参考文献

[1]王小平, 曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社, 2002.

[2]马艳丽, 裴玉龙.基于混沌神经网络的驾驶员动态路径诱导算法研究[J].交通运输系统工程与信息, 2007, 7 (1) :57-60.

最佳路径算法 篇2

关键词：遗传算法,最短距离,最优解

遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的J.Holland教授在1975年首先提出, 采用概率化的寻优方法, 得到最优解。具体算法如下:首先确定种群的规模, 然后进行编码, 选取目标函数, 进行交叉变异操作, 从而得到最优解。

1 工程实例

有一测量船, 要求从A (30, 44) 出发, 经历表1的所列各位置进行测量, 最后回到A点, 如何选择行驶路线以达到行驶距离最近。

1.1 染色体编码

编码方法在很大程度上决定遗传进化的效率。在求解复杂问题上, 二进制编码搜索空间会加大, 进化性能较差。本项目采用十进制编码, 用随机数列作为染色体, 其中 (1=2, 3…101) , 第一个目标和最后目标为0, 1。编码位置i代表目标, 位置i的随机数代表目标i在航行中的顺序。

1.2 种群初始化

初始种群规模M=5 0, 对于随机产生的初始值, 交换u和v的位置, 新路径为:。

1.3 目标函数

目标函数即航行的路线长度, 为此:

1.4 交叉

交叉采用单点交叉, 交叉率, 对于两个父代个体随机选取交叉点交叉, 以得到子代个体。

1.5 变异

变异是实现多样性的一种手段, 是全局寻优的保证, 这里令变异率。

利用遗传算法最近的航行路线为:

2 结语

遗传算法具有良好的全局搜索能力, 可以快速地将解空间中的全体解搜索出, 而不会陷入局部最优解, 利用它的内在并行性, 可以方便地进行分布式计算, 加快求解速度。

参考文献

[1]边霞, 米良.遗传算法理论及其应用研究进展[J].计算机应用研究, 2010 (7) .

[2]邓亮, 赵进, 王新.基于遗传算法的网络编码优化[J].软件学报, 2009 (8) .

[3]段玉倩, 贺家李.遗传算法及其改进[J].电力系统及其自动化学报, 1998 (1) .

最佳路径算法 篇3

关键词：GIS,配电网,最佳抢修路径分析

1 数学模型

虽然配电网故障的地点随机的，但由于城市配电网的线路一般沿道路架设，从城市道路的网络拓扑结构分析。因此配电网最佳抢修路径问题转化为城市交通最短路径问题。

定义：设G=(V, E)为一有向图，V为节点集，E为边集;Xij为边(i, j)是否存在逻辑指示因子;Wij为存在边(i, j)的权值。对i∈V, k∈V, P (i, k)为点i到点k的一条路径。给定一节点r为根，r∈V，单源最短路径即为找到一棵有向树T，使得，i V，且(r, i)，即在T中从r到i的唯一路径是G中从r到i若出行车所要经过的区域内的各交叉路口组成V，区域内所有路段组成E。车辆从i交叉路口行使到j交叉路口的时间，即权值Wij，由车辆在路段i→j行使时间和交叉路口的延误时间以及交通管制的措施的影响来决定。

2 局部Dijkstra算法

在Dijkstra算法中，网络被抽象为图论中定义的有向图或无向图，用图的遍历方法搜索最短路径。其中包括邻接结点Dijkstra算法和局部Dijks tra算法(局部最短路径搜索Dijks tra算法)。邻接结点Dijks tra算法所有结点首先初始化为未标记结点，在搜索过程中凡与最短路径中的结点相连通的结点为临时标记结点，每次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，效率低。为了能够提高Dijkstra算法的最短路径搜索效率，局部Dijkstra采用尽量减少最短路径分析过程中搜索的结点数量，从而尽快到达目标结点，对邻接结点的Dijkstra算法进行了优化。

定义：在一个赋权的简单连通无向图G=(V, E, W) (V：顶点集;E：边集;W：权重)中，某一源结点s到某结点t的最短路径所必须经过的结点集合Vst必定是V的子集，即Vst∈V。

假设在网络中任意给定两点s和t，显然，如果网络中存在一条边连接s与t, p (s, t):

首先，要沿由s至t的直线段方向寻找s与t之间的最短路径，即Vs t分布于s、t及其附近;

其次，参与计算的弧段为直线段。

据此，在配电网地图中的局部最短路径搜索算法可以描述为：

输入：选择的起止结点s和t，坐标分别为(Xs, Ys，)和(Xt, Yt)。

输出：s和t之间的最短路径及其长度。

步骤如下：

步骤1：获取起始点与目标点s和t。

步骤2：计算直线段s-t的长度，记为L。

步骤3：如果s与t之间存在一条弧段或弧段链，则为最短路径。否则转4。

步骤4：以s-t直线段为中线建立宽为10个基本单位的局部搜索矩形。

步骤5：搜索矩形范围内的所有弧段，获取弧段在矩形范围内的所有结点，并按顺序编号。并以新的结点为依据建立临时弧段数据。

步骤6：从s所在弧段开始，依次寻找与其它各弧段的交点。如果最终出现目标结点所在的弧段，转7;否则转8。

步骤7：利用Vst建立邻接矩阵和关联矩阵及权值矩阵。并使用Dijs tra算法进行最短路径标记并输出，算法结束。

步骤8：以原矩形为基础，向四周扩展10个基本单位，形成新的局部搜索矩形。转5。

如(图1)所示，如果求结点V1至V3的最短路径，根据局部最短路矩搜索算法，则可以先搜索路径必须经过的顶点集合Vst，在Vst中进行最短路径的标记。

用局部最短路径搜索，所形成的节点邻接矩阵如下：

该算法是从局部开始计算并向外逐惭扩散，因此称为局部最短路径搜索Dijkstra算法，算法可以很大程度上减少在最短路径搜索过程中搜索的结点数，从而达到优化算法的目的。算法的运行的效率决定于网络图的复杂程度和各弧段之间的连通程度。连通程度越好复杂度越高，局部最短路径搜索算法的运行效率较高

3 结束语

本文根据电力配电网的结构特点，分析配电网故障数学模型，分析研究了局部Dijkstra算法在电力配电网中抢修故障的最短路径应用。较好地解决网络分析中空问数据拓扑问题，同时也在很大程度上减少了Dijks tra算法在搜索过程中搜索的结点数，极大地提高了算法的执行效率。

参考文献

[1]Caixin Sun, Lifeng Liu et al.2002.Study on Mathermatical Model of Urban Distribution System Optimal Rushmaintain Path.Proceeding of the International Conference on Power System Technology (PowerCon2002) , Kunming, China.

[2]孙才新, 刘理峰.电力地理信息系统及其在配电网中的应用.北京:科学出版社, 2003.

集体备课最佳路径的探索 篇4

关键词：色集体备课模式,试行完善,应用,效果

在教学过程中备课是非常重要的环节, 质量的高低直接影响教学效果和目标。我校是4规制教学, 特色集体备课模式的形成, 有着三年的尝试完善过程。

一、改革前教学设计存在的问题

以往备课都是每人独立写一份教学设计, 学校每学期检查两次, 即完成了任务。在教学管理的过程中, 我们发现大多数教师备课、上课两张皮, 究其原因是有的教师买教案参考或在网上下载, 为了应付检查, 一抄了事。也有的是抄别人或抄自己以前备的课, 根本不根据本班学生实际情况动脑筋构思方法步骤。也有的教师在课堂上讲解一个知识点, 或解决一个问题时, 用了很巧妙的方法, 但在其教学设计中没有任何记载, 这就是以往独立备课方式存在的问题。教学设计成了应付检查的工具, 写教学设计等同于做无用功。

二、教学设计改革过程中走的弯路

发现问题就要解决问题。为了让教师们摆脱做无用功, 我们曾提倡过提纲式教学设计, 一改以往教学设计中“重过程、重细节”为“重方法、重反思”。教学设计可以不拘一格, 但要有课前准备, 有突出重点、突破难点的方法, 有板书设计及课后反思。经过一学年的试行, 老师们都反映, 这样的教学设计节省了大量时间, 少做了无用功。但是诸多的弊端暴露无疑, 由于教学设计过于简单, 一些教师又缺少思考过程, 大部分青年教师把握不好重点、难点以至于上课心中没底, 并且不会说课。绝大部分老教师整个过程简化到短短几条, 课后反思应付了事。

于是我们又在一个年级试行集体备课的方式, 方法是“组长牵头———集体研讨———试讲———集体修改———形成样本———个人反思”。经过一学期的试行, 效果不理想, 有些课的设计纯属网上资料的拼凑, 有些课的教学设计干脆是组长一人代劳。原因是按照此流程每个环节都认真对待耗费时间太长。每位教师一个学期课时数一百余节, 如果节节课如此, 老师们将所有时间都搭上, 只进行集体备课这一项工作, 其他工作都做不好, 老师们干脆将步骤简化或者不做到位。再次试行又宣告失败。

三、特色集体备课模式的形成

失败乃成功之母, 最佳的方法是经过不断完善形成的。我们认真分析失败的原因, 总结经验吸取教训, 多次召开研讨会, 学习外地先进的改革经验, 集思广益并结合本校实际情况形成了特色教学设计的基本思路。即“集体备课———分头执笔———个人微调———课后反思”, 并率先在语文、数学这两个学科实行。

1. 集体备课。

每学期开学前用一周的时间, 由组长牵头, 同学科组共同学习“课程标准”, 共同通读教材, 确定每个单元的重点、难点, 商讨每个单元重点课的可行教学方法。探讨教材中哪些知识是可以让学生自己学习掌握的, 哪些是需要教师讲解的, 教师该放到什么位置, 预想学生会出现什么问题。教师采取什么方法、什么形式帮助学生解决问题以及教具的准备等。

2. 分头执笔。

经过集体备课达到资源共享的同时, 分头执笔可以节省很多时间, 减轻教师的劳动。执笔教师有更充裕的时间和精力使教学设计细化, 更便于其它教师使用。

3. 个人微调。

在每页教学设计右侧都留有5厘米的空白区域, 供执教者再根据本班学生实际情况和个人风格进行调整, 使教者融入课堂教学的“有我之境”, 才能真正在课堂上挥洒自如, 游刃有余。

4. 教学反思。

“学而不思则罔, 思而不学则殆。”我们建议教师从以下几个方面进行教学反思。 (1) 写成功之处。即将教学过程中达到预先设计教学目的地方;教学方法上的改革与创新;教材的创造性使用;教学过程中偶发事件产生的灵感等等。 (2) 写不足之处。对课堂教学中的疏漏之处进行回顾、梳理、探究、剖析, 可成为今后教学上的教训, 使自己, 也使别人少走弯路。 (3) 写学生的奇思妙想。在课堂教学过程中, 学生是学习的主体, 学生经常会有些奇思妙想, 教师先肯定学生提出的独特见解。这样不仅是对学生的赞赏和鼓励, 也充分彰显了学生的个性。同时, 这些难能可贵的见解, 也是对课堂教学的补充与完善, 可以拓宽教师的教学思路, 教师及时记录下来, 日积月累, 将是今后教学的丰富资料。

四、特色集体备课的效果

经过一学年的试行, 特色集体备课的形式受到老师们的欢迎。老师们普遍反映, 特色集体备课形式:1.可以节约教师的时间, 能使教师从以往繁重的备课中解脱出来, 有更充足的时间、更充沛的精力进行其他工作, 教师的休息时间也能得以保障;2.能促进青年教师尽快成长, 青年教师能在高起点上发展;3.能互相促进, 取长补短, 使教师队伍教学能力整体提高。

特色集体备课更需要个人的智慧, 任何磨灭个性的集体备课, 只能使集体备课走向形式化。为保证特色集体备课形式长期有效地发挥作用, 我们还要结合学校实际情况不断进行完善, 进一步丰富集体备课的内涵, 保持其鲜活旺盛的生命力。

参考文献

[1]给教师的建议.[苏]B·A·苏霍姆林斯基.教育科学出版社出版

一种公交最佳路径选择方法 篇5

公交系统是城市基础设施的一个重要组成部分。随着我国可持续发展战略的提出,合理规划、充分利用城市公交系统是缓解我国目前许多城市交通问题的重要途径,也是充分利用不可再生能源保护环境的一种重要手段。

目前我国的许多城市尤其是大城市都拥有城市电子地图。城市电子地图中的公交模块提供的交通查询服务功能为人们的出行提供了巨大的方便。通过该模块,用户可以方便地获得出行路线和换乘方案的信息。例如,当用户输入起始点和目标点之后,系统便可以给用户提供最优的公交出行方案。

1 公共交通网络模型

一个公共交通网络是由一组公交线路及公交上下车站组成。每一条公交线路贯穿一组不同的上下车站点,且各条公交线路可以有相重合的上下车站点。在数学上,公交网络其实质是一个无向连通图[1]。表示为G(V,A)。其中V为公交网络中所有上下车站点的集合,A为公交路段的集合(即相邻两个上下车站点之间的线路)。

图1为一个简易公交网络示意图。其中有三条公交线路L1L2L3,它们经过的公交站点分别如表1所示。

表2为对应于该公交网络中各上下车站上所经过的公交路线,其中各边所对应的数字为其权。公交网络模型采用“结点—弧段—线”的数据结构表示[2]。该结构由图2[2]表示,其中公交线路表中节点顺序按照公交线路中原始线路排列。

在实际当中,虽然会有公交路口将两个相邻站点间的弧段分割,但这种分割并不影响对公交换乘问题的分析。因而无须在公交网络图中明确标出,只需表示出一条连接两相邻站点的弧段就可以。

2 公交换乘的算法

2.1 Dijkstra算法[4]

在求最短路径的各种算法中,目前公认的效率最高的算法是1959年由荷兰计算机专家E.W.Dijkstra提出的标号算法,该算法一般称为Dijkstra算法。该算法不仅可以求得从v点到w点之间的最短距离而且可以求从v点到图中任意点之间的最短距离。在Dijkstra算法中将图G中顶点分为P和T两部分,P为永久节点集,对P中的节点进行P标号l(v),表示从v1到v的最短路径,T=V-P为临时节点集。对T中节点进行T标号l(v),表示v1到v的一条路上的权。

其算法过程为:

(1)令P={v1},对v1进行P标号,且l(v1)=0,其余节点T=V-P进行T标号,l(vj)=w1j,j=2,3,…,n,w1j为v1导vj的边上的权。

(2)在T标号的节点中选择最小标号节点vj进入P。

(3)对(2)中选择的节点vj根据下私进行修改:min{l(vj),l(vi)+wij}。

(4)重复上述步骤,直到到达目标点。

2.2 公交网络抽象图

对于公交问题而言,其实质就是提供给乘客一种从出发点到目的点的最佳解决方案。通过对乘客出行的心理调查得知,在乘客出行时其最关心的问题是出行路线的便利性,即只需最小换乘次数便可到达目的地。其次才是时间最少,距离最短[3]。而时间又与步行时间、等车时间、换乘次数、路线距离密切相关。因而本文所述公交换乘算法是基于最少换乘基础上的最短距离算法。

对于公交网络中任意一条公交线路上的任意两个上下车站点而言,其都是可以直接到达不需换乘。从而可以得到公交网络的直达矩阵T[4]。在该矩阵中,两站点间如果至少有一条公交线路经过则Tij=1,否则Tij=0。在公交网络的直达矩阵中,其行列顺序均为从A到B的字母顺序依次进行排列。矩阵表示如下所示:

根据该直达矩阵,整个公交网络便可以抽象表示成一个连通图(如图3所示)。

在该图中,各个结点对应于公交网络中各上下车站点。对于图中任意两点间若有一条公交路线通过两点间便用一个弧段相连。

为便于分析,对图3作如下规定:

(1)对于公交网络中不管两站点间有几条公交线路经过,图中只用一条弧段进行表达。

(2)各个弧段所对应的权均为1。

对于该图可以称之为“公交网络站点邻接图”,它是公交网络图的抽象。

2.3 基于邻接图的最少换乘次数

利用Dijkstra算法,在图3中任给两点求出其最短路径。若两点间只有一条边相连,则说明两点间至少有一条公交线路经过,这两点可直达换乘次数N=0;若两点间需经n条弧段才能到达,则说明需要换乘,其换乘次数N=n-1,n为连接两站点间最少经过的弧段数,且换乘点为中间经过的点。

2.4 算法思想

对公交换乘问题的解决思想分为如下几步:

(1)通过抽象公交路线图利用Dijstra算法求解在抽象公交网络图中起始站点与目标站点间的最短路径。

(2)获得所求最短路径中各个换乘站点,并将其按顺序排列。

(3)获得(2)中所得到各相邻站点间所有公交线路。

(4)通过组合,依次连接各段公交线路,得到多条公交线路结果。

(5)计算求得各线路的路径长度即各段路径权的和,选出最短的线路即为所求结果。

3 算例

根据图1所示交通网络,求从A点至F点的最佳路径(如图4所示)。

第一步:通过对该公交网络的抽象图3,用Dijistra算法求得图3的最短路径,也即求得图1的最少换乘路径。计算步骤如下:

(1)根据图3可知A点与F点不相邻,因而不存在一条公交路线从A点直接到达F点,必须进行换乘。

(2)将A标号为P标号点。与A相邻的点有B,C,E。A点到这三点的权值 均为1,选取这三点为待定点,将其标记为T标号点。

(3)求B,C,E点的相邻点。B点的相邻点为C,C点相邻点为D和F,E点无下一相邻点。B,C点到达其邻接点的权值均为1。

(4)由于F即为所查找目的点,查找结束。将C点标记为P标号点。

A点到F点的路径为A→C→F。路径长度为L=AC+CF=2,换乘次数为n=路径长-1=2-1=1。换乘点为C点。

第二步:根据公交线路表求得最佳路径。其步骤如下:

(1)求经过公交路段两端点的所有公交线路;

对于第一步所得各公交站点依顺序排列:A,C,F,则相邻两站点间为一公交路段。求经过相邻两站点间的所有公交线路。

由表1得,经过A点且经过C点的公交线路有L1和L2。

(2)由①所得各公交线路,根据公交线路表求得各线路长度。

对L1线路而言,由表1可知在L1线路上A站点和C站点是相邻的两站点,根据表4得AC=2。对L2线路而言,由表1可知在L2线路上从A站点至C站点经过B站点,在L2线路上A站点至C站点的路线为:A-B-C。根据表4得,AB=1,BC=2,因而L2线路上AC=AB+BC=1+2=3。

(3)重复(1),(2)步骤,求得各公交路段的实际路径长度,直至目标点。

从C站点到F点只有L3线路,线路长度为CF=3。

(4)将各段线路组合得出各个线路换乘方案,对所得各方案中各段线路相加,比较,得最佳结果。方案1:A→F=L1+L2=AC+CF=2+3=5

方案2:A→F=L2+L3=AB+BC+CF=3+3=6

比较后可知最佳路径为方案1,从A点乘L1至C点换乘L3即可到达F点。

4 结束语

设计合理的公交网络和公交最佳路径选择方法给人们的出行带来极大的便利。而公交换乘是公交网络敏感而又不可避免的问题。距离最短往往并不意味着线路是最优的。本文通过对公交网络进行抽象生成新的抽象公交网络图,并根据Dijkstra算法首先确定出最少换乘次数及换乘点。再通过第一步所得结果根据公交线路表最终得到综合考虑换乘次数和路径长度的最佳公交换乘线路。

参考文献

[1]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1997:156-169.

[2]苏爱华,施法中.公交网络换乘问题的一种实现[J].工程图学学报,2005.

[3]邓辉文.离散数学[M].北京:清华大学出版社,2006:217-218.

[4]王莉,李文权.公交系统最佳路径算法[J].东南大学学报:自然科学版,2004.

最佳路径算法 篇6

图像分割(Image Segmentation)是把图像分成各具特性的区域并提取出感兴趣目标的技术和过程,是图像处理的一个重要领域,被广泛应用于计算机视觉领域。从上个世纪七十年代起图像分割问题就一直受到人们的高度重视,并已经进行了广泛而深入的研究,特别是根据阈值的灰度图像分割,随着神经网络、遗传算法、蚁群算法、模式识别、模糊逻辑等理论的不断发展,这些理论也逐渐被引入到图像分割领域,产生了许多新的图像分割方法。阈值法是一种最简单最基本的图像分割方法。阈值法可与其他分割方法结合使用,以得到更好的分割结果。确定最佳阈值是阈值分割法的关键,利用遗传算法的特点来快速准确地确定灰度图像直方图熵的最佳分割阈值,实现图像分割。

2 图像分割算法

图像分割中如何求解最佳的阈值,寻找出最优分割参量,以保证有效的分割效果是研究的目标。为了使设计出的算法更有效地搜索到全局最优解,寻找出最佳阈值,利用遗传算法的特点来快速准确地确定灰度图像直方图熵的最佳分割阈值,实现图像分割。

基于遗传算法的直方图熵的图像分割算法的具体的实现步骤:

第一步:利用直方图熵方法处理图像。最大熵方法处理图像本质上就是将图像的各像素均匀地分布在各个灰度级上,使对比度差的原始图像得到改善。选取的灰度图利用直方图熵方法进行处理,得到一维数组,a[i],i=0,1,2,……,元素个数为256。

第二步:染色体编码。由于图像灰度值在0~255,正好对应一个8位二进制即一个字节,因此本算法也采用二进制编码方案,将各个染色体编码为8位二进制。每个染色体代表了一个分割阈值。并将它们按二进制形式进行编码,初始群体的每个个体都是随机产生的,其相应的适应度值也有高有低。

第三步:利用适应度函数。通过测量图像灰直方图的熵,找出最佳阈值。

图像总熵H(t)为目标熵H0(t)和背景熵HB(t)之和:

可见,当H(t)最大时将达到最好的分类效果。于是最佳阈值为:

上式中Argmax是求使函数H(t)最大的那个值t,即所求得的最佳分割阈值。因此采用公式(1)作为适度函数,满足最大熵即最高适应度值的个体为所求的最佳阈值。利用公式(1)计算初始群体中每个个体的适应度。

第四步:依据遗传策略,选用遗传算子,产生下一代群体。

第五步:直到找到最大值,否则继续执行第三步。

第六步:用找到的最佳阈值分割图像。

3 仿真实验

在Matlab 6.5操作平台,选取源图米粒图片(图1)进行仿真实验,分别用算法和传统的Otsu算法对源图进行分割,实验结果如表1以及图2和图3所示。对比两幅图像的分割结果可以看出,图2较图3轮廓清晰,分割效果相当好。

4 结语

结合遗传算法和灰度图像直方图熵法的特点,通过直方图最大熵法提高灰度图像质量,结合遗传算法的优化特性,提出一种新的寻找最佳阈值分割图像的方法。与传统分割算法相比分割时间短,分割效果明显。

摘要：图像分割是图像处理的一个重要领域。阈值法是一种最简单、最基本的图像分割方法。确定最佳阈值是阈值分割法的关键,利用遗传算法的特点来快速准确地确定灰度图像直方图熵的最佳分割阈值,实现图像分割。通过仿真试验验证,分割效果明显,该算法具有很好的应用前景。

关键词：遗传算法,直方图熵,图像分割

参考文献

[1]江兴方,陶纯堪,是度芳.用最大熵法改善图像质量[J].江苏工业学院学报,2005.

[2]孙艳歌,邵罕.基于改进遗传算法的最优阈值图像分割算法[J].信息系统工程,2010.

[3]龚声蓉,刘纯平,王强.数字图像处理与分析[M].北京:清华出版社,2006.

[4]冈萨雷斯.数字图像处理(MATLAB版)[M].北京:电子工业出版社,2007.

探寻小小说教学的最佳路径 篇7

一、拟标题, 理文脉, 抓人物———知道写了什么

在揭示课题《半截蜡烛》后, 我问孩子们:“知道这是什么体裁的文章吗?”有学生回答:“小说。”“你在课外读过哪些小说?”生纷纷讲述。“是的, 我们在课内外也读了不少的小说, 你觉得小说最吸引你的是什么?”有学生说是跌宕起伏的情节, 有学生说是丰富多彩的人物, 也有的说是精彩的环境与细节描写等。我予以肯定:“的确, 小说往往具有一波三折的情节, 塑造的人物也具有鲜明的特点, 那么通过预习, 你知道《半截蜡烛》中塑造了哪几个主要人物呢?”我根据学生的回答, 板书了“伯诺德夫人、杰克、杰奎琳”。

“根据这些人物变化, 你能概括出情节是怎样发展的吗?”我以第二小节为例子, 示范概括出小标题“半截蜡烛, 巧藏情报”, 接着请学生认真阅读并自行概括, 我随机点拨并形成板书:

伯诺德夫人吹熄蜡烛暂缓危机

杰克借烛搬柴遭到喝止

杰奎琳端走烛台保住情报

我请学生根据板书画出变化图示 (如下图) , 再根据图示简要说说课文情节, 谈谈这样设计的好处, 学生明显感受到作者在构思情节时的精心了。

理清文脉后, 我就抛出一个问题引导学生自读自悟:“在这样危险的情况下, 伯诺德夫人一家分别有什么样的表现呢?你从中感受到他们有着怎样的品质?”这种相对开放的教学提问可以让学生有自己独特的体验和感悟, 虽然我们在课堂上经常看到“画出你最有感受的地方谈谈你的收获”此类的教学环节, 这种要求看似更为尊重学生个性化感悟, 其实容易造成学习活动漫无目的, 尤其不利于学困生的发展。作为课堂的主导, 我们应该为孩子的深入感悟设置拐杖, 帮助他们少走弯路。学生沿着我提供的思路展开学习, 有一定的针对性, 提高了学习的效率, 同时也遵循了“小说塑造了怎样的人物”这一文体特征。鲜明的人物形象是小说的核心所在, 所以要紧紧扣住人物形象来展开教学。

二、创情境, 探内心, 品描写———体会怎样写的

本文在写作上的最大特点是安排了极强的戏剧冲突。文中人物的动作、神情、语言及心理活动的描写细腻, 人物极富个性。因此, 教学时教师应该抓住文本的这个特点, 让学生充分研读课文中描写人物的动作、神情、语言及心理活动的句子, 进一步训练学生从人物外表揣摩人物内心的能力。探内心, 如入其心。如果能够透过人物的语言、动作去感受内心, 更有利于激发孩子共鸣, 引导他们走近人物。于是便有了如下一幕的教学:

孩子们, 本文还有一个亮点就是注重人物心理描写。文中伯诺德夫人一家每一个人的内心都是丰富的, 各有各的想法, 你能任意选择一个场景, 配合紧张的背景音乐渲染, 想象人物的内心世界并写下来吗?

呈现情境, 供学生自选———

一个中尉顺手拿过藏有情报的蜡烛点燃……

伯诺德夫人似乎感到德军那几双恶狼般的眼睛正盯在越来越短的蜡烛上……

大儿子杰克慢慢地站起来

……

他从容地搬回一捆木柴, 生了火, 默默地坐着等待……

小女儿杰奎琳镇定地把烛台端起来, 上楼去了……

正当杰奎琳踏上最后一级楼梯时, 蜡烛熄灭了……

……

学生从想象中体会到的担心、着急、对敌人充满的无限的仇恨, 这与人物外在的机智、镇静形成了强烈的对比。这样一来, 学生深入了文本人物的灵魂深处, 文中人物的爱国之情在学生心中显得更加真实可感。学生不仅对文中人物的动作、神情、语言及心理活动的句子进行了高质量的品读, 还得到了练习心理描写的机会。

学生阅读小说, 一般关注的是一波三折的故事情节, 而对环境描写则往往忽略, 在教学中要引导学生关注环境描写, 体会环境描写对刻画人物形象和烘托主题的作用。我启发学生道:“默读课文的第三到七小节, 你在读到哪些句子的时候感觉自己的心像被一只有力的大手一下子揪住了?请你在下面画上颤抖的线, 然后在旁边的空白处写上你的感受。”学生们的交流非常精彩, 关注到了我课前预设的所有内容, 比如:烛焰摇曳, 发出微弱的光, 此时此刻, 它仿佛成了屋子里最可怕的东西。有学生说:“此时此刻, 这已经不是普通的蜡烛, 而是随时会爆炸的定时炸弹, 这句话传达出令人窒息的紧张氛围。”有一位学生画出的句子是我都没有发现的, “一个中尉顺手拿过……”孩子说:“中尉一个顺手的动作, 却揪住了我的心。我想也揪住了伯诺德夫人一家的心, 因为中尉是不知情, 可我们都明白这个貌似顺手的动作意味着什么, 所以这也是作者表达的高明之处。”我不由得为学生的见解叫好, 他让我感受到课文中一些看似消极的语言, 你若能抓住, 它往往能传达积极的意义。

三、议战争, 谈背景, 深拓展———关注为什么要写

小说作为一种文学体裁, 它有自己独特的写作特点, 其一就是“视角独特, 以小见大”。小说往往选择一个很小的视角去细致刻画、描绘, 但作者通过这个小小的视角反映的却是广阔的社会生活现象。

在预习时我就布置学生通过网络等媒介了解故事发生的背景, 第二次世界大战给德国、法国和世界人民都带来深重灾难, 是德、法两国人民都不希望发生的。可战争这架机器迫使很多人陷入了流血、逃亡和死亡的泥沼中。

教学结尾处, 我抛出问题:“伯诺德夫人一家只是法国无数家庭中的普通一员, 伯诺德作为一名普通的家庭妇女, 为什么要带着自己幼小的孩子来参与这么危险的情报传递工作?”一石激起千层浪, 学生各抒己见, 有的认为国家兴亡, 匹夫有责, 有的尽情赞美伯诺德夫人一家的高尚品质, 有的表达对侵略者的憎恨, 有的则呼吁人们珍视和平, 称和平是世界人民共同的愿望。每篇小说的作者都要表达一个明确的观点, 这观点也就是小说的主题, 通过这个问题的讨论, 其实也进一步揭示了小说的主旨, 还关注了“为什么要写”的问题。

在立足文本的基础上作适当的延伸, 引导学生将思维的触角“伸”向更广阔的天空, 会对文本的理解产生积极的促进作用。教学结束后, 我依据学生的兴趣推荐了描述发生在二战时期事件的影片《辛德勒的名单》和《钢琴师》, 组织学生谈谈观后感。