文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 第八章 数论算法及计算几何算法
侵权投诉

第八章 数论算法及计算几何算法

242 if(d<tempd) {

tempd=d;

p1=p[i]; p2=p[j]; } }

return tempd; }

3.算法分析

从算法描述可知循环体内的时间是常数时间,循环次数

i 0n 2n 1

n(n 1), ==1(n i 1) 2j i 1i 1

n 1

因此shortest_dis算法的时间复杂性为O(n)。

2

8.6.2最接近点对问题的分治法

显然,最接近点对问题的穷举搜索效率不高,尤其是n很大时效率会更低。为了提高时效,本节将讨论一种应用于该问题的分治算法。

将所给平面上的n个点的集合S分成规模大致相等的两个子集S1和S2。递归求解S1和

S2中的最接近点对。在这里,采用分治法求解的关键在于合并步骤,即由S1和S2中的最接近点对,如何求得S中的最接近点对?很明显,集合S中的最接近点对或者是子问题S1的解,或者是子问题S2的解,或者是一个点在S1中,一个点在S2中的情况组成的最接近点对。S1和S2中的最接近点对可以用递归来求得。但是一个点在S1中,一个点在S2中的情况组成的最接近点对怎么求得呢?

为了讲明白这个问题,先来考虑一维的情形。 1.一维情形 (1)算法思想

令平面上的点的纵坐标全部等于0,S中的n个点退化为X轴上的n个实数 x1,x2,…,xn。最接近点对即为这n个实数中相差最小的两个实数,每个实数对应数轴上的一个点。用xm将x1,x2,…,xn分成两部分S1和S2,这种情况下如何找出S1中的一个点p和S2中的一个点q组成的点对(p,q)呢?令S1中最接近点对的距离为d1,S2中的最接近点对距离为d2,取

d=min{d1,d2}。如果S的最接近点对是(p,q),则|xp-xq|小于等于d。由于p∈S1,q∈S2,所以两者与xm的距离不超过d,即m-d<xp≤m,m<xq≤m+d。

在S1中任何两个点的距离均小于等于d1,同样也小于等于d。因此,在区域(m-d,m]中至多包含S1中的一个点且是S1中最右边的点,即S1中x坐标的最大点。同理,在区域(m,m+d]中至多包含S2中的一个点且是S2中最左边的点,即S2中x坐标的最小点。可见,线性时间就可以找出S1中的p和S2中的q,因此线性时间就可以完成子问题的解合并成原问题解的过程。

(2)算法设计

步骤1:基于平衡子问题的思想,通过S中各点的x坐标的中位数xm将S划分为两个子集S1= ixi xm 和S2= ixi xm ,如图8-4所示。

上一页第18页

热门文档

相关文档

  • 第8章 数论算法及计算几何算法

    第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...

  • 第8章 数论算法及计算几何算法

    第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...

  • 第8章 数论算法及计算几何算法

    第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...

  • 数论和计算几何

    数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...

  • 数论和计算几何

    第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...

  • 离散数论-第八章

    离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...

  • 第二章 贪心法

    第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...

  • 进化算法EA

    [编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...

  • 第8章 几何运算

    三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...

  • 第一章 算法及基础知识

    224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email