没有合适的资源?快使用搜索试试~ 我知道了~
用分治算法解平面最接近点对问题
4星 · 超过85%的资源 需积分: 50 71 下载量 51 浏览量
2008-10-28
22:19:18
上传
评论 4
收藏 236KB DOC 举报
温馨提示
试读
9页
关于最接近点对问题 给定平面上n个点,找出其中一对点,使得在n个点所构成的所有点对中,该点对的距离最小。 这个问题很容易理解,似乎也不难解决: 先求第1个点与其余n-1个点的距离; 再求第2个点与其余n-2个点的距离; 再求第3个点与其余n-3个点的距离; ………………………………………… 再求第n-1个点与其余1个点的距离; 然后找出最小值。但这种算法对于n很大的情况是不合适的。 分治法: 为了使问题易于理解和分析,我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序,然后,用一次线性扫描就可以找出最接近点对。对这种一维的简单情形,我们尝试用分治法来求解,并希望能推广到二维的情形。
资源推荐
资源详情
资源评论
一. 用分治算法解平面最接近点对问题
1.题目
关于最接近点对问题:
给定平面上 n 个点,找出其中一对点,使得在 n 个点所构成的所有点对中,该
点对的距离最小。
2. 程序详细介绍(各模块的功能等)
本程序主要包括两个类:类 Point 和类 Ppoint.其中类 Point 为处理一些的
基本数据传递等.类 Ppoint 为该程序的主要实现模块,该类中有输入点对的函数
shuru,对所输入的点对按 X 轴排序的函数 sort,求各点对的距离的函数 xiao 等.
假设 S 中的点为平面上的点,它们都有 2 个坐标值 x 和 y。为了将平面上
点集 S 线性分割为大小大致相等的 2 个子集 S1 和 S2,我们选取一垂直线 l
(方程:x=m)来作为分割直线。其中 m 为 S 中各点 x 坐标的中位数。由此
将 S 分割为 S1={p∈S|px≤m}和 S2={p∈S|px>m}。从而使 S1 和 S2 分别
位于直线 l 的左侧和右侧,且 S=S1∪S2 。由于 m 是 S 中各点 x 坐标值的中位
数,因此 S1 和 S2 中的点数大致相等。递归地在 S1 和 S2 上解最接近点对问
题,我们分别得到 S1 和 S2 中的最小距离 δ1 和 δ2.此即为该程序的大致算法.
3. 程序结构(流程图)
该程序的流程图如下所示
jiangxin20051986
- 粉丝: 1
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页