用于块体划分的最小回路法及模型试验

Model test and study on minimum circuits for block partition.

(1.中国科学院地质与地球物理研究所，北京100029;2.中国地质大学（北京）地质过程与矿产资源国家重点实验室,北京100083；3.中国地质大学（北京）地下信息探测技术与仪器教育部重点实验室，北京100083；4.沈阳大学，辽宁沈阳110044)

Institute of Geology and Geophysics, Chinese Academy of Sciences, Beijing 100029, China

块体模型在综合利用地球物理、测井、地质信息进行油气储层或其它地质体预测方面起着重要的作用，目前已有的块体建模技术，包括基于Delaunay剖分和多边形填充、种子填充、边填充等，有的实现速度较慢，有的难以适应地质上的复杂情况。为此，对块体建模技术的算法进行了改进，即将断层（包括工区边界）轨迹抽象为无向图，将断块自动剖分和封闭问题转化为最小回路问题。这是一传统的NP问题，为了把算法的时间复杂度降低到计算机可以承受的范围，在传统有向图寻找回路算法的基础上，提出了一种简化的无向图按区域进行深度优先遍历，在遍历的过程中记录走过的路径，从而在遍历的同时找到回路，再在所得的回路中过滤出全部最小回路的算法。以某油田的开发模型数据的断层和地层数据为例对方法进行了实用性检验，结果表明，该方法大大降低了算法的时间复杂度，在单个微机上就可实现块体模型的建立。

The block model is important in the comprehensive utilization of geophysics, logging and geological information to predict reservoirs or other geological objects. The existing block modeling methods, including partition based on Delaunay division, polygon filling, boundary filling, seed filling algorithm, are either slow or inapplicable under complex geological conditions. In order to improve the algorithm, the fault traces( including the working area boundary) were abstracted into an undirected graph; fault block automatic partition and closing problem were converted to a problem of searching the minimum circuits, which is a traditional NP problem. In order to decrease the time complexity of the algorithm to a tolerable degree for the computer, a simplified undirected graph algorithm was proposed based on the traditional algorithm of searching minimum circuits on digraph. The principles of the algorithm are that: first, the depth-first traverse is carried out by area, and, at the same time, the traveling path is recorded, then the circuits are found simultaneously, finally, all the minimum circuits are filtered from the obtained circuits. The fault and formation data of the development model in one oilfield was used to test the practicability of the method, showing that the time complexity of the algorithm was greatly decreased and the block model can be built in a single PC.