最近对问题

来自计算思维百科
跳转至: 导航搜索
最近对问题1.png

如果有两个村庄,每个村庄中都有很多人家,我们想求出最近的两户人家之间的距离,这个问题就是最近对问题。

解决方法

设P1(x1,y1),...,Pn=(xn,yn)是平面上n个点构成的集合S,最近对问题就是找出集合S中距离最近的点对。

方法一

算出各点到所有其它点的距离,找出最小值;

方法二

(1)将集合S分为左右两个小集合S1,S2,我们求出两个小集合中的最近对,距离分别为d1和d2

(2)设d为d1、d2中最小的一个,但是d不一定是集合S中最小距离,因为距离最近的两个点可能分别位于两个小集合S1,S2中,所以我们要在集合S1,S2的分界线左右距离为d的范围内寻找是否存在这样的点对;

(3)在求小集合的最近点对时也采用(1)(2)的步骤进行,直到集合中点的个数足够少。

最近对问题2.png

应用范围

最近对问题在找最短距离上应用广泛。例如大量飞机组成的机群最有可能相碰最应该关注其安全的当然是距离最相近的两架飞机。这就涉及空间中的最近对问题了,但是求解思想不变。

使用方法及步骤

1.如果点数是2,3,则采用蛮力法直接计算。因为2个点直接可计算距离返回,如果是3个点采用分治划分的话,一侧没有或者有1个点,则无法计算,所以在点数是2或者3的时候直接计算出距离或者最小距离;

2.如果点数大于等于4,则将集合分为左右点数相对一致的两个小集合;

3.对每个小集合重复操作1,2直到算出两个集合的最近距离并对比得到当前最小距离d;

4.此时的并不一定是最小的距离,因为最小距离的两个点可能分布在中轴两侧,故需要以中轴点左右各取的长度d,在此两侧范围内的点再采用蛮力计算方法计算出中轴范围内最短距离。

应用案例

应用1-预测金属块断裂的概率

案例:假设在一块金属上钻5 个大小一样的洞,如果洞太近,金属可能会断。若知道任意两个洞的最小距离,可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。

该问题涉及点数较少可以采用方法一,找出所有点对的距离进行比较。

用方法二解决步骤如下:

解决步骤:

(1)将金属块 上5个点分成左边2个,右边3个;

(2)采用方法一分别算出左边2点的距离d1和右边3个点的最短距离d2,比较d1和d2的大小,将最小值记为d;

(3)以分界线为轴,在距离分界线左右两边d的范围内用方法一求出点的最短距离与d比较得到最终结果。

应用2-草坪灌溉系统设计

案例:为了方便对高尔夫球场的草坪进行灌溉,在草坪中安装了400个水龙头。但是整改后草坪面积变小了,有些水龙头距离太近造成水资源的浪费,怎样在该块草坪中找出所有水龙头中距离最近的两个?假设草坪为一块面积为100m*100m的正方形。

解决步骤:

(1)将草坪看成是平面中的一块正方形区域,所有水龙头则为分布在正方形区域中的点,找出距离最近的两个水龙头也即在正方形区域中找出最近点对;

(2)将正方形草坪按中线分成左右两边,先找左边100m*50m矩形草坪中最近的一对水龙头,再找右边100m*50m矩形草坪中最近的一对水龙头;

(3)对左右两边的矩形草坪重复第(2)步,直到草坪面积划分成10m*10m左右的两个正方形草坪(包含3个水龙头左右的面积),分别找出左右两边两个距离最近的水龙头,比较两队的距离大小,假设为3m;

(4)以当前草坪区域中线为轴,在距离中线3m的左右两边区域中找出距离最短的两个水龙头和3m比较,如果小于3m,则当前区域距离最近的两个水龙头就是该对水龙头;

(5)对其他区域也采用第(2)、(3)、(4)步即可找出距离最小的一对水龙头。

可以体现的计算思维

当解决一个数量级特别大的问题时,蛮力法会显得太笨拙,于是便想到将问题划分成同类的小规模问题直到可以求解,然后再一步一步递归求解到最终结果。最近对问题的解决体现了计算思维的递归特点。