钻井布局

钻井布局问题D题钻井布局（同B题）勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元。设平面上有n个点Pi，其坐标为(ai,bi),i=1,2,…,n，表示已有的n个井位。新布置的井位是一个正方形网格N的所有结点（所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点）。假定每个格子的边长（井位的纵横间距）都是1单位（比如100米）。整个网格是可以在平面上任意移动的。若一个已知点Pi与某个网格结点Xi的距离不超过给定误差ε（=0.05单位），则认为Pi处的旧井资料可以利用，不必在结点Xi处打新井。为进行辅助决策，勘探部门要求我们研究如下问题：1)假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。在平面上平行移动网格N，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。2)在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。3)如果有n口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。数值例子n=12个点的坐标如下表所示：i123456789101112ai0.501.413.003.373.404.724.725.437.578.388.989.50bi2.003.501.503.515.502.006.244.102.014.503.410.80问题背景勘探部门在某地区找矿,初步勘探时期已零散在若干位置上钻井,取得了地质资料.进入系统勘探时期后,要在一个区域内按纵横等距的网格点来布置井位进行“撒网式”全面钻探,由于钻一口井的费用很高,如果新设计的井位与原有井位重合(或相当接近),便可利用旧井的地质资料,不必打这口新井.因此应该尽量利用旧井,少打新井,以节约钻探费用.问题限定条件设平面上n个点Pi,其坐标为(ai,bi)i=1,2,…,n.表示已有的n个井位.新布置的井位是一个正方形网格的所有结点(所谓正方形网格是指每个格子都是正方形的网格;结点是指纵线和横线的交叉点).假定每个格子的边长(井位的纵横间距)都是1个单位.整个网格是可以在平面上任意移动的.若已知点Pi与某个网格结点的距离不超过给定误差(ε=0.05单位),则认为处的旧井资料可以利用,不必在结点处打新井.问题重述为进行辅助决策,勘探部门要求我们研究如下问题:1)假定网格的横向和纵向是固定的(比如东西向和南北向),并规定两点间的距离为其横向距离(横坐标之差绝对值)及纵向距离(纵坐标之差绝对值)的最大值.在平面上平行移动网格,使可利用的旧井数尽可能大.试提供数值计算方法,并对下面的数值例子用计算机进行计算.2)在欧式距离的误差意义下,考虑网格的横向和纵向不固定(可以旋转)的情形,给出算法及计算结果.3)如果有n口井,给出判定这些井均可利用的条件和算法(可以任意选定一种距离).数值例子：12个点的坐标如下表所示i123456789101112ai0.501.413.003.373.404.724.725.437.578.388.989.50bi2.003.501.503.515.502.006.244.102.014.503.410.80问题一的分析条件假设不需考虑总井数，利用旧井不会导致总井数的增加，只要考虑尽可能多利用旧井网格充分大给出的旧井均在勘探区域内地形对误差无影响，无需考虑地形因素符号约定：[X]取整，等于X的整数部分在没有说明的情况下代表题设误差，即0.05单位Pi第i口旧井(ai,bi)所在的点Pi´第i口旧井平移(m,n)个单位后的点(ai+m,bi+n)(m,nZ)Xi代表Pi附近的网格结点Q一个边长2为的只可平移不可转动的正方形W结点(0,0),(0,1),(1,0),(1,1)所围成的一网格名词解释：网格坐标系以某点为坐标原点，以网格纵横方向为x,y轴方向建立的坐标系，并以题设网格边长为单位长度矢量的M-N分解若矢量A1A2可表示成A1A2=mi+nj,m,n∈Ｚ，i,j为互相垂直的单位向量，则称m,n为A1A2的一组M-N分解距离的近似M-N分解两个点pipj的距离d满足|d-|≤2εm,n∈Ｚ,称m,n为距离d的近似M-N分解网格原点设起始时网格坐标系与题设坐标系重合，称这时的坐标原点为网格原点近似分解三角形如果三个点构成的三角形任意一边满足距离的近似M-N分解，且分出的（mi,ni）满足如下条件=0，=031iim31iin22mn问题一的简化根据题意，网格的方向是固定的,对于任意一点Pi，当网格纵横平移整数个单位时，Pi相对于最近的网格结点的距离是不变的,即当Pi在网格上纵横平移整数个单位至Pi´时，Pi相对同一网格的距离不变,于是，我们把所有的旧井点都纵横平移整数个单元,使他们都落在同一网格单元W中,此时，各点相对于最近网格结点的距离保持不变。问题一的分析在题一的距离意义棋盘距离下，要使尽可能多的网格结点与旧井点的距离不大于ε，等价于让尽可能多的旧井点落在以结点为中心，２ε为边长的正方形内。此时，如果正方形的中心为某种网格的网格结点，则正方形里面的点都可以利用。这样，原问题就转化为用小正方形Q去盖住尽可能多的点。基本步骤:对所有的旧井点进行坐标变换，使它们平移到网格w中，即设原井点坐标（x,y）,则新的坐标为（x’,y’）,其中x’=x-[x]y’=y-[y]特别，对位于离网格边界≤ε的点，映射到［１，１＋ε］处理。对于网格w’中的旧井点，按x,y坐标进行分组，设Ai={(x,y)|x∈[ai,ai+2ε],(x,y)∈{(a1,b1)(a2,b2)…(an,bn)}(i=1,2,…,n)Bi={(x,y)|y∈[bi,bi+2ε],(x,y)∈{(a1,b1)(a2,b2)…(an,bn)}(i=1,2,…,n)令Cij=Ai∩Bj。找到元素最多的Cij，再构造一个正方形来盖住这些点，则此正方形的中心即为达到盖住最多旧井点的结点，把网格原点移到这个结点，此时的网格N即为所求验证程序first.cpp结论：最大可利用四口旧井编号为（４，１０，５，２）此时网格结点为（０．４０，０．５５）分析：实际得到的应是结点所在的区域对应为x∈[0.36,0.41]y∈[0.46,0.55]问题二的分析与求解总体思路：找到一个网格坐标系，使旧井点中能同时与结点(欧氏距离)≤ε的点尽可能多将问题一中的坐标旋转一定角度后得到一个新的坐标后,利用坐标变换公式，可得原来的点在新的坐标系中的坐标.X´=Xcos()-Ysin()Y´=Xsin()+Ycos()考虑到网格是正方形,故转角只需变化/2便可以穷举,故可取为网格纵边与横边与X轴的正向夹角,并满足0/2.除距离的定义变换外,类同于题一的做法，对每一个α都能得到相应可利用的最大点数．至于网格相对于原坐标的位移量,对点的纵横坐标取最大值即可；运行second2.cpp;second3.cpp;结论说明得到六个点（１，６，７，８，９，１１）网格所处的角度应是一个范围（０.７７３，０.７９９）对应每一个角度α，网格的位移量也应是一个范围，类同于题一，故不赘述；所有旧井均可利用的充分条件是：当所有源点旋转角度(0/2)形成一映射区(称为-映射区)后，所有像点必须落在一个半径R的圆内，即=n.并且Dij2。我们称其为误差圆.对于完全利用问题，可用如下判据作优先判断：判据一在-映射区内，若存在两点的距离Dij2，则n口旧井不能同时利用，因为相距Dij2的两点不可能同时在一个误差圆内判据二若-映射区内任意两点距离Dij满足Dij√3，则有=n，即这个n像点能被全部包含在误差圆内，这时n口旧井能全部利用判据三任意连接三个像点成三角形，若成锐角或直角三角形，则其外接圆是能将三个顶点完全包围的最小圆；若成钝角三角形，则以钝角的对变为直径作的圆为能将三个顶点完全包围的所有圆中的最小圆.当最小圆半径R时，则n。这就是说如果存在三个点不能同时在一个误差圆中，这时n口旧井就一定不能同时被利用。说明：判据一和判据三是判定n口旧井不能同时被利用的充分条件，判据二是判定n口旧井能同时被利用的充分条件问题三：n口井都可利用的条件判据证明：判据一和判据三的证明显然给出判据二的证明：做误差圆的内接正三角形ABC，边长为3½。分别以A,B,C为圆心做半径为3½的圆，得到其交集区域E(影阴区域)，由于映射区内任何一点到A,B,C的距离都不超过3½，必落在区域E中．证之．求最小圆的算法——中垂线上的二分逼近法如图，为了在映射区中找到能覆盖全部像点的最小圆域，做包含个n像点的凸m(mn)边形，作其直径PQ的中垂线交多边形于S,T，从PQ与ST的交点O出发，在中垂线上搜索所求圆的圆心，步骤如下：1.取点O为圆心，R=|OP|=|OQ|为半径作圆；2.找出其余m-2个像点到O点的最长距离D。若DR，则使圆心Oi朝Ri增大而Di减小的方向(向外)移至SO的中点，继续步骤3；若DR，则R即为所求最小圆的半径，结束；(下标i代表迭代运算的次数,i=1,2,…)3.找出其余m-2个像点到Oi的最长距离Di，若DiRi(Ri=POi)，则使圆Oi+1心向Ri增大的方向移动，移至Di与其向外方向邻接点的中点处；若DiRi，则使圆心Oi+1向Ri减小的方向(向内)移动，移至Oi与其向内方向邻接点的中点处；若Di=Ri，则Ri即为所求最小圆的半径，结束；4.重复步骤3的工作，直到|Di-Ri|(为任意给定的充分小的正实数)为止，此时Ri即为所求最小圆的半径,若Ri，则能覆盖全部像点，所有像点能全部利用，否则若Ri，不能完全利用边界问题结论：若n口井能被全部利用，则圆Q内一定有n个点，且一个源点在圆Q内只对应一个象点；证明：因n口井可以被全部利用，则有０≤Dij≤２ε，处于边界区的每个源点对应圆Q内一个象点，而任一个源点所对应的两个或三个象点只能有一个在圆Q内．得证；这样,边界问题的考虑不会影响问题的实质,即井点个数及可利用井点的编号不变.充要条件定理：平面上n个点可以被一个半径为的圆域所覆盖，当且仅当如下二条件成立：(i)任意两点距离2;(ii)任意形成锐角三角形的三点的外接圆半径.证明：必要性显然.充分性实质上是证明这样一个对偶命题：包含n个点的圆域半径的最小值等于任意“三点确定的圆域”的半径的最大值，这里，所谓三点确定的圆域是指包含它们的最小圆域，即当三点构成锐角三角形时，它就是外接圆，否则就是一斜边为直径的圆，我们把其中以两点连线为直径的圆给第一类圆，锐角三角形的外接圆成为第二类圆，这些圆的半径最大值r．现在作覆盖n个给定点的最小圆域，设其圆周为C，半径为R。由覆盖性知Rr。由最小性知，C上至少有两个给定点。若恰有两个点，则C为第一类圆，从而Rr，下设C上的给定点为P1,P2,…,Pt(t3).在C上取出包含这t个点的最小圆弧A（见图５）。分如下情形：(a)若A小于半圆，则可以过A的两端点作出半径小于R的圆域包含n个给定点，与C的最小性矛盾(b)若A恰为半圆，则C是以A的两个端点连线为直径的圆，即第一类圆，故Rr.(c)若A大于半圆，则在P1,P2,…,Pt中可找到三点构成锐角三角形，从而C是第二类圆，故Rr综上得到R=r.证毕关于“同时被利用”的思考(i)在坐标轴方向固定的情