软件工程论文软件工程论文范文基于《数字矿山》软件中矿体平均品位

软件工程论文下载软件工程论文范文：基于《数字矿山》软件中矿体平均品位自动生成技术的研究和应用摘要：以数字矿山软件GeoView3D平台为依托，通过改进的深度优先搜索算法（M－DFS）来搜索现有克里格插值的品位所在的范围，并用三次多项式曲线拟合计算平均品位，以实现以较快的速度计算出鼠标所在位置的平均品位，提高软件的可视化程度。M－DFS算法通过模拟迷宫的有向图是有向无环图，而且对邻接表的表头节点增设一个数据域的方式降低算法的时间复杂度，提高运算速度。关键词：数字矿山；搜索算法；曲线拟合；矿体品位0引言中国地质大学与紫金矿业集团公司合作开发的数字矿山软件，是一套功能比较完整，适合矿山储量计算、设计的软件。该软件同时拥有我国传统储量计算方法和国际通用的地质统计学储量计算两种计算方式。由于地质统计学是基于克里格法，用三维建模计算，相对更科学、更准确，并能直接使用于矿山设计。现在国内储量计算提倡使用地质统计学方法。这套软件仍处于开发期，本研究结合此项目，在已有的功能上，增加一些比较实用的功能，如点击鼠标计算区域内平均品位。决策者往往需要估算剖面的一块区域的平均品位，大致了解一下这一区域矿体的贫富程度，遗憾的是现在软件并无这一功能。而增加这一功能后无疑会大大方便使用者。本文主要是通过改进的深度优先算D-BFS算法搜索现有克里格插值的品位所在的范围，范围由鼠标所在位置的品位范围确定。平均品位的计算方法用三次多项式曲线拟合计算。本文的研究目的和意义就在于解决面对剖面图无法目测所关注区域的平均品位的问题，增加了这个功能之后，清晰准确的数据一目了解地展现在专家的面前，无疑会对他们的指导工作提供较大方便。1D-BFS算法1.1广度优先搜索算法计算机解决问题的第一步就是根据问题建立相应的数学模型，或者说根据问题的逻辑关系设计一个较为合理的存储结构。把剖面图中的每一个插值位置当成一个节点来处理，那么整个剖面图就会变成一张图，只是在图中要能区分通和阻塞两种情况，只不过在这样一个具体问题中，要走通整个迷宫，所关注的问题是通，所以在图中只要能表示通的情况就可以了，这样还会减少需要处理的顶点的个数。图的入口即为鼠标所在的位置。1.2D-BFS算法中的数据结构为了降低空间复杂度，把图当成一个有向图来处理，利用邻接表来存储这张有向图。本文假设模拟迷宫的有向图是有向无环图，而且对邻接表的表头节点增设一个数据域（outdegre－e），即顶点的出度，用来判断该顶点是否出口。如果一个顶点的出度大于1，则通过该顶点有多条路径，为了避免在这多条路径中循环遍历，为每个节点设立一个访问标志visited，初值为假，当访问后该标志为真。用一堆栈来保存成功路径，如果没有成功路径，最后堆栈为空。以图的入口为开始顶点（如图1中顶点A）进行广度优先遍历该有向图。本文对深度优先搜索算法作了以下改进.。首先，利用访问标志visited来避免对经过同一顶点的多条路径进行重复访问；其次，图中可能存在入度（indegree）大于1的顶点，即存在多条路径进入同一顶点，称这样的顶点为汇点（meetvertex，MV）。为了找到迷宫中所有可行路径，在一个顶点出栈时，要恢复经过该顶点所能到达顶点的访问标志；第三，在图路径中存在绝路顶点（impassevertex，IV），如图1中顶点L，在寻找更多可行路径时，不对绝路顶点及经过绝路顶点的路径进行重复探索，因此在第一次寻找可行路径时要对绝路顶点作绝路顶点标记，结合访问标志visited来实现。所以，在迷宫较复杂、绝路顶点较多时，D-BFS较传统算法会有更好的搜索效率。根据上述修改可得如下M-BFS算法思想：假设堆栈栈顶节点为V，则邻接于V的所有节点位于以V为头节点的单链表中，所以只要在这根单链表中搜索一个未被访问的节点V1，如果V1的出度为0，则V1可能是出口或绝路顶点，否则V1进入堆栈继续访问。如果邻接于V的所有节点都已被访问，则V出栈，恢复邻接于V的非绝路节点的访问标志，如果邻接于V的所有节点都是绝路节点，则V也是绝路节点（如图1中L，邻接于L的两个节点M和N都是绝路节点，则L也是绝路节点），当再寻找其它可行路径时，经过D就不再到L，更不可能到M和N，当迷宫中绝路节点很多时，这会节省大量的搜索时间，应作相应的绝路标志，同时V的访问标志置为（1）以新的栈顶节点继续访问。相应的算法描述D-BFS算法。2加权平均品位值计算2.1加权平均品位计算公式视单工程品位为沿某一直线方向品位指标值的直方图和多形图，设图中的直方图间距分别为Ll，L2，…，Ln。L=Ll+L2+…=Ln（L为取样品位跨度），与其相对应的品位指标值分别为C，q，…，Cn。现按常规的加权平均值计算法计算品位平均值，有：2.2算法分析对有n个顶点的迷宫图，在传统的解法中，所需要的存储空间至少是O（n2）。如果用有向图来表示一个迷宫，而采用邻接表可大大降低空间复杂度，因为邻接表中不会存放障碍节点以及永远不能到达的离散的通路节点。虽然存在一定的结构性的开销，当迷宫很复杂而且规模较大时，邻接表较数组有良好的空间复杂度。由于对DFS算法进行了适当改进，只需调用一次D-BFS算法就能找出迷宫中所有的可行路径，而且在找更多可行路径时，搜索效率较数组有较大改善。另外，当某个顶点被标志为绝路顶点，就不会再从它出发进行搜索，寻找迷宫路径的过程就是查找其邻接点的过程，用邻接表作为其存储结构，搜索邻接点所需时间为O（e），其中e为有向图弧的条数，因此在迷宫规模较大而且很复杂时，绝路顶点可能会很多，这时M-DFS算法会有更好的搜索效果。参考文献：［1］严蔚敏，吴伟民.数据结构（C语言版）［M］.北京：清华大学出版社，2001.［2］李俊英，等.热液金属矿床特高品位问题浅析［J］.山东黄金，1995（1）.［3］廖国勇，王广超.用遗传算法解迷宫问题［J］.华东交通大学学报，2006（2）.［4］王仁铎，胡光道.线性地质统计学［M］.北京：地质出版社，1987.［5］杜德真，吴淑真，马永良.地质统计学方法综述［J］.世界地质，1995（12）.