分治算法的研究论文

《论算法设计中的分治与增量》，我会写！！

随机增量法较为简单，遵循增量法的一贯思路，即按照随机的顺序依次插入点集中的点，在整个过程中都要 维护并更新一个与当前点集对应的Delaunay三角剖分。考虑插入vi点的情况，由于前面插入所有的点v1,v2,...,vi-1构成的DT(v1, v2,...,vi-1)已经是Delaunay三角剖分，只需要考虑插入vi点后引起的变化，并作调整使得DT(v1,v2,...,vi-1) U vi成为新的Delaunay三角剖分DT(v1,v2,...,vi)。(插入调整过程：首先确定vi落在哪个三角形中（或边上），然后将vi与三角形三个顶点连接起来构成三个三角形（或与共边的两个三角形的对顶点连接起来构 成四个三角形），由于新生成的边以及原来的边可能不是或不再是Delaunay边，故进行边翻转来调整使之都成为Delaunay边，从而得出DT (v1,v2,...,vi)。)其Pseudocode如下：Algorithm IncrementalDelaunay(V)Input: 由n个点组成的二维点集VOutput: Delaunay三角剖分 a appropriate triangle boudingbox to contain V ( such as: we can use triangle abc, a=(0, 3M), b=(-3M,-3M), c=(3M, 0), M=Max({|x1|,|x2|,|x3|,...} U {|y1|,|y2|,|y3|,...})) DT(a,b,c) as triangle i <- 1 to n do (Insert(DT(a,b,c,v1,v2,...,vi-1), vi)) the boundingbox and relative triangle which cotains any vertex of triangle abc from DT(a,b,c,v1,v2,...,vn) and return DT(v1,v2,...,vn).Algorithm Insert(DT(a,b,c,v1,v2,...,vi-1), vi) the triangle vavbvc which contains vi // FindTriangle() (vi located at the interior of vavbvc) 3. then add triangle vavbvi, vbvcvi and vcvavi into DT // UpdateDT() FlipTest(DT, va, vb, vi) FlipTest(DT, vb, vc, vi) FlipTest(DT, vc, va, vi) if (vi located at one edge (. edge vavb) of vavbvc) 5. then add triangle vavivc, vivbvc, vavdvi and vivdvb into DT (here, d is the third vertex of triangle which contains edge vavb) // UpdateDT() FlipTest(DT, va, vd, vi) FlipTest(DT, vc, va, vi) FlipTest(DT, vd, vb, vi) FlipTest(DT, vb, vc, vi) DT(a,b,c,v1,v2,...,vi) Algorithm FlipTest(DT(a,b,c,v1,v2,...,vi), va, vb, vi) the third vertex (vd) of triangle which contains edge vavb // FindThirdVertex()(vi is in circumcircle of abd) // InCircle()3. then remove edge vavb, add new edge vivd into DT // UpdateDT() FlipTest(DT, va, vd, vi) FlipTest(DT, vd, vb, vi)复杂度分析问题的规模为点集中的点的总个数n（没有重合的点），循环内的基本的操作有：1.寻找插入点所在的三角形(FindTriangle())2.测试点是否在外接圆内(InCircle())3.更新三角网(UpdateDT())4.寻找共测试边的第三顶点(FindThirdVertex())考虑最坏情况：时间复杂度T ＝ T(addboudingbox()) + Sum(T(insert(i), i=1,2,...,n)) + T(removeboundingbox)因为addboudingbox()和removeboundingbox不随n变化，是个常量。T(addboudingbox()) = O(1), T(removeboundingbox()) = O(1).T = Sum(T(insert(i), i=1,2,...,n)) + O(1) + O(1). 考虑插入第i个的点的时间: T(insert(i)) = T(FindTriangle(i)) + T(UpdateDT(i)) + K*T(FlipTest(i)) (K为常数)故T = Sum(T(FindTriangle(i)), i=1,2,..,n) + Sum(T(UpdateTD(i)), i=1,2,..,n) + K*Sum(T(FlipTest(i)), i=1,2,..,n)挨个考虑：FindTriangle(i)是要找出包含第i个点的三角形，由欧拉公式知道，平面图的面数F是O(n), n为顶点数，故此时总的三角形数是O(i)的。所以问题相当于在O(i)个记录中查找目标记录，如果不借助特殊的数据结构，按照一般顺序查找，需要O (i)的时间。T(FindTriangle(i)) = O(i),故：Sum(T(FindTriangle(i)), i=1,2,..,n) = O(n*n)UpdateTD(i)是更新三角网数据结构，插入和删除三角形到当前的三角网是个常量操作，因为已经知道插入和删除的位置。T(UpdateDT(i)) = O(1),故：Sum(T(UpdateTD(i)), i=1,2,..,n) = O(n)FlipTest(i)比较复杂些，是个递归过程。细分为：T(FlipTest(i)) = T(FindThirdVertex(i)) + T(InCircle(i)) + T(UpdateDT(i)) + 2*T(FlipTest(j))。(这里，用j来区分不同的深度)因为InCircle(i)是测试点是否在外接圆内，是个常量操作，不随点数变化而变化。故T(InCircle(i)) = O(1), 又T(UpdateDT(i) = O(1)(见上)FindThirdVertex(i)是查找目标点，在O(i)个记录中查找目标记录，如果不借助特殊的数据结构，按照一般顺序查找需要O(i)的时间。T(FindThirdVertex(i)) = O(i).剩下的是递归调用FlipTest的过程，不过还好，因为FlipTest的递归深度只有常数级(设为K)。正比于点在三角网中的度数(degree)。故FlipTest(i)最多调用的次数为2*2*,...,2 = K',还是常数。故T(FlipTest(i)) = O(i) + O(1) + O(1) + K'*(O(i) + O(1) + O(1)) = O(i) + O(1) + O(1) .Sum(T(FlipTest(i)), i=1,2,..,n) = O(n*n) + O(n) + O(n)综上，最坏情况下算法总时间复杂度 T = O(n*n) + O(n) + K*(O(n*n) + O(n) + O(n)) + O(1) + O(1) = O(n*n) 其中，关键的操作是FindTriangle()和FindThirdVertex()，都是n*n次的。在网上很多资料说随机增量法是O(nlogn)的，但是分析下来，却是O(n*n)的。后来看到别人的实 现，原来是用的别的数据结构来存储三角网，减少了FindTriangle()和FindThirdVertex()的复杂度。使得某次查找三角形和共边 三角形的第三顶点能在O(logn)，而非O(n)的时间内实现。这样，总的查找的时间为 O(log1)+O(log2)+,...+O(logn) = O(nlogn)。程序=算法+数据结构，看来一点没错。比如说用DAG，Quad-edge等，都能达到O(nlogn)的复杂度。分治法（Divide and Conquer）据说是现在实际表现最好的。

《论算法设计中的分治与增量》

1、论文论著91年01期 程序变换综述 计算机与现代化 第一作者91年08月 过河算法的演绎推理 91全国理论计算机年会 第一作者论文集并作大会报告91年04期 面向对象系统中的分类 计算机与现代化 第二作者91年04期 二叉树插入删除算法的演绎推理 江西师大学报 第二作者92年01期 多型函数和高阶函数的可重用性 计算机与现代化 第二作者92年04期 函数程序语言SML及其实现 计算机与现代化 第二作者92年04期 C++的虚拟函数与虚拟基类 江西师大学报 第二作者92年04期 过河算法的综合 计算机研究与发展 第一作者93年08月 一类树的遍历算法的演绎综合 中国计算机学会第八届 第一作者年会论文集(摘要)94年增刊 程序设计语言中的可复用机制 计算机与现代化 第二作者95年11期 函数式语言中多态类型的实现技术 计算机研究与发展 独 著96年07期 通用的文本检索工具 电子与计算机 第一作者96年11月 江西省高校计算机等级考试手册 江西高校出版社 第二主编96年02期 环型队列的插入删除算法分析及其改进 江西师大学报 独 著96年03期 面向对象开发中的继承机制和可重用性 计算机与现代化 第一作者96年03期 树算法综述 成人高教理论与实践 独 著97年增刊 面向对象的多态性和异质队列系统的实现 计算机与现代化 独著97年04期 OO设计和对象模型构建技术 计算机与现代化 第一作者97年01期 树遍历算法的演绎综合 计算机工程与科学 独 著97年04期 面向对象软件开发及其可复用性分析 江西师大学报 第二作者97年02期 双机容错热备系统综述 计算机与现代化 第三作者97年增刊 用分枝限界法求解0/1背包问题 计算机与现代化 通讯第一作者98年02期 金山汉字编辑系统加密剖析 江西师大学报 第二作者98年06期 回溯法的并行处理 计算机与现代化 通讯第一作者98年02期 金山汉字编辑系统加密剖析 江西师大学报 第二作者98年12月 数据结构 江西教育出版社 第一作者98年05期 面向对象多态性和通用异质栈的实现 计算机科学 独著98年10月 分治方式的并行处理与高效 98全国理论计算机年会 第一作者并行排序算法 论文集并作大会报告98年05期 江西省高校计算机等级考试研究和实施 江西高教研究 第二作者98年05期 面向对象多态性和通用异质栈的实现 计算机科学 独著99年01期 分治算法的并行处理 江西师大学报 通讯作者99年11期 回路算法的演绎综合 计算机科学 独著00年04期 计算机应用技术基础 华东师大出版社 主编00年02月 计算机软件工 上 地质出版社 副主编00年02月 计算机软件工 中 地质出版社 副主编00年02月 计算机软件工 下 地质出版社 副主编00年08期 一类数组算法的演绎综合 计算机科学 独著00年04期 异构计算机开发最大循环并行性 江西师大学报 第三作者00年增刊 软件工程教学探讨 江西师大学报 通讯作者00年10月 浅谈21世纪计算机基础教育改革 清华大学出版社 通讯作者00年10月 探索教学方式，提高教育质量 清华大学出版社 通讯作者01年02期 汽车备件管理系统的OO分析与建模 计算机科学与工程 第一作者01年07期 信息管理系统的OO分析与建模 计算机科学 第一作者01年07期 证券网与 ES-9000大中型机互连应用 计算机科学 第二作者01年04月 企业进销存管理系统的对象建模与设计 计算机应用研究 第一作者01年10期 DirectShow 中构建过滤器图表技术 计算机应用研究 通讯作者02年01期 利用DirectShow技术实现多媒体流的 计算机应用研究 通讯作者解码和回放02年12期 利用VBA扩展WORD功能的一个实例 计算机应用与软件 通讯作者02年08月 Web企业应用软件的面向对象开发方法 计算机科学 第一作者02年06期 MPEG流封装成RTP协议包的具体实现 微型电脑应用技术 通讯作者02年12月 C语言程序设计 中国铁道出版社 主 审03年03期 汉若塔问题非递归算法的形式推导 计算机科学与工程 通讯作者03年06期 基于MIS的通用编辑界面的关键技术 计算机与现代化 通讯作者及其实现03年01期 VB中高清晰可视化图文打印的实现 江西师大学报 通讯作者03年09月 计算机文化基础 江西高校出版社 主 审04年09月 A High­-efficient Parallel Reasoning Algorithm 第一作者DCABES 2004 Proceadings04年04期 基于MFC的对象序列化机制探讨及其应用 江西师大学报 通讯作者04年05期 一种视频点播系统的研究与实现 江西师大学报 通讯作者04年08月 对印度计算机教育的思考 全国高等学校计算机基础教育研究会 通讯作者会 2004年会论文集 清华大学出版社04年08月 培养创造应用型软件人才的几点建议 全国高等学校计算机基 第二作者础教育研究会 2004年会论文集 清华大学出版社05年05月 A Developing Method of GPS Real-time Data Collection Systemfor Traffic Monitoring and PositioningPROCEEDING 2005 SEMINAR ON engineering Education Cooperation& Academic Research for Chinese-French Universities 第一作者05年05月 Design and Implementation Message and Presence Service Basedon SIPPROCEEDING 2005 SEMINAR ON engineering Education Cooperation& Academic Research for Chinese-French Universities 通讯作者2、课题部分实现理论及其在软件开发中的应用 国家自然科学基金项目 骨干完成OO建模设计及其在软件开发中的应用用 省自然科学基金项目 主持完成面向对象的重用技术及其在软件开发中的应用 省自然科学基金项目 主持完成面向对象的设计及其在软件开中的应用 省科委一级项目 主持完成基于对象的教案设计平台研究开发 省教委重点项目 主持完成国家计算机软件工题库系统 国家劳动部项目 主持完成基于语义的题卷库系统 省教委重点课题 主持完成智能演绎模型开发工具研究 省科委一级项目 主持完成教案编辑方法研究 校重点课题 主持完成可重用性理论及其在软件开发 省自然科学基金项目 骨干完成党外干部管理系统 省科委软课题 主持在研导师制下的项目驱动教学模式研究 省教育厅 主持在研基于webservice的通用教案制作平台设计 江西省分布式计算工程中心 主持在研