Algorithm 版 (精华区)

发信人: lofe ()感激生活(), 信区: Algorithm
标  题: [转载] 99'全国大学生数学建模竞赛试题B
发信站: 哈工大紫丁香 (Sun Sep  3 16:20:16 2000), 转信


B题：钻井布局问题
    勘探部门在某地区找矿。初步勘探时期已经零星地在若干位置钻井，
取得了地质资料。进入系统勘探时期后，要在一个区域内按照纵横等距
的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用
很高，如果新设计的井位与原有的井位重合（或相当接近），便可以利用
旧井的地址资料，不必打这口新井。因此应该尽量利用旧井，少打新井，
以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料为10
万元，则利用一口旧井就节约费用490万元。
    设平面上有n个点Pi，其坐标为(ai,bi),i=1,2,3...n,表示已有的
n个井位。新布局的井位是一个正方形网格N的所有结点，(所谓正方形网
格是指每个格子都是正方形的网格；结点是之纵线和横线的交点)。假定
每个格子的边长（井的纵横间距）都是1单位（如100米）。整个网格是
可以在平面任意移动的。若一个已知点Pi与某个网格结点Xi的距离不超过
给定误差eps=0.05 unit，则认为Pi处的旧井资料可以利用，不必在结点Xi
处大新井。
    为进行辅助决策，勘探部门要求我们研究如下问题：
1)假定网格的横向和纵向是固定的（如东西或南北方向），并规定两点间的
距离为其横向距离及纵向距离的最大值。在平面上平行移动网格N,使可利用
的旧井数尽可能的大。提供数值计算方法，并对下面的数值例子用计算机进
行计算。
2)在欧氏距离的误差意义上，考虑网格的横向和纵向不固定(可以旋转)的情形
，给出算法及计算结果。
3)如果有n口旧井，给出判定这些井均可利用的条件和算法（可任意选定一种
距离）。
数值例子  n=12个点的坐标如下表   略 

--
※ 修改:．haojs 于 Sep  3 16:17:52 修改本文．[FROM: bbs.hit.edu.cn]
※ 来源:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: 202.115.10.213]
--
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: bbs.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: haojs.bbs@bbs.whnet.]
※ 修改:·lofe 於 09月03日16:21:01 修改本文·[FROM: 202.118.226.15]