结构算法（通用12篇）
结构算法 篇1
1、并行调度概述
并行分布计算是当前计算机科学的热点之一。调度算法是影响分布计算的关键因素，也是一个具有挑战性的课题。本文所述的并行调度依据RIPS (Runtime incremental parallel scheduling）任务调度策略设计的。RIPS是分布式系统中调度任务的一种擦略，它将整个调度过程分为两个阶段：系统阶段和用户阶段（如图1.1）ㄢ
一个RIPS开始于一个系统阶段，这个阶段执行一些初始化工作，调度初始化任务。第二个阶段是用户阶段，执行调度的任务，这个阶段有可能产生新的任务。当整个系统进入下一轮系统阶段时，上一轮调度没有执行完的任务与新产生的任务一起调度，两个阶段交替进行，直到所有任务执行结束。系统阶段可进一步分为两个组成部分：增量调度和并行调度，增量的含义是指在两次相邻的并行调度之间，系统中可能有新的任务产生，所以下一轮的并行调度是对发生了数量变化的任务集进行调度。增量调度决定系统什么时间开始下一轮并行调度。并行调度的含义是指系统并行地收集负载信息并完成任务的调度。
为了便于分析，我们假定：
⑴系统中每个站点有2个队列管理本站点上的任务：经调度准备执行的任务进入RTE (ready to execute）队列，新产生的未被调度的任务进入RTS (ready to schedule）队列；
⑵转换策略：系统中半数站点的RTE中的任务执行完毕时调用RING算法；
⑶定位策略：一个超载的任务沿着环的顺时针方向向下传递，直到有一个站点接受该任务；
⑷信息策略：调度算法在并行调度之前首先收集系统的负载信息；
⑸每个任务需要同样长的运行时间，负载尺度是任务个数，主控节点为发出init的节点
⑹选择策略：随机选择系统中任一未执行的任务进行调度
2、RING算法的具体描述
RING算法的步骤可描述如下：
(1) 按顺时针方向为每个节点编号i (i=0, 1, 2，…，n-1）, N为系统的节点总数；
(2) 令Wi为节点i的任务数，每个节点保留一个Wi;
(3) 主控节点j计算平均任务数Wavg=[ni=0∑1Wi/N]，
余数R=ni=0∑1Wimod N。把Wavg和R广播到全部节点；
(4) 节点收到Wavg和R后，计算本节点应调度多少任务：
当R=0时，每个节点应调度的任务数为Wavg;
如果：Wi=Wavg，则该节点不接收也不发送任务，开始用户阶段；
Wi<Wavg，则该节点准备接收Wavg-Wi个任务；
Wi>Wavg，则该节点选择Wi-Wavg个任务后向后传递，传递完成后，开始用户阶段；
当R≠0时，从编号为j+1开始的R个节点应调度的任务数为Wavg+1，其余节点为平均数Wavg;
如果：i在j+R之后且Wi=Wavg或i在j+1到j+R之间且有Wi=Wavg+1，则该节点不接收也不发送任务，开始用户阶段；
i在j+R之后且Wi<Wavg，则该节点准备接收Wavg-Wi个任务或i在j+1到j+R之间且有Wi<Wavg+1，则该节点准备接收Wavg-Wi+1个任务；
i在j+R之后且Wi>Wavg，则该节点准备接收Wi-Wavg个任务向后传递或i在j+1到j+R之间且Wi>Wavg+1，则该节点选择Wavg-Wi-1个任务向后传递，传递完成后，开是用户阶段；处于准备接收状态的节点，等待从该节点的前方传递来的任务，一旦满足条件，就开始用户阶段。
在该算法中，第 (1) 步只在系统初始化时执行，第 (2) 步通过一个全局检测操作得到全局的任务，在第 (3) 步，主控节点计算每个节点的平均任务数并广播出去，这样在第 (4) 步，每个节点就知道它是否超载。如果任务不能平均分配，则从主控节点j开始的R个节点分配Wavg+1个任务，这样他们就比别的站点多一个任务。从而在系统调度阶段的最后时刻，每个站点有几乎相同数目的任务。
3、RING算法的几个结论及其证明过程
结论一：RING算法执行后，每个节点的任务数最多相差1，即达到较好的负载平衡。
[证明]：根据算法的步骤 (4) ，当R=0时，每个节点分配的任务数均为Wavg，每个站点的任务数相差0；当R≠0时，从主控节点的下一节点开始的R个节点分配Wavg+1个任务，其他节点分配Wavg个任务，每个节点的任务数相差1。证毕。
结论二：当R=0时，RING算法使通信总量ni=0∑1Ci和任务传递
的总数ni=0∑1Wi最小，即最大限度地减少任务的迁移和通信总量。
[证明]：当R=0时，节点i与主控节点j之间只有一次通信，即向j报告负载量，j向i广播Wavg和R，只需一次通信就足够了，即Ci=
1，所以总的通信量ni=∑0-1Ci是最小化的。
在每个节点，如果Wi>Wavg，那么它要选择（Wi-Wavg）个任务向下一节点传递，这是从该节点传出的最小数目的任务数；同理，如果Wi<Wavg，那么要从前驱节点接收（Wavg-Wi）个任务，这是该节点能接收的最小数目的任务数。这样就实现了任务总的传
递数目ni=∑0-1Wi的最小化。
该算法也做到了最大程度地使计算本地化，因为有超载的节点才将Wi-Wavg个任务传递到其他节点，平载和轻载的节点不会迁移到任何任务。证毕。
引理1：为了平衡负载，异地任务的最小值为：ni=∑0-1 (max
[证明]：每个Wi<Wavg的节点必须从其他节点接收Wavg-Wi个
任务，以达到负载平衡，因此整个系统中应有ni=∑0-1 (max (Wavg-Wi0) ) 个任务发生迁移。证毕。
结论三：R=0时，RING算法使异地执行的任务总数ni=∑0-1 (max (Wavg-Wi, 0) ) 得到最小化，即能最大程度的使计算本地化。
[证明]：在RING算法中，每个节点先接收任务后传递任务，任一时刻执行RING算法，每个节点的任务数不小于Min (Wi, Wavg），因
此，所有的节点中，至少ni=0∑1 (min (Wavg, Wi) ) 个任务是本地的，因
此全部的异地任务之和不大于：N*Wavgni=∑0-1 (min (Wavg, Wi) ) =ni=∑0-1
正如引理1, RING算法最小化了异地执行的任务总数。证毕。
同理易证：R≠0时RING算法使异地执行的任务总数接近最小化。
4、总结与展望
本文针对并行计算中的调度问题，在结合其他基于环结构的并行调度算法的基础上给出了RING算法描述和结论及其论证，从而更好地证明了基于环结构的并行调度算法能较好地实现负载平衡，能最大限度地减少任务的迁移和通信量，且能最大程度地使计算本地化。
摘要：并行计算中的调度问题属于典型的NP完全问题, 目前许多优秀的并行调度算法所体现出来的优异性能都是以对调度问题的诸多限制条件为前提。因此, 如何在诸多限制条件的基础上设计一个相对优秀的调度算法成为一个重要问题。本文给出了一种比较好的并行调度算法--RING算法的描述、结论和详细的论证。
关键词：并行计算,调度算法,RIPS
参考文献
[1].王玎.协同标注系统中可扩展动态容错机制研究[D];华中科技大学;2006年
[2].宋术群.基于遗传算法的分布式系统中任务调度[D];青岛大学;2006年
[3].张淑丽.基于剩余函数的Job-Shop调度算法的研究[D];哈尔滨理工大学;2005年
[4].张坚.分布式工作流引擎及其负载平衡技术的研究与实现[D];国防科学技术大学;2005年
[5].陈国良.并行算法--排序和选择[M].合肥:中国科学技术大学出版社, 1990.
结构算法 篇2
100401200510计本（4）班章兴春
本学期所学习的《数据结构与算法》课程已经告一段落，就其知识点及其掌握情况、学习体会以及对该门课程的教学建议等方面进行学习总结。以便在所学习知识有更深刻的认识。
一、《数据结构与算法》知识点：
学习数据结构之前、一直以为数据结构是一门新的语言、后来才知道学习数据结构是为了更加高效的的组织数据、设计出良好的算法，而算法则是一个程序的灵魂。经过了一学期的数据结构了，在期末之际对其进行总结。首先，学完数据结构我们应该知道数据结构讲的是什么，数据结构课程主要是研究非数值计算的研究的程序设计问题中所出现的计算机处理对象以及它们之间关系和操作的学科。
第一章主要介绍了相关概念，如数据、数据元素、数据类型以及数据结构的定义。其中，数据结构包括逻辑结构、存储结构和运算集合。逻辑结构分为四类：集合型、线性、树形和图形结构，数据元素的存储结构分为：顺序存储、链接存储、索引存储和散列存储四类。最后着重介绍算法性能分析，包括算法的时间性能分析以及算法的空间性能分析。
第二章具体地介绍了顺序表的定义、特点及其主要操作，如查找、插入和删除的实现。需要掌握对它们的性能估计。包括查找算法的平均查找长度，插入与删除算法中的对象平均移动次数。
链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高。链表这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。
第三章介绍了堆栈与队列这两种运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；而队列要遵循“先进先出”的规则，教材中列出了两种结构的相应算法，如入栈、出栈、入队、出队等。在介绍队列时，提出了循环队列的概念，以避免“假溢出”的现象。算法上要求掌握进栈、退栈、取栈顶元素、判栈空盒置空栈等五种操作及掌握使用元素个数计数器及少用一个元素空间来区分队列空、队列满的方法。
第四章串和数组中，我们知道串是一种特殊的线性表，是由零个或多个任意字符组成的字符序列。串的储存结构分为紧缩模式和非紧缩模式。
基本运算需掌握求串长、串赋值、连接操作、求子串、串比较、串定位、串插入、串删除、串替换等。
第五章二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序。
树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。
第六章介绍了图的概念及其应用，图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。
最后两章集体说明了查找和排序算法，查找教材上介绍了静态查找表和哈希查找表，静态查找表中介绍了顺序查找、折半查找以及分块查找。哈希法中，学习要点包括哈希函数的比较；解决地址冲突的线性探查法的运用，平均探查次数；解决地址冲突的二次哈希法的运用。
排序是使用最频繁的一类算法，可分为内部排序和外部排序。主要需要理解排序的基本概念，在算法上、需要掌握插入排序（包括直接插入排序算法、折半插入排序算法），交换排序（包括冒泡排序算法、快速排序递归算法）,选择排序（包括直接选择排序算法、堆排序算法）等。
二、对各知识点的掌握情况
总体来看，对教材中的知识点理解较为完善，但各个章节均出现有个别知识点较为陌生的现象。现将各个章节出现的知识点理解情况列举如下。
第一章中我对数据和数据结构的概念理解较为透彻，熟悉数据结构的逻辑结构和存储结构。而对算法的时间、空间性能分析较为模糊，尤其是空间性能分析需要加强。
第二章，顺序表的概念、生成算法理解较为清晰，并且熟悉简单顺序查找和二分查找，对分块查找较为含糊；排序问题中，由于冒泡排序在大一C语言课上已经学习过，再来学习感觉很轻松。对插入排序和选择排序理解良好，但是，在实际运用中仍然出现明显不熟练的现象。由于在归并排序学习中感觉较吃力，现在对这种排序方法仍然非常模糊，所以需要花较多的时间来补习。此外串的模式匹配也是较难理解的一个地方。
链表这一章中，除对双向循环链表这一知识点理解困难之外，其他的知识点像单链表的建立和基本算法等都较为熟悉。
接下来的有关堆栈以及队列的知识点比较少，除有关算法较为特殊以外，其余算法都是先前学过的顺序表和链表的知识，加上思想上较为重视，因此这部分内容是我对全书掌握最好的一部分。不足之处仍然表现在算法的性能分析上。
在学习第六章时感觉较为吃力的部分在于矩阵的应用上，尤其对矩阵转置算法的C语言描述不太理解。稀疏矩阵相加算法中，用三元组表实现比较容易理解，对十字链表进行矩阵相加的方法较为陌生。
第七章是全书的重点，却也有一些内容没有完全理解。在第一节基本概念中，二叉树的性质容易懂却很难记忆。对二叉树的存储结构和遍历算法这部分内容掌握较好，能够熟练运用，而对于二叉树应用中的哈弗曼树却比较陌生。
第八章内容较少，牵涉到所学的队列的有关内容，总体来说理解上没有什么困难，问题依旧出现在算法的性能分析上。
散列结构这一章理解比较完善的知识点有：基本概念和存储结构。散列函数中直接定址法和除留余数法学得比较扎实，对数字分析法等方法则感觉较为陌生。对两种冲突处理的算法思想的理解良好，问题在于用C语言描述上。
最后一章，图及其应用中，图的定义、基本运算如图的生成等起初理解有困难，但随着学习深入，对它的概念也逐步明朗起来。邻接矩阵、邻接表和逆邻接表掌握较好，而对十字链表和邻接多重表则较为陌生。感觉理解较为吃力的内容还有图的遍历（包括深度和广度优先遍历），最小生成树问题也是比较陌生的知识点。最短路径和AOV网学习起来感觉比较轻松，而对于C语言描述却又不大明白。
由于平时上机练习的少，对于教材中很多算法都掌握的不是很熟悉、不过这些都是可以弥补的，我会在剩下的时间中不断练习书上给出的算法和练习，正如教材上说的，学习数据结构，仅从书本上学习是不够的，必须经过大量的程序设计实践，在实践中体会构造性思维方法，掌握数据组织与程序设计技术。
三、学习体会：
多做实验！这个就没有太多理由了，我一直觉得编程是一门熟练科学，多编程，水平肯定会提高，最重要的是能够养成一种感觉，就是对程序对算法的敏感，为什么那些牛人看一个算法一下子就看懂了？而自己要看很久才能弄懂，而且弄懂了过了一阵子又忘记了？其实这个是因为牛人们以前看的程序很多，编得也很多，所以他们有了那种感觉，所以我觉得大家应该多看程序，多写程序，培养自己的感觉。
复习和考试的技巧，我想大家应该都有这样的感觉，就是觉得自己什么都掌握了，但是在考试的时候就是会犯晕，有时候一出考场就知道错在哪个了，然后考完以后一对答案，发现其实考得很简单，应该都是自己会做的，这个就是与自己的复习和考试的技巧有关系了。
首先就是复习，前面已经说过其实我们学的算法也就是几十个，那么我们的任务也就是理解这几十个算法，复习也就是要加深你的理解。如何理解算法，然后理解到什么程度呢？ 是能默出整个算法吗？其实不是这样的，数据结构的考试有它的特点，考过程考试了，大家应该都发现数据结构其实不要求你把整个算法背出来，它注重考察你的理解，那么怎么考察呢？其实也就是两种方式吧，一种就是用实例，就是给你一个例子，要你用某个算法运行出结果，我想这个期末考试的时候仍然会有很多这样的题目，比如排序那块就很好出这样的题目，要复习这种题目我觉得很简单，就是每个算法都自己用例子去实践一下，以不变应万变，我期中复习的时候就是这样去做的，而且考试之前我就觉得那个并查集的题目就很有可能会考，于是就自己出了几个例子，做了一下。另外一种考察方式就是算法填空和算法改错，可能有一些同学觉得这种题目很难，其实我们首先可以确定这两种题目肯定是与书上算法有关系的，只要理解了书上的算法就可以了，有人觉得看完书以后什么都懂了，而且要默也默得出来，其实不是这样的，算法改错和填空主要是考察的细微处，虽然你觉得你默得出来，那是能够默出算法的主体部分，很多细微的地方你就会很容易忽略。我想大家考过期中考以后应该都有这种感觉吧？那要怎样解决这种问题呢？ 我觉得有两种方法，一种就是自己去编程实现，这种方法比较有意义，还能够提高编程水平，另外一种就是用实例分析算法的每句话，我认为这种方法是最有效的。
然后还有一种题目，就是最后的写算法的题目，我觉得这种题目还是很好解决的，只要是能够自己做出作业的，基本上都会很容易做出来，这也是为什么我前面觉得平时做作业应该自己独立思考的原因，同时做这种题目千万要小心，尤其是题目简单的时候，那肯定会有一些小地方要考虑清楚，一不小心就会被扣掉很多分，这样很不值。
我觉得考试的时候没有太多要讲的，只要复习好了，考试的时候细心一点就可以了，然后就是做一个题目开始就要尽量保证正确，如果觉得留在那里等后面做完了再来检查，这样错误还是很有可能检查不出来，我期中考试的时候就基本上没有检查，因为我做每个题目都是确保正确，用的时间也挺多的，然后也觉得没有检查的必要了。
三、对《数据结构与算法》课程教学的建议
1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。
2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。
3、要更加重视实验的重要性。
数据结构最短路径算法及其应用 篇3
关键词： 最短路径 Dijkstra算法 Floyd算法 图论
最短路径，就是在所有路径中找到一条距离最短的路径，而我们所说的最短路径不仅指地理意义的距离最短，而且可以引申到其他度量，如时间、费用、路线容量。相应地，最短路径问题就成为最快路径问题，最低费用问题等，所以我们所说的最短路径也可以看做最优路径问题。最短路径问题在交通网络结构的分析，交通运输路线的选择，通讯线路的建造与维护，运输货流的最小成本分析，城市公共交通网络的规划等方面，都有直接应用的价值。最短路径问题在实际中常用于汽车导航系统及各种应急系统等这些系统，一般要求计算出到出事地点的最佳路线的时间应该在1s到3s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效的。经典图论与不断发展完善的计算机数据结构及算法的有效结合使新的最短路径算法不断涌现。
一、图论基本概念
1.图的定义。图（graph）是一种较线性表和树更为复杂的数据结构，图与线性表和树的结构区别表现在结点之间的关系上，线性表中的每个结点（除首尾结点外）都有一个前驱结点和一个后继结点，结点与结点之间的关系是一对一的关系；树上的每个结点都有一个父结点（根结点除外）和一个或多个孩子结点（叶子结点除外），结点与结点的关系是一对多的关系；而图中结点之间的关系是多对多的关系，结点与结点之间的连接是任意的，每对结点间可以有连接也可以没有连接。
2.图的存储结构。除了存储图中各个顶点本身的信息外，还要存储顶点与顶点之间的所有关系。常用的图的存储结构有邻接矩阵、邻接表、十字邻接表和邻接多重表。
二、最短路径问题
所谓最短路径即从图G中某对顶点Vi和Vj（i≠j）之间的所有路径中选出权值之和最短的一条路径作为顶点Vi到顶点Vj的最短路径。其中边的权值可多种，如路途、费用、耗时等，也可以同时存在多种权值，根据给定的比例，算出边的综合权值。
1.最短路径。在一个无权的图中，若从一个顶点到另一个顶点存在一条路径，则称该路径长度为该路径上经过的边的数目，等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在多条路径，每条路径上经过的边数不同，即长度不同，把长度最短的那条叫做最短路径。
2.最短路径算法。求图中最短路径有两方面问题：求图中某一顶点到其余各顶点的最短路径与求图中每一对顶点之间的最短路径。它们分别有Dijkstra算法和Floyd算法。
2.1Dijkstra算法。Dijkstra算法又称为标号法，是用于求解单源点最短路径的实用算法，至今仍然被公认为是解决从固定点出发到网络中的任意顶点的最短路径问题的较好方法之一。基本思想如下：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中，V为网中所有顶点集合。按最短路径长度递增的顺序逐个用V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。
2.2Floyd算法。Floyd算法能够求得任意顶点之间的最短路径。基本思想是任意2个顶点vi到vj的距离的带权邻接矩阵开始，每次插入一个顶点vk，然后将vi到vj间的已知最短路径与插入顶点vk作为中间顶点时可能产生的vi到vj路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出N个矩阵D（1），D（2）…D（n），当所有顶点均作为任意 2个顶点vi到vj中间顶点时得到的最后的带权邻接矩阵D（n）就反映了所有顶点对之间的最短距离信息，成为图G的距离矩阵。
三、 应用举例
1.Dijkstra算法在公交网络中的应用。在纷繁复杂的城市公交网中，如果想寻找到一条从当前某个站点到达另一个目的站点的最短路径应该怎样实现呢？针对这个问题采用图论中最短路径思想进行了思考和研究，并采用Dijkstra算法实现搜寻计算操作和过程。
（1）实际问题描述。公交网络中最短路径问题可以描述为从某起始站点S出发到达目的站点E，其中S和E之间可行的线路往往不只一条，而是有很多条，那么这么多可行线路中哪一条是最短的呢？这里“最短”指实际走过的路程最短，或指在不计算公交换乘花费时间和公车保持匀速行驶的前提下，能够以最短时间到达目的地中的“最短”。要求解这个问题如果不考虑其他各方面的复杂因素，就可以看成一个简单的最短路径问题。
（2）数学模型建立。起始站点、目的站点及所有可行路径和中间站点构成的交通网络，可以抽象为一个图状的数据模型——有向带权图记为G=（V，E，L），其中V表示所有站点的集合，假设共有N个站点；E表示所有直接通路或直通边的集合，假设共有M条直通边，注意，在实际应用中，这里的边是有方向性的，边的方向表示该直接通路的可行方向；L表示每条直接通路对应的边权集合，即每条直通边对应的距离值或时间开销等。
（3） 实际问题抽象化。经过上述分析和建模，实际最短路径问题可抽象为有向带权图中两顶点之间的最短路径问题。
四、结语
若寻找从起始点到其他所有顶点的最短路径，按照Dijkstra算法则最多需要经过N-1步的搜寻计算操作（N表示G中的顶点个数）。在实际应用中，Dijkstra算法称为单源点最短路径算法。事实上，Dijkstra最短路径算法除了可以用在公交网络上之外，还可以用在现实生活的很多方面，如邮政线路、物流线路、管道布线等，我们还可以不断将其推广应用于更多方面，从而使数学与计算机科学能够更充分地为人类服务。
参考文献：
[1]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2002.
[2]李春葆，曾慧，张植民.数据结构程序设计题典[M].北京：清华大学出版社，2002.
[3]张永，李睿，年福忠.算法与数据结构[M].北京：国防工业出版社，2008.
[4]刘玉龙.数据结构与算法实用教程[M].北京：电子工业出版社，2007.
[5]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社，2004.
解释结构模型算法实现研究 篇4
用节点和有向连接边构成的有向连接图来描述的一个系统结构。不仅可以分析系统的要素选择是否合理,还可以分析系统要素相互关系对系统总体的影响等问题。将复杂的系统分解为若干子系统(或要素),利用矩阵计算方法以及计算机的帮助,最终将系统转换成一个多级递阶的结构模型。
1.1 建立邻接矩阵
首先分析当前系统由哪些要素构成,并将需要分析的要素编号(Si,i=1,2,...,n);然后将各个要素之间的关系描述出来,邻接矩阵A中的元素aij表示要素Si和Sj的“从至关系”。
1.2 建立可达矩阵M
设I为与A同阶的单位矩阵。进行以下的布尔运算可以求得可达矩阵(从一个要素到另外一个要素间是否存在连接的路径)M=(A+I)k-1≠(A+I)k=(A+I)k+1。
1.3 各个要素的级别建立
从可达矩阵作出层级有向图。定义两个集合R(Si)、A(Si)。R(Si):从Si出发,可能到达的全部要素集合,称之为可达集合;A(Si):所有可能达到Si的要素集合,称之为先行集合。以R(Si)、A(Si)求出R(Si)∩A(Si)集合。R(Si)∩A(Si)是要素Si能达到,而且又是能够达到Si全部要素集合。如果R(Si)∩A(Si)=R(Si),则R(Si)这个集合中的要素是全部要素中的最高层级。按照这种方法,将有向图中的最高层级决定后,可从可达矩阵中排除。然后将剩下的要素按照同样的方法求出其中的最高层级,如此,找出系统中各要素所在的不同层级。
1.4 建立层次结构图
在最下层放第一级要素,其上面放第二级要素,直到把所有的要素都放到相应的层次上,然后用有向图的形式来表示整个系统要素的层次关系。这样整个系统结构就会完整、清晰地呈现。
2 实现过程关键算法分析
2.1 可达矩阵算法
可达矩阵建立方法有:(1)邻接矩阵加单位矩阵自乘法(按布尔代数运算法则);(2)上下位集推断法(包括解自蕴涵方程);(3)经验对话法。前两方法中除了解自蕴涵方程有时会遇到麻烦外,均可较方便地求出可达矩阵。方法(3)虽可免去矩阵计算之繁,但有时并不能给出可达矩阵[2]。
采用邻接矩阵加单位矩阵自乘法实现算法如下:
2.2 级别要素建立算法
2.3 关系图实现算法
2.4 目标矩阵与实现结果(见图1)
3 存在的问题
(1)用ISM分析问题只能将系统内部的联系简化成递阶关系,只知道元素之间有无关联,但无法知道这种关联的强弱,以及这种关联是线性的还是非线性的。
(2)用ISM进行系统分析的关键是确定系统要素之间逻辑关系的邻接矩阵。由于邻接矩阵通常由领域专家通过讨论确定,因此邻接矩阵的主观依赖性比较强。
尽管ISM存在这些缺陷,其价值不可抹杀,价值体现于可以快速和比较准确的建立系统结构关系。
参考文献
[1]戴敏利,谈国新,陆峰,等.解释结构模型(ISM)在教学计划制定中的应用[J].杭州:计算机时代,2006(10):58-60.
[2]吴振奎.解释结构模型与层次分析法等的注记[J].天津:天津商学院学报,1998(5):45-48.
数据结构算法设计与分析 篇5
网页制作、程序设计Java、JSP程序设计、Oracle、XML程序设计、计算机网络、SSH（Struts+Spring+Hibernate）框架、Java EE程序设计、Ajax程序设计、Linux+PHP+MySQL程序设计、Android手机开发、UML系统分析与设计、性能测试、自动化软件测试、软件质量保证、毕业设计及项目综合实训等。
数据结构、计算机网络、计算机组成原理、操作系统原理、编译原理、数据库原理及应用、金融学概论、西方经济学等基础理论课程；
网页制作、程序设计Java、JSP程序设计、J2EE程序设计、SQL Server数据库、Oracle数据库、Linux操作系统、UML系统分析与设计、软件工程、XML程序设计、SSH框架、金融市场学、ERP财务管理、管理信息系统、投资银行学、商业银行学、国际金融管理、毕业设计及项目综合实训等专业课程。
数据结构、计算机网络、计算机组成原理、操作系统原理、数据库原理及应用、软件工程、软件测试等计算机基础理论课程；
结构算法 篇6
【摘 要】《算法导论与体系结构》课程是电子信息技术类的基础课程，但也比较强调实践性。本文针对当前该课程教学中存在的问题，探索基于案例驱动的算法导论与体系结构教学改革，探索算法导论与体系结构教学中案例设计，并将其应用于实际教学过程中。
【关键词】算法 体系结构 案例驱动 教学改革
IT技术已成为社会发展的主要核心技术之一，在过去短短的几十年时间里，IT技术涉及通信领域（移动通信的交换设备、基站和手机、IP电话等）、消费类电子设备（数字照相机、摄像机、机顶盒、家庭影院系统等）、机器人及各种自动控制系统等典型应用，这些都离不开算法实现。对电子信息类学生而言，《算法导论与体系结构》课程的开始，能够使其了解和掌握算法与体系相关的实用技术。但是算法与体系结构技术的发展，其速度都超出我们的预料。同时，应用的发展又不断地对技术的发展提出许多新的更高的要求，形成一个相互促进的良性循环。
1. 课程特点及教学现状
《算法导论与体系结构》顺应这一发展方向而为电子信息科学与技术专业信号处理方向学生开设的专业课。但是就目前的课程内容和教学体系来看，本课程虽然介绍了一些经典算法相关的知识，但针对性不强，无法有效激发学生主观能动性，而且当前所采用教材主要还是以传统理论，与本系其他课程如数字图像处理、智能信息处理、模式识别等方面联系不是很紧密，并且也不符合目前IT技术新的应用特别是多媒体相关领域的发展方向。因此，如何利用《算法导论》课程平台，使学生能对数字信号处理、数字图像处理、模式识别等方面有一个更为深入的认识，并使本专业毕业生具有利用实际算法解决实际问题的实践能力是本教改项目所要解决的重要问题。
针对上述问题，从C语言、数据结构等基础知识介绍入手，以面向应用为导向进行课程开发和设计，强调实践教学行动的过程属性，按照典型的实践项目开发过程逻辑编排课程内容，设计教学环节，组织教学过程。通过该课程的实践探索，开发一套行之有效的课程教学体系，进而推广到其他类似课程，全面提升学生的就业竞争能力
2. 算法导论与体系结构教学中案例设计探索
在案例教学中，教师根据课堂教学目标和教学内容的需要，以现实生活中的一些应用为蓝本，通过设计具体教学案例，让学生把自己纳入案例场景，引导学生参与分析、讨论、实践等，通过讨论或者研讨来进行学习的一种教学方法。
案例教学首先要有明确的教学计划，主要包括特定的教学对象、明确的教学目的、具体追求的教学效果和对教学过程的整体设计及其控制。课程教学中所使用的案例既不是编出来讲道理的故事，也不是写出来阐明事实的事例，而是为了达成明确的教学目的，基于一定的事实而编写的故事。
在《算法导论与体系结构》课程中，我们采用了以下几个方面来探索案例设计：
2.1 课程定位与目标
《算法导论与体系结构》在强调算法原理的基础理论的同时，与实践和应用紧密结合，在教学中占有举足轻重的地位。在课程设计上本着以“实际、实用、实践”为原则，淡化理论知识，突出应用技术。通过本课程的学习，使学生较系统地掌握算法开发编程环境，对其编程语言和开发流程有基本的了解，具备基本的算法设计开发与实现能力。
以应用实践引领知识、技能和态度，让学生在完成具体应用的过程中学习相关知识，发展学生的综合能力；掌握用所学知识解决实际问题的方法与手段，增强对各种问题能以多角度探寻解决问题的道路的素质；并具有良好的科学态度和创新精神，合理地提出新思想、新概念、新方法的素养。
2.2课程内容与教学设计
《算法导论与体系结构》课程的内容设计应体现连续性、实用性和前沿性，旨在使学生了解业界最新的算法技术发展动态和发展方向并具备一定的实践能力，因此必须紧跟国际潮流重新选择课程内容。另外，由于学生在之前的学习过程中已经修完了数字信号处理、数字图像处理等必修课程，也有模式识别、机器视觉和多媒体技术之类的选修课程，因此在教学设计中也充分考虑与前面的课程相融合，从实际的角度来巩固所学知识。同时也注重教学内容的实用性和针对性，以实践性知识为主，陈述性知识为辅，使学生能更充分地了解相关算法在各个领域的应用状况。
在教材内容的筛选上，尽量选用近两年比较新的教材作为主要教材，以在网络中及时更新的IT公司笔试题目作为辅助材料，并将算法应用的成熟案例（如业界比较成熟的方案或自己的横向课题）作为实例介绍给学生。力求选择的案例来自生产实际，同时充分考虑其复杂度和实用性，以保证学生在完成时态度认真，并能有效促进学生兴趣，拓展学生能力。
在教学方法上，强调以学生为主体、以教师为引导，将理论教学和实践教学集成化，使课堂学习融“教、学、做”为一体。在教学过程中注重学生学习方案的设计，运用自学、讲授、答辩、咨询、示范、操作多种形式进行教学。在具体的教学方案中要注重目标、过程、情感、结果的设置，充分调动学生个体和班、组团体的主观能动性，激发学生学习热情，使学生能力得到全面的发展和提高。
2.3实践环节设计
在前期的课程如数字图像处理、智能信息处理等都具有相应的课程设计环节，在这一环节中，学生会根据教师要求用Matlab或C语言实现一个比较系统的算法或方案。而在《算法导论与体系结构》的实践环节，可以充分利用这些算法或方案设计的结果，与实际的IT应用相结合，让学生真正体会算法是如何实现的。选择比较成熟的项目或案例都，可以充分地把理论知识、实践技能与实际应用环境结合在一起。在课程实践过程中要充分发挥学生的主体作用，给学生以足够发挥的空间，让学生真正动起来，激发学生的学习积极性，培养学生独立分析问题和解决问题的能力、自我控制与管理能力、做计划的能力和评价的能力。同时，以小组协作式进行实验，有利于发挥学生的团队合作精神，培养学生的协调人际关系能力，增强社会责任感。通过完成典型项目或任务，激发学生的学习动机，使之获得完成工作任务所需要的综合能力，提高自身素质。
2.4 教学团队建设
在《算法导论与体系结构》课程建设的教师团队中，进一步加强与行业、企业及各种社会教育资源的深度合作，选择长期在一线从事相关科研工作的教师作为主体，同时邀请业界资深技术人员做补充。教师团队自于实际企业，有着丰富的、实实在在的企业生产、管理经验，这些教师的经历本身就是很好的案例。业界专业人士参与实践课程设计，直接走上讲台，把技术开发岗位中需要的技术能力以及开发过程真实的描述出来，加深学生融入案例场景。
3. 结语
《算法导论与体系结构》课程是电子信息技术类的基础课程，但也比较强调实践性。一定要与当前飞速发展的机器学习、数据挖掘等IT技术相结合，将导航、机器人、移动互联网等实际应用加入案例，才能不断完善该课程教学内容，提高案例教学效果。
【参考文献】
[1]冯杰，黄海，胡洁，曹丽. 基于案例驱动的《DSP应用技术》教学改革探索[J].科技信息，2011（33）：19-20.
[2]渠丽岩. 让学生在快乐中学习：谈案例教学法在“单片机原理与应用”教学中的应用[J]. 计算机教育，2009（18）：93-95.
识别稳定的局部社区结构算法 篇7
社区结构对研究分析网络内部相互作用、社区演化都具有重要意义。在许多实际应用中,由于条件限制往往只能获取局部网络信息,或者只需分析某个特定群体的社区结构,这就对社区识别提出了限制和要求,为此需要研究如何利用网络局部信息进行局部社区识别。
Newman和Girvan于2004 年首次提出基于模块度的社区评价测度[1],由此引发了社区识别研究的热潮。文献[2]提出基于结构相似度的方法来聚类节点,以识别网络中的聚类和“离群”值。文献[3]提出的基于模块度识别社区的贪心算法采用树状图描述社区结构、运用层次聚类方法在线性时间内快速处理更大规模的分层网络。然而,以上几种识别方法都需要知道网络的整体拓扑结构。
文献[4]给出的局部社区结构识别算法从源顶点出发,依据一组节点到源节点的测度距离来增加顶点,该算法的性能取决于开始节点的选择,此外,该算法缺少一个适当的停止标准,仍然依赖于阈值。文献[5]定义了局部社区模块度R,采取最大化局部模块度的方法来发现局部社区,通过迭代增加邻接节点来产生R的最大增值,直到社区达到预定的规模。文献[6]给出的算法采用基于链接密度的社区评价测度来衡量社区结构,从给定的起始节点出发,首先提取可能的候选集节点,然后优化社区结构,该算法无需初始参数且可发现从特殊节点开始是否存在局部社区,但其存在着所发现社区不稳定的问题。文献[7]给出的局部聚类算法的特点是基于密度的组内聚性进行社区结构的扩展,它能够较好的发现小规模的社区结构。Andersen提出基于“剪枝增长过程”识别局部二分社区的聚类算法[8],在二分网络中该算法获得很好的社区识别效果。文献[9]提出基于极值优化的算法,通过最优化模块度来识别复杂网络中的社区结构。文献[10]给出的基于模块度矩阵的算法通过实现模块度的最大化过程来识别社区结构。文献[11]将局部中心节点作为局部网络的核心节点,围绕局部中心节点来扩展局部社区,以改善局部社区发现结果的精确度。文献[12]定义外部节点与局部社区之间的连接相似度,通过聚类、优化和剪枝三个步骤循环迭代,直至不能通过聚类外部节点使局部模块度增大时则停止迭代,以期发现更好的局部社区。上述算法识别出的社区包含较多的离群值,准确率不够高、社区划分效果不够理想。
本文给出一种基于提取局部团、通过局部团扩展社区、自动选择社区扩展的终止条件的局部社区识别算法,以发现稳定的社区结构、保留最优社区结构。
1 识别算法
本文给出的局部社区识别方法是: 1挖掘提取网络中的局部团结构作为初始社区; 2从局部团开始扩展,迭代遍历局部团的邻接节点集,每次选择链接密度最大增量的邻接节点添加到社区结构中; 3进行剪枝操作,移除“离群”节点。
1. 1 提取局部团
局部团属于稠密子图,它由一个节点及其邻接节点组成,是社区内部具有最高链接密度的局部结构。从一个局部团开始进行社区扩展,初始社区具有较高的链接密度和稳定性。为了维持局部团较高局部链接密度的特性,不能将一个节点的所有邻接节点都添加到团结构中,需要移除一些链接密度低( 有较少的内部链接) 的节点。我们用D表示识别出的社区,节点集合S表示图中未知部分的节点,S包含邻接于D中节点但不属于D的节点。定义D的两个子集: 核心节点集C和边界节点集B,C中节点与D外部节点不存在邻接边,B中节点至少有一个邻接节点在集合S中。
记节点v所在的局部团为cliquev,Lv表示局部团cliquev的链接密度,L( u,cliquev) 表示节点u在局部团cliquev中的链接密度,Lv和L( u,cliquev) 分别按式( 1) 和( 2) 计算:
其中,Lv - in表示局部团cliquev的平均内部链接密度,Lv - ex表示局部团cliquev的平均外部链接密度,Deg( u,cliquev) - in表示节点u与局部团cliquev中节点的链接数目,Deg( u,cliquev) - ex表示节点u与局部团cliquev外部节点的链接数目,Lv - in和Lv - ex分别按式( 3) -( 4) 计算:
其中,INi表示节点i与局部团cliquev中节点相连边的数目,Boundry表示局部团cliquev中与集合S有边相连的节点集合,EXj表示节点j与S中节点相连边的数目。
满足下列条件的邻接节点u将被添加到局部团cliquev中:
其中,平衡因子a用来平衡局部团链接密度Lv和局部团cliquev大小的关系: 增大a可以提高局部团链接密度Lv,但减小了局部团cliquev的规模; 反之,减小a可以降低局部团链接密度Lv,却增大局部团cliquev的规模。我们采取启发式策略来提取局部团,搜索局部子图结构G中所有节点,并按Lv值倒序排列G中节点,找出满足式( 5) 要求的局部团结构。
提取局部团算法( 简记为Jbt_get算法) 描述如下:
算法1 Jbt_get算法
按Lv值对G中节点进行降序排列,得到有序图G’;
利用Jbt_get算法可以找出局部社区中链接密度较高的局部团结构,为扩展局部团、识别出局部社区结构提供基础。
1. 2 局部团扩展
提取局部团cliquev之后,迭代合并集合S中的节点到局部社区D中,一次迭代社区添加一个新节点。在迭代过程中,使用社区D的链接密度L作为适应度函数,能较好地优化局部社区结构。提取出的局部社区结构D中可能存在“离群”值的干扰,因此需对社区结构D应用剪枝策略,移除“离群”节点,以获得高质量的社区结构。记Lin、Lex和L分别代表社区结构D的平均内部链接密度、平均外部链接密度和链接密度,Lin'、Lex'和L'分别代表增加或者删除节点v后社区D的平均内部链接密度、平均外部链接密度和链接密度,其计算公式可参见文献[8]。
当增加新节点到社区D中时,下列3 种情形可能导致L' > L的结果: 1 Lin' > Lin和Lex' < Lex;2Lin' < Lin和Lex' < Lex; 3 Lin' > Lin和Lex' > Lex。
显然,情形1的节点增强了社区的内部联系,降低社区外部的链接密度,此类节点属于需要合并到社区D中的节点。情形2的节点属于离群值,因为它同时降低对社区内部和社区外部的链接密度。情形3的节点在增强社区内部联系的同时,也提高了社区外部的链接密度,该节点可能同时链接两个社区中,在这种情况下,为保证社区具有较高的链接密度,我们不将该类节点合并到社区D中。因此,算法检查社区结构D中所有节点,只保留属于情形1的节点。
局部团扩展算法Jbt_extend描述如下:
算法2 Jbt_extend算法
Jbt_extend算法开始时将局部团cliquev内的所有节点都添加到社区D中,与S有边连接的节点添加到B中,与S没有边连接的节点添加到C中,并初始化S。然后迭代地扩展社区,每次迭代将加入一个新节点到D中,这个节点存在于集合S中,在迭代过程中找出L的最大增量。每次迭代,遍历集合S,计算加入新节点v后L的增量,如果L的增量大于等于0,则更新D、B、C和S; 否则,将节点v从社区D中移除。如果所有的邻接节点都不能够使L的增量大于或等于0,则迭代自动停止; 或者当集合S为空集时,也停止迭代。对于识别出的社区结构D,为降低“离群”值的干扰,依次遍历D中各个节点u,并进行“剪枝”和“添加”操作,比较“剪枝”和“添加”前后Lin和Lex值的大小,进而保留属于情形1 的节点。
与以往的局部社区识别算法不同的是,Jbt_extend算法提取出局部团作为社区的初始状态,而不是随机选择一个节点作为初始社区,同时迭代过程中选择L增量最大的邻居节点添加到社区结构中,如果不存在新的结点进一步提高L的值,或者没有结点剩余,则自动退出迭代,从而使得迭代扩展后识别出的社区比较稳定; 为保证提取出的社区结果具有较高的准确率,算法遍历迭代社区结构中的节点,通过“剪枝”和“添加”操作,保留属于情形1 的节点。
2 实验
2. 1 实验环境
实验硬件平台为内存容量4GB、CPU为Intel( R) Pentium( R) G2020 的双核计算机,运行的操作系统为Windows XP,采用C ++ 语言编程实现算法。给定局部团cliquev、网络真实社区结构的数据集Cvreal、提取出的局部社区结果Cvalg,采用与文献[6]相同的具有代表性的precision( 准确率,简记为p) 、recall( 召回率,简记为r) 及F - measure( 简记为F)评价局部社区识别算法的性能,p为局部社区中被正确划分的节点数在局部社区所占的比例、r为局部社区中被正确划分的节点数在标准数据集所占的比例、F为是p和r的加权调和指标:
2. 2 实验结果分析
2. 2. 1 人工生成网络上的实验
文中采用有代表性的GN网络[1]作为人工生成网络的实验。GN网络包含128 个节点,每个社区有32 个节点,节点之间的边是随机生成的,din表示社区内部边的数目,dout表示社区外部边的数目,保证同时满足对任意节点有din+ dout= 16。通过保持每个节点的度数不变,改变dout的值,能够得到多组边界稀疏度不同的数据集。
社区内部的链接密度随dout的增大逐渐降低,维持dout< 8,才能得到比较合理的社区结构。实验中人工生成网络的所有数据集都满足此要求。
实验自动生成500 组GN网络,根据dout不同,每组各有7 个GN网络( 其dout取值分别为1,2,3,4,5,6 和7 ) 。对这些数据集分别运行本文提出的局部团识别算法Jbt _extend和有代表性的Chen算法[6],实验结果如图1 - 3 所示。
从图1 的结果可知,随着dout的增大,社区结构趋于不明显,致使Jbt_extend算法和Chen算法识别的效果都有所下降,但是,Jbt_extend算法识别准确率明显高于Chen算法。这主要是因为局部团具有密集性,在社区扩展过程中,只有链接密度高的节点才能够合并到社区中,这样就降低了社区外节点被错误添加到社区的可能性。当dout≤ 6 时,Jbt_extend算法取得了很好的识别效果,准确率几乎均为100% ,当dout> 6 时,社区外部边的数目增多,社区的边界节点链接密度增大,社区内部链接密度降低,社区结构不够明显,导致提取出的社区结果准确率p值开始下降。但是,即使当dout= 7 时,Jbt _extend算法识别准确率也达到80% ,识别效果一直保持在比较高的水平,这表明Jbt _extend算法具有高稳定性。
图2 的结果表明: 对于所有的dout值,Jbt_extend算法的召回率均高于Chen算法,特别是当dout≤5时,Jbt_extend算法可以识别出社区的完整结构; 而Chen算法则表现较差,召回率随dout增大下降比较明显。这是因为Chen算法没有充分考虑到“离群”值的影响,识别出的社区结构中包含较多链接密度低的节点。当dout> 5 时,社区内部和外部边的数目开始趋于相等,情形3中的节点增多,为了确保社区具有较高的链接密度,Jbt_extend算法和Chen算法都严格控制不将此类节点合并到社区中,从而可能使得提取出的局部社区结果Cvalg下降,两种算法的r值呈下降趋势。
图3 给出了dout逐步增大时,Jbt_extend算法和Chen算法F值的对比结果。
从图3 的实验结果可知,无论dout取何值,Jbt_extend算法识别的效果均明显优于Chen算法。从图1 - 2 可以看出,当dout> 5 时,p和r值都呈下降趋势,F作为p和r值的加权调和指标,它也应该是呈下降趋势。图3 的实验结果验证了这种趋势。
图1 - 3 的结果表明Jbt_extend算法识别人工生成网络社区结构的能力具有明显的优势,其识别出的局部社区结构质量高。
2. 2. 2 真实数据集上的实验
NCAA足球赛网络图包含180 个节点以及787条边,任意两个节点之间存在边代表两个球队之间有一场比赛[2]。NCAA中有115 个球队归属于11个社区,社区内部的球队通常有更加频繁的比赛,另外还有4 个球队各自单独构成一个社区,其余所有节点没有社区,作为“离群值”。NCAA足球赛网络的拓扑结构已知。
实验多次运行Jbt_extend算法和Chen算法,取多次运行实验结果的平均值评价算法效果,仍然采用p、r和F值比较Jbt_extend算法和Chen算法对NCAA网络图中社区结构的识别效果,实验结果如表1 所示。
从表1 的结果可知,Jbt_extend算法和Chen算法均能识别出11 个社区,r值均为1,Jbt_extend算法和Chen算法都能够将真实社区结构中包含的节点完整识别出来,但是Jbt_extend算法得到的准确率和F值都优于Chen算法,这说明Jbt_extend算法不仅能完整地提取出真实网络中的社区结构,而且能很好地排除“离群值”的干扰。Jbt_extend算法不是随机选择初始节点,而是选择具有较高链接密度的局部团作为社区膨胀中心点,实验结果表明Jbt_extend算法每运行一次即可发现结构稳定的社区。而Chen算法随机选择一个节点作为初始状态,然后通过此节点进行扩展,以将更好的节点合并到社区中,算法效果很大程度上依赖于初始节点的选取,多次运行的实验结果表明,Chen算法每次选择的初始节点的社区链接密度不同,致使每次运行的识别效果不稳定,也难以保证社区划分效果理想。
综上所述,与局部社区识别代表性的Chen算法相比,本文给出的Jbt_extend算法在人工数据集和真实数据集上能够自动停止迭代扩展,输出稳定的结果、发现高质量的社区结构。
3 结束语
本文给出的局部社区发现算法从提取出的局部团出发进行扩展,迭代遍历局部团的邻接节点集,每次选择链接密度最大增量的邻接节点添加到社区结构中,以不存在新的节点进一步提高局部链接密度值或者没有节点剩余作为迭代终止条件,从而解决已有识别方法稳定性不高、不能够自动停止迭代扩展等的问题,通过“剪枝”和“添加”操作可确保提取出的社区具有较高的准确度。在确保准确度和稳定性的前提下,如何将局部社区发现算法应用到动态社会网络中社区演化分析将是下一步的研究工作。
摘要：通过提取出具有高链接密度的局部团,从局部团出发进行扩展社区,设计自动选择社区扩展的终止条件,以保留最优社区结构,提出一种社会网络局部社区识别算法。在人工生成网络和真实网络上的实验结果表明,与同类算法相比,该算法能够识别出稳定的局部社区结构,提升了局部社区识别结果的准确率。
关键词：社会网络,局部社区识别,局部团,局部链接密度
参考文献
[1]Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Physical review E,2004,69(2):026113.
[2]Xu X,Yuruk N,Feng Z,et al.Scan:a structural clustering algorithm for networks[C]∥Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining.New York:ACM,2007:824-833.
[3]Clauset A,Newman M E J,Moore C.Finding community structure in very large networks[J].Physical review E,2004,70(6):066111.
[4]Bagrow J P,Bollt E M.Local method for detecting communities[J].Physical Review E,2005,72(4):046108.
[5]Clauset A.Finding local community structure in networks[J].Physical review E,2005,72(2):026132.
[6]Chen J,Zaane O,Goebel R.Local community identification in social networks[C]∥Proceedings of 2009 International Conference on Advances in Social Network Analysis and Mining.Piscataway,NJ:IEEE,2009:237-242.
[7]Xu J.Identifying Cohesive Local Community Structures in Networks[C]∥Proceedings of the 30th International Conference on information Systems,Phoenix,Arizona,USA,Dec.15-18,2009:112.
[8]Andersen R.A local algorithm for finding dense subgraphs[J].ACM Transactions on Algorithms,2010,6(4):60.
[9]Duch J,Arenas A.Community detection in complex networks using extremal optimization[J].Physical review E,2005,72(2):027104.
[10]Newman M E J.Finding community structure in networks using the eigen vectors of matrices[J].Physical review E,2006,74(3):036104.
[11]Chen Q,Wu T T,Fang M.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537.
数据结构中图的遍历算法 篇8
因为图的复杂性, 在图中的任何顶点都可能和其余顶点相邻接, 故在访问了某个顶点之后, 可能沿着某条路径又回到了该顶点。为了避免重复访问图中的同一个顶点, 在搜索访问过程中必须记住每个顶点是否被访问过, 为此可设置一个向量visited[vexnum], 它的初始值为{0}, 一旦访问了第i顶点, 便将visited[i]置为1。
根据搜索路径方向的不同, 遍历图的方法可分深度优先搜索遍历和广度优先搜索遍历, 又根据编制算法的方法不同, 可分为递归遍历算法和非递归遍历算法, 再考虑到图的邻接矩阵和邻接表两种不同存储结构, 综合起来图的搜索遍历共可分为八种。
下面以图1为例, 分别介绍图的各种优先遍历方法。
1 深度优先搜索遍历
假定给定图G的初态是所有顶点均未访问过, 在G中任选一顶点i作为遍历的起始点, 则深度优先搜索遍历基本思想是:
首先访问起始顶点i, 并将其访问标记置为已访问过, 即visited[i]=1;然后依次从顶点i的未被访问的邻接点中选顶点j, 若j未被访问过, 则访问它, 并将顶点j的访问标记置为已访问过, 即visited[j]=1, 再从j开始重复此过程。若j已访问, 再看与顶点i有边相连的其他顶点, 若与i有边相连的顶点都被访问过, 则退回到前一个访问顶点并重复前过程, 直到图中所有顶点都被访问完为止。
以图1中无向图G为例可以得到不同深度优先搜索遍历顶点序列。
例如:0→1→3→7→4→2→5→6
0→1→4→7→3→2→6→5
2 广度优先搜索遍历
假定给定图G的初态是所有顶点未被访问, 在G中任选一顶点i作为遍历的起始点, 则广度优先搜索遍历的基本思想是:
首先访问起始点i, 并将其访问标记置为已访问过, 既visited[i]=1, 接着依次访问顶点i的未被访问过的邻接点w1、w2、……、wt, 然后再依次访问与w1、w2、……、wt相邻接的未被访问过的顶点, 依次类推, 直到图中所有顶点都被访问完为止。
同样以图1中无向图G为例可得出不同的广度优先搜索遍历序列:
例如:0→1→2→3→4→5→6→7
0→2→1→6→5→4→3→7
3 图的存储结构数据类型的定义
为了讨论方便, 下面用C语言来描述
1) 图的邻接矩阵数据类型描述:
#define vexnum maxver
#define edgenum maxedge
typedef struct{int vertex[vexnum];int matvix[vexnum][vexnum];}adjmatrix;
2) 图的邻接表数据类型描述:
typedef struct acrnode{int adjvex;struct acrnode*nextedge;}edgenode;
typedef struct vnode{int data;edgenode*firstedge;}vexnode;
typedef struct{vexnode vx[vexnum];}adjlist;
4 深度优先搜索遍历算法
4.1 用邻接矩阵实现图的深度优先搜索
1) 深度优先搜索遍历递归算法[2]
用上述算法和图 (b) 的存储结构, 可以描述从顶点0出发的深度优先搜索遍历顶点序列为:
0→1→3→7→4→2→5→6
2) 深度优先搜索遍历非递归算法[1]
用此算法得出的深度优先搜索遍历序列为:0→2→6→5→1→4→7→3
4.2 用邻接表实现图的深度优先搜索[2]
1) 深度优先搜索遍历递归算法[2,3]
用上述算法和图 (c) 的存储结构, 可以描述从顶点0出发搜索遍历的顶点序列为:
2) 深度优先搜索遍历非递归算法[1]
5 广度优先搜索遍历算法
5.1 用邻接矩阵实现图的广度优先搜索
1) 广度优先搜索遍历递归算法[2,3]
2) 广度优先搜索遍历非递归算法和深度优先搜索遍历非递归算法相似, 不同之处在于前者用栈存储数据, 后者用队列储数据。
5.2 用邻接表实现图的广度优先搜索
1) 广度优先搜索遍历递归算法
2) 广度优先搜索遍历非递归算法[1][3]
参考文献
[1]杨枨.数据结构[M].高等教育出版社, 2002.
[2]严蔚敏, 吴伟民.数据结构[M].清华大学出版社, 1997.
基于数据结构的算法优化 篇9
“数据结构+算法=程序”,说明程序设计的实质就是对确定的问题选择一种合适的数据结构,加上设计一种好的算法。由此可见,数据结构在程序设计中有着十分重要的地位。
一个高效的程序不仅需要编程小技巧,更需要合理的数据组织和清晰高效的算法。算法复杂性的高低体现在运行该算法所需要的计算机资源的多少上,所需要的资源越多,该算法的复杂性越高,反之就越低。针对同一问题,可能会有不同的算法,不同的算法会有不同的复杂性,所以,针对一个算法的优化就显得非常重要。
2 带权区间最短路问题
最短路径问题是网络分析中的基本问题,传统的Dijkstra最短路径算法把网络抽象为有向或无向图,并使用邻接矩阵或邻接表作为网络拓扑信息数据的存储格式。而在实际应用中,绝大多数网络为稀疏网络,以邻接矩阵作为这些网络的数据存储结构会产生大量的冗余,需要占用较多的存储空间。邻接表结构采用链表方式存储网络的结构数据,由于其每个结点只存储与它相邻的结点数据,减少了存储空间的浪费。然而,邻接表不能直观地判断网络两结点间的相邻关系以及结点的入度等,给最短路径算法的实现带来难度。
带权区间最短路问题具体表述是:设S是直线上n个带权区间的集合,从区间到区间的一条路是S的一个区间序列J(1),J(2),…,J(k)。其中,J(1)=I,J(k)=J,且对所有1<=i<=k-1,J(i)与J(i+1)相交。这条路的长度定义为路上各区间权之和。在所有从I到J的路中,路长最短的路称为从I到J的最短路,带权区间图的单源最短路问题要求计算从S中一个特点的源区间到S中所有其他区间之间的最短路。
3 算法设计思想
根据上面的讨论可设计带权区间图的最短路径算法如下:
上述算法的关键是有效地实现步骤2中的(2.1)和(2.2)。
4 实现方案
4.1 采用平衡搜索树
为方便理解,这里先介绍二叉平衡搜索树。二叉平衡搜索树或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉排序树。
下面是具体的实现:用一颗平衡搜索树(2-3树)存储当前区间集S(i)中的有效区间。以区间的右端点的值为序。
算法shortest Interval Paths步骤2中的(2.1)的实现对应于平衡搜索树从根到叶的一条路径上的搜索,在最坏情况下需要O(logn)时间。算法shortest Interval Paths步骤2中的(2.2)的实现对应于反复检查并删除平衡搜索树种最右叶结点的前驱结点。在最坏的情况下,每删除一个节点需要O(logn)的时间。
综上所述,算法shortest Interval Paths用平衡搜索树的实现方案,在最坏的情况下的计算时间复杂性为O(nlogn)。
4.2 采用并查集结构
在一些有N个元素的集合应用问题中,通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。针对看似并不复杂但数据量极大的应用来讲,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,所以可以采用一种全新的抽象的特殊数据结构———并查集来描述。
并查集(union-find sets)是一种简单的用途广泛的、若干个不相交的集合,能够实现较快的合并和判断元素所在集合的操作,在数据结构的搜索及索引方法中应用较多,特别是在等价类的算法处理中的应用尤显重要。一般采取树形结构来存储并查集,并利用一个rank数组来存储集合的深度下界,在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集,空间复杂度为O(N),建立一个集合的时间复杂度为O(1),N次合并M查找的时间复杂度为O(M Alpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是线性的。它支持以下3种操作:
Union(Root1,Root2)即并操作,把子集合Root2并入集合Root1中,要求Root1和Root2互不相交,否则不执行操作。通常来说,合并之前,应先判断两个元素是否属于同一集合,这可用下面的“查找”操作实现。
Find(x)即搜索操作,搜索单元素x所在的集合,并返回该集合的名字。
UFSets(s)即构造函数,将并查集中s个元素初始化为s个只有一个单元素的子集合。通常来说,这个步骤在每次使用该数据结构时只需要执行一次,无论何种实现方式,时间复杂度均为O(N)。
对于并查集来说,每个集合用一棵树表示。
采用并查集结构。用整数k表示区间I(k),1<=k<=n。初始时每个元素k构成一个单元素集,即集合k是{k},1<=k<=n。
基于上述并查集原理,基本算法中的步骤2可实现如下:
5 结语
随着计算机的广泛应用,计算机能够处理的问题越来越复杂,数据也越来越丰富。要设计出解决某一问题的程序,首先要解决的是建立合适的数据结构,合理地组织和表示数据,然后设计出实现数据处理程序运行的高效率算法,最后编写出求解问题的程序。算法设计是程序设计的灵魂,对于同一个问题,可以设计出解决该问题的不同的算法,每种算法各有特点。但是在高效的程序要求中,针对有限的资源,必须对特定的数据结构采取算法优化。
摘要：通过对问题的分析,选用合适的数据结构,可将算法的计算时间减至O(na(n)),数据结构的优化直接导致算法的优化。
关键词：数据结构,算法优化,并查集
参考文献
[1]王晓东.算法设计与分析[M].清华大学出版社,2007.
[2]王继东,陈桂林.基于半边数据结构的最短路径算法及其实现[J].计算机工程与应用,2009,45(8):118-120.
结构算法 篇10
《数据结构》课程是计算机类、信息管理类、电子商务、经济类及相关专业的一门重要的专业基础课程。早在1968年, 美国一些学校的计算机系就开设《数据结构》课程。20世纪70年代中后期, 我国也开设《数据结构》课程作为计算机专业的核心课程。开设该课程的目的在于让学者了解数据的计算机外部逻辑结构和计算机内部的存储结构以及相关操作, 它为后续的专业课程, 如编译原理、数据库原理、操作系统、系统分析与设计等课程提供必要的知识和技能准备。本人认为数据结构学习中的难点包括递归程序的阅读、非线性结构中图和树的相关算法, 尤其是图的最短路径、拓扑排序、关键路径的基本应用, 学习难点在于:图的存储结构、图中顶点的定位、图中各个顶点的访问方法等。本文试图就图的最短路径算法的学习过程进行探讨。在学习中, 我们发现:在图形结构中, 节点之间的关系可以是任意的, 图中任意两个元素之间都有可能相邻, 如果对图进行操作或者遍历的话, 必须先确定图中第一个访问的顶点, 才能对其他顶点进行访问 (操作) , 因此, 图是一种比线性表和树更为复杂的非线性数据结构。图之所以仍然作为《数据结构》课程的重要内容出现, 是因为图的存储结构容易定义和掌握, 但是需要通过图的形式化定义及其相关操作来实现具体问题的求解, 这就是我们所说的在《数据结构》的图中需要掌握的重要知识点。图的运算已经成为人们解决实际问题的重要工具, 比如通过Prim算法或Kruskal算法求最小生成树以构造最低价的通信网;通过关键路径求解确定一个工程中的“关键工程”;通过Dijkstra算法求某个源点到其余各个顶点的最短路径, 解决物流配送的最短路径选择;通过Floyd算法计算每一对顶点之间的最短路径, 用于确定设施的选址。本文重点讨论Floyd算法在医院选址问题中的应用。
医院是社会的重要基础设施, 医院建设的选址必须本着以人为本、服务社会、经济效益的原则, 如何使群众就医路径较短, 是医院选址需要充分考虑的问题, 本文以患者就医路径最短为切入点, 选址问题转化为数据结构图论中的求解最短路径的问题, 并采用Floyd算法对最短路径问题进行求解, 为医院的选址问题提供定量分析。
二、Floyd算法基础概念
1.图:顶点和连线的集合, G= (V, VR) , 其中V是图中顶点的有穷非空集合, VR是两个顶点的关系的集合, 即图中连线的集合。若VR中顶点对<v, w>是有序的, 则为有向图, 否则为无向图。
2.连通图:在无向图或者有向图G= (V, VR) 中, 若任意两个顶点v, w都能找到一条路径连接v和w, G即为连通图。
3.网:带权值的图称为网。
4.邻接矩阵:表示顶点之间连接关系的矩阵。网的邻接矩阵定义如下:
三、Floyd算法基本思想
最短路径问题是数据结构图论中的一个典型问题, 这里的最短路径, 不仅仅指的是距离的长短, 还可以引申为经济费用、时间等广义上的最短。在数据结构中求解网络中任意两个顶点之间的最短路径的典型算法是Floyd算法。
Floyd算法的基本思想是:从带权邻接矩阵出发, 若 (vi, vj) 存在, 则存在路径长度D[i][j], 但该路径不一定是最短路径, 需要进行n次试探。如果存在一个k, 且D[i][k]+D[k][j]<D[i][j], 则将vk插入到vi到vj的路径中, 得到新的矩阵D1, 经过n次循环迭代, 比较过所有顶点作为任意两个顶点之间的中间点的路径, 得到最后的最短距离矩阵Dn。
四、实例应用
(一) 医院选址问题建模
现假设给定n个村庄之间的交通图, 现在要从这n个村庄中选择一个村庄建一所医院, 要求离医院最远的村庄到医院的路程最短。
上述问题中, 可将地理信息中的交通网络抽象为数学模型, 以顶点表示村庄, 以连线表示村庄之间的道路, 因此交通图转化为由有限顶点和有限条边组成的无向图, 图中顶点之间的关系由权值表示, 定义权矩阵为前述网的带权邻接矩阵, wij的值为村庄之间的道路距离。这样医院选址问题就转化为在全部顶点之间最短距离的最大值中寻找最小值的问题, 按照Floyd算法进行运算。
(二) 医院选址算法示例
1.假设有6个村庄, 村庄v0、v1之间道路距离为12, v0、v2为3, v0、v4为9, v0、v5为10, v1、v3为2, v1、v4为6, v2、v3为2, v2、v5为6, v3、v4为4, v3、v5为7, v4、v5为4。将6个村庄作为顶点, 有直接道路的村庄之间连线, 顶点之间的边所对应的权值为村庄之间的道路距离。
2.按照上文的算法, 建立带权邻接矩阵D0。
3.第一次迭代, 插入v0后计算最短路径, 即两点之间可以有一个中间点的最短路径, D1[i][j]=min{D0[i][j], D0[i]+D0[j]}。
4.第二次迭代, 插入v1, D2[i][j]=min{D1[i][j], D1[i]+D1[j]}, 在D1的基础上构建D2。
5.第三次迭代, 插入v2, D3[i][j]=min{D2[i][j], D2[i]+D2[j]}, 在D2的基础上构建D3。
6.第四次迭代, 插入v3, D4[i][j]=min{D3[i][j], D3[i]+D3[j]}, 在D3的基础上构建D4。
7.第五次迭代, 插入v4, D5[i][j]=min{D4[i][j], D4[i]+D4[j]}, 在D4的基础上构建D5。
8.第六次迭代, 插入v5, D6[i][j]=min{D5[i][j], D5[i]+D5[j]}, 在D5的基础上构建D6, D6就是最后求得的最短距离矩阵。
9.以各个顶点为源点的最短距离的最大值maxdis={9, 9, 6, 7, 9, 9}, min{maxdis[i]}=6, 对应顶点为v2, 因此本例的最终医院选址为v2村庄。
(三) 选址算法的C语言实现
1. 图的邻接矩阵存储结构表示。
2. 主要算法。
五、结论
实际应用中, 医院选址问题需要考虑众多因素, 可以设置权值为各项耗费总值。本文运用Floyd算法将医院选址问题进行了量化, 并采用C语言实现, 在实际的设施合理选择中, 具有一定的理论意义和实用价值。除了选址问题, 物流配送的路线选择、旅游中最短路线的设计等问题都可以通过建立数学模型进行算法设计。在数据结构的学习过程中, 我们更需要学会的是如何将实际问题抽象为合理的数学模型, 然后设计一个解决该模型的算法, 最后进行编程、测试得到最终解答。
摘要：本文阐述了数据结构中Floyd最短路径算法的原理, 实例讨论了使离医院最远的村庄到医院的路程最短的医院选址问题, 将地理信息抽象为数据结构中的图, 采用Floyd算法, 描述了医院选址问题的算法及其具体实现步骤, 最后通过C语言实现邻接矩阵的存储结构和主要算法。
关键词：数据结构,Floyd最短路径算法,医院选址,C语言
参考文献
[1]陈燕, 曹妍, 贾红雨.数据结构 (C语言版) [M].北京:科学出版社, 2014.
[2]王军, 王伟, 公长春.基于多因素评价法下的社区医院投资研究[J].中国全科医学, 2010, 13 (10A) :3143-3144.
[3]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 2009.
[4]王晓东.算法设计与分析[M].北京:清华大学出版社, 2011.
结构算法 篇11
关键词：非计算机专业；数据结构；Flash动画
中国分类号：G218.7
0引言
由于专业需求，一些理工类非计算机专业也相继开设数据结构课程，在我国，数据结构已成为理工科非计算机专业必修的信息技术基础课程之一[1]，学习数据结构是要让学生掌握数据在计算机中的表示、组织和相应结构上的算法设计，以便学生在软件开发的过程中能选择适当的逻辑结构、存储结构，高效的设计算法，并初步掌握算法的时间和空间分析技术[2]。
然而由于课程内容繁多、理论抽象、逻辑性强、难以理解，很多算法没有源程序实现，因此，存在学生上课听不懂、上机实践动手能力差、课程难教难学的现象。本文从非计算机专业的视角切入，探讨数据结构教学的一些实践策略以及创新思维，为非计算机专业的数据结构教学提供一些有参考价值的建议。
1非计算机专业学生学习数据结构的现状
1.1学生学习基础薄弱，知识衔接不畅
程序设计基础是数据结构的先导课程之一，非计算机专业的学生一般在学习本课程之前，已经学习过C语言程序设计知识，学生对此课程的掌握程度直接关系到数据结构课程的教学效果。
1.2课时不足
数据结构通常只作为非计算机专业学生的选修课，一般只设置18个学时，因此无论是理论授课还是实验课时都相对不足。
1.3教学内容理论性较强，实用性难以充分体现
数据结构对于习惯了学习“所见即所得”的计算机知识（如Flash制作、网页设计等）的非计算机专业学生来说，还是比较困难的。一来教材虽然是C语言版的，但其实是往往觉得难以理解，二来有些教材中使用的类C语言又不能够直接上机使用，而且即便是写出相应的C程序，其运行结果也没有生动的界面来得好看和直接，学生对课程的实用性，心存疑惑。
2引入算法动画，改善课堂教学效果
2.1利用Flash软件，制作算法动画
数据结构课程内容多，大部分都很抽象，用传统的方法来讲解该课程非常枯燥，为了改善这种状况，可以借助现代教学手段，除了把教学内容做成多媒体课件外，还可以把适合动画演示的内容，通过Flash技术直观地展示出来。
HANOI问题是程序设计中的经典递归问题，掌握算法的执行过程，对深入理解和灵活运用递归有重要意义。该算法用高级语言描述只有几行语句，但由于递归算法中有两次递归调用，程序执行过程复杂。在实际教学中，为了把这个过程讲明白，可以利用Flash设计一个动画，形象地描述运作过程和堆栈的变化状态，从而帮助学生理解递归调用及递归过程，加深其对知识的理解。类似的问题还有很多，如串的模式匹配、二叉树的遍历、图的遍历等都可以借助动画演示来加深理解，改善教学效果。
2.2把握课程主线，紧扣知识要点
数据结构课程内容比较繁杂，但总体来说主要介绍线性结构和非线性结构这两大基本结构类型[3]，线性结构部分包括线性表、栈和队列、串、数组和广义表，非线性结构包括树和图。
在线性结构中，线性表是最基本、最简单的一种结构，属于课程最基础的内容，如果学生掌握了它的存储结构及其基本操作，其他线性结构的教学就会相对容易。因此，在教学过程中加重对线性表部分的讲解十分重要，而利用算法的动画讲解又起到了事半功倍的效果。
非線性结构的典型代表是树和图，主要涉及存储结构、基本操作及其在实际中的应用，在这些存储结构下，树和图的各种操作几乎都是以遍历为基础的，因此以结构的遍历为主线进行展开是合适的。例如，二叉树是树这一部分的重点，因为树和森林的各种操作可以转换为二叉树来实现，而二叉树的各种操作都是以遍历为前提的。因此，掌握了二叉树的遍历，也就掌握了树及森林的遍历，从而达到快速掌握其他操作的目的。
另外，随着数字化校园网络的建设，利用网络教学平台辅助教学对改善教学效果十分有益。借助网络教学平台的发布和交流功能，可以把电子教案、多媒体课件、参考资料、课后习题、章节测试等各种课程资源提供给学生，学生可以在课后慢慢消化课堂上没有消化的知识；网络教学平台的论坛和答疑系统也为学生和老师之间提供了一个交流的平台，学生可以随时向同学或老师提问，任课老师也可以与学生充分交流，及时掌握学生的学习动态，调整教学方法。
3通过实验巩固课内知识
3.1科学设置实验内容
首先，在实验类型上我们把实验项目分为两大类，即验证型和综合型。验证型实验以验证教材介绍的算法为主，实验指导书提供了这些算法的详细案例代码。综合型实验注重相关知识的融合，通过设计合理的实验内容强化知识间的联系，锻炼学生的综合实践能力。
其次，在实验内容的设计和选择上必须兼顾广度、深度和梯度。广度即实验内容应该涵盖课程的所有的知识点；深度即对实验题目进行精心设计，选择一些带有趣味性的现实问题；梯度即有对基础知识进行巩固的较简单问题，也有相对较难的让学生有所提高的隐蔽性问题。
3.2规范实验过程
为了规范实验过程，我们在实验教学过程中要坚持做到有计划、有指导、有报告、有总结，随时掌握学生动态。实验开设前由教师制定详细的实验计划，对每个实验项目确定基本目标和要获得的具体结果；要求学生每次实验必须随堂提交实验报告，教师通过批改实验报告了解学生对相关知识的掌握程度，及时调整教学策略。
4结语
在利用Flash动画算法的教学过程中，在保证理论教学质量的前提下，充分重视实践教学环节，唤醒学生的兴趣，培养其自我性、主动性、抽象的归纳力和理解力，在教学中始终坚持培养学生的思维能力甚于知识本身的理念，以期对学生未来的发展起到有益的作用。
参考文献：
[1]张铭，许卓群，杨冬青，等.数据结构课程的知识体系和教学实践[J].计算机教育，2004（3）：89
[2]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007：1-10
基于遗传算法的土壤结构反演模型 篇12
1 电阻率的测量
测量土壤的电阻率有两种办法, 分别是三极法和四极法[1]。其中三极法是常常应用计算垂直接地棒的电阻公式来反推土壤电阻率的方法, 常用的公式为
式中:a为半径, m;l为长度, m;R为垂直接地极的接地电阻, Ω。上述两个公式分别是根据垂直接地棒的两种计算公式推导而来。
这种方法测量土壤电阻率有一个极大的弊端:在打垂直接地棒时, 土壤的松紧影响它和电棒之间是否紧致, 导致了电棒和土壤之间的接地电阻R的变化。接下来介绍四极法, 这个方法可以消除三级法进行测量时会产生的误差。
F.Wenner在1915年时发明一种新的更加正确的测量土壤电阻率的方法, 他是用布置在同一水平上的4个电极来测量的, 简称为四极法。具体布置方法如图1所示。
在图1中, 4个电极中2、3电极代表电压极, 1、4电极代表电流极, h0代表电极的埋深, a代表极间距。
均匀土壤的计算公式如下[2]:
当埋深h0为零时, 采用式 (1) , 其结果是土壤电阻率的真实值, V23代表电位差, 它是在点电流源I、-I对电压极2、3电极发起的。当埋深不等于零时, 其计算公式如下:
在测得I和V23后, 由式 (2) 即可求出土壤电阻率为
虽然引进的电流线和电压线会造成一定的误差, 但是这样非常有利于实际中操作。因此, 本文为了有利于工程使用和减小误差, 还是把电压极和电流极打在土壤不深处, 并且取a≥10h0, 可以粗略看做h0等于零, 式 (3) 可由式 (1) 代替。
在分层土壤中按照这种方法求出的只是把一个分层土壤看做了一个均匀土壤, 而不再是土壤电阻率的真值, 测量极间距和土壤结构不同对应的视在电阻率也不同, 它与电流的流动范围有关:当电棒之间的距离不大时, 电流极流出的电流绝大部分都是在表层土壤中流动, 得出就是表层土壤电阻率。当电棒之间的距离越来越大, 越来越多的电流流向了深层土壤, 反映出的数据是反映了深层土壤参数, 根据电棒之间距离的变化得到的数据是反映了不同深度土壤的参数。因此, 在实际应用中, 会测量多组电棒距离, 也就是常说的测量深度。
本文测得的一系列数据是土壤的视在电阻率, 对这些数据要用数学方法、磁场理论得到正确的土壤结构。最后根据所推导公式编制计算机程序。
2 视在电阻率的推导
用四极法不同测量深度得到的数据是视在电阻率, 分层土壤中视在电阻率满足下式[3]:
式中, A1 (λ) 和B1 (λ) 与分层土壤参数有关, 因此函数中含有每层土壤的参数。当深度变为零时, 式 (4) 变为[4]
用上述的复镜像法将式 (3) 、式 (4) 进行展开, 这样得到一个比较简单的公式[5]:
式中:ci、di分别为复镜像源的位置和大小;h0为测量电极的埋深;a为极间距。
3 建立视在电阻率的目标函数
为了找到一组正确的土壤结构参数, 实际中要测量m个视在电阻率的数值, 最后总会有一组数据满足下式:
式中:ρci为测量深度ai时用复像法计算的计算值;ρmi为测量深度ai时的测量值。x'为列向量, 其表达式如下:
4 目标函数进行最优化
遗传算法在20世纪80年代中期得到了蓬勃发展[6]。遗传算法的灵感来自于生物进化论, 在自然选择的模式下不断生成和不断的检验。遗传算法是在编码群体进化的基础上, 根据适应度, 使遗传机制和生物进化选择得以实现。在实现过程中, 一一迭代个体位串, 通过随机选择把位串中重要的基因提出来重新组合, 使新一代的群体个体比上一代要优化, 就这样不断的群体优化, 逐渐靠近最优化, 最终实现所要解决的问题[7]。适应度函数的设计、参数编码、遗传操作的设计、控制参数的设计和遗传参数的设定、参数编码称为遗传算法五要素。它是一个最适应环境的个体, 在一代一代不断进化中产生, 得到问题最优解, 但没有显示完全随机搜索的特点, 在整个进化过程中遗传算法的遗传操作是随机的。
遗传算法在天然气管道控制优化应用中, Goldberg提出了遗传算法的工作流程和结构形式, 通常称为标准遗传算法 (standard GA-SGA) 或规范遗传算法 (canonical GA-GA) 。人们通常把问题的特征和领域知识用到GA的应用过程中, 各种特定的GA便由此形成, 这些GA具有全局搜索以及求解不同种类的优化问题的能力[8]。标准的遗传算法的基本流程图以及结构如图2所示。
由图2可知, 遗传算法是要经过多次迭代才能得出结果, 其运行过程的基本内容如下:
1) 选择合适的算法编码策略, 用结构空间来替代参数集合。
2) 定义算法的适应度函数f (x) 。
3) 确定遗传参数如变异的概率Pm、交叉的概率Pc等;确定遗传算法的策略, 通过选择算法参数如群体的变异、交叉、选择方法、群体的大小n来确定算法策略。
4) 采用随机初始化的方法生成群体P。
5) 计算群体串位解码后的个体适应值f (x) 。
6) 根据已选择的策略, 在群体中用将交叉算子、变异、选择等方法进行繁殖产生下一代。
7) 如果群体性能以及已完成迭代次数不满足指标, 返回步骤6) , 就可修改遗传算法策略后再返回步骤6) 。
选取随机变异算子、单点配对交叉算子、赌盘选择算子为遗传算法策略的3个基本算子[9], 用浮点数编码方法作为编码方式[10]基本过程, 如图3所示。
5 计算实例并验证
算例一
对于双层土壤, 表1为一组实际工程中用四极法测的在不同测量深度下的视在电阻率数据。表2为根据本文的反演模型计算出的水平分层土壤的模型, 并与CDEGS的结果进行了对比。算法的遗传参数选取:群体的大小为200, 最大代数为500, 交叉概率为0.7, 变异概率为5%。
算例二
新疆国投哈密电厂一期工程在拟建场地共布置土壤电阻率测试点25个, 测试点均布置在工程钻孔处, 且测试点编号与钻孔编号一致, 主要选择在构架、主厂房、烟囱等主要建筑物地段。
依据《电力工程物探技术规程》 (DL/T5159-2002) , 本次土壤电阻率测定采用了四极电测深法, 测定 (解释) 最大深度为30 m。为了保证解释深度满足规程要求, 四极电测深法各极距的选定:测量极距MN/2为0.5 m;供大极距AB/2为1.5 m、3 m、5 m、7 m、9 m、13 m、20 m、45 m。
哈密电厂实测视在电阻率值1如表3所示。
哈密电厂实测视在电阻率值2如表4所示。
本次土壤电阻率测定使用重庆地质仪器厂生产的DDC-8型电子自动补偿仪。对现场使用的仪器设备, 按规程质量体系文件的要求, 使用前进行了认真的检查, 各项指标均满足测试要求。
根据表3和表4的数据, 用本文理论编制的计算程序计算得到的结果, 如表5所示。在设计该项目时取上层土壤电阻率5125Ω·m, 上层土壤厚度2.5 m, 下层土壤电阻率41Ω·m。
6 结论
1) 土壤分层模型在以往的接地参数计算中近似的看作均匀土壤会导致很大的误差, 因为大接地网, 电流会向深层土壤中流动。
2) 反演模型计算出的水平分层土壤的模型, 与CDEGS的测量结果相符, 验证了本文所建模型的正确性。
参考文献
[1]鲁志伟, 文习山.三角法测量双层土壤接地电阻的误差分析[J].高电压技术, 2002, 28 (7) :15-16.LU Zhiwei, WEN Xishan.Error analysis of grounding resistance of double-layer soil based on triangulation measurement[J].High Voltage Engineering, 2002, 28 (7) :15-16.
[2]鞠勇, 张波, 崔翔, 等.双层土壤中接地网接地电阻补偿测量法的修正曲线[J].电网技术, 2003, 27 (1) :44-46.JU Yong, ZHANG Bo, CUI Xiang, et al.The correction curve of grounding resistance compensation measurement in two-layer soil[J].Power System Technology, 2003, 27 (1) :44-46.
[3]解广润.电力系统接地技术[M].北京:中国电力出版社, 1999:185-205.XIE Guangrun.Power system grounding technology[M].Beijing:Chinese Power Press, 1999:185-205.
[4]TAKEHIKO T.calculation of earth resistivity for a deep-driven rod in a multi-layer earth structure[J], IEEE Transaction on Power Delivery, 1991, 6 (2) :608-614.
[5]张波, 崔翔.复镜像法中的的一种自适应采样方法[J].华北电力大学学报, 2002, 29 (4) :1-4.ZHANG Bo, CUI Xiang.An adaptive method of complex image sampling method[J].Journal of North China Electric Power University, 2002, 29 (4) :1-4.
[6]马永杰, 云文霞.遗传算法研究进展[J].计算机应用研究, 2012, 29 (4) :1210-1206.MA Yongjie, YUN Wen Xia.The progress of study on Genetic Algorithm[J].Application Research of Computers, 2012, 29 (4) :1210-1206.
[7]赵亮, 雎刚, 吕剑虹.一种改进的遗传多目标优化算法及其应用[J].中国电机工程学报, 2008, 28 (2) :96-102.ZHAO Liang, JU Gang, LJianhong.An improved multi-objective optimization with genetic algorithm and its application[J].Proceedings of the CSEE, 2008, 28 (2) :96-102.
[8]杨金明, 吴捷, 钟丹虹.多目标优化问题中一种改进的遗传算法[J].华南理工大学学报 (自然科学版) , 2001, 29 (12) :65-67.YANG Jinming, WU Jie, ZHONG Danhong.Multi-objective optimization of an improved genetic algorithm[J].Journal of South China University of Technology (Natural science edition) , 2001, 29 (12) :65-67.
[9]崔明义.一种基于景观特征的浮点数编码遗传算法的研究[J].计算机应用研究, 2007 (8) :48-51.CUI Mingyi.A study of the application of computer float coded genetic algorithm based on the landscape characteristics[J].Application Research of Computer, 2007 (8) :48-51.