最小生成树的模型数学公式

龙源期刊网

基于最优最小生成树的三维模型形状优化方法

作者：韩丽 刘书宁 于冰 徐圣斯 唐棣

来源：《计算机应用》2019年第03期 龙源期刊网 龙源期刊网 龙源期刊网

龙源期刊网

龙源期刊网

龙源期刊网

龙源期刊网

摘 要：针对海量、异构、复杂的三维模型高效形状分析需求，提出基于最优最小生成树的三维模型形状优化方法。首先基于三维模型的初始最小生成树（3D-MST）构造模型的结构描述;其次通过拓扑结构与几何形状检测并结合双边滤波与熵权值分布进行局部优化，获得模型的优化MST表示;最终基于优化的Laplacian谱特征，结合薄板样条函数（TPS），实现模型的形状分析与相似性检测。实验结果表明，所提方法不仅有效地保留了模型的形状特征，而且可高效地实现复杂模型的稀疏优化表示，能进一步提高几何处理与形状检索的高效性和增强鲁棒性。

关键词：最小生成树; 体积; 双边滤波; 熵权值; 谱嵌入 龙源期刊网

中图分类号： TP391.41

文献标志码：A

文章编号：1001-9081（2019）03-0858-06

Abstract： For the efficient shape analysis of massive， heterogeneous and complex 3D

models， an optimization method for 3D model shape based on optimal minimum spanning tree was

proposed. Firstly， a model description based on 3D model Minimum Spanning Tree （3D-MST）

was constructed. Secondly， local optimization was realized by topology and geometry detection and

第３３卷　第１期　１２４　２０１７年　１月　农业工程学报　

Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆ　ｔｈｅ　Ｃｈｉｎｅｓｅ　Ｓｏｃｉｅｔｙ　ｏｆ　Ａｇｒｉｃｕｌｔｕｒａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｖｂ１．３３　ＮＯ．１　Ｊａｎ．２Ｏｌ７　

基于最小生成树的渠道系统优化布局模型　

许自昌　

（１．中国地质大学（武汉）资源学院，武汉４３００７４；２．福建省地质测绘院遥感中心，福州３５００１１）　

摘要：针对平原地区农田灌溉渠道优化布局问题，当前普遍采用渠道布局原则进行布局，但其不能取得成　

本最优的布局。通过简化平原地区农田灌溉渠道优化布局问题，该文构建了基于最小生成树的渠道优化布局模　

型。与传统最小生成树模型不同的是该模型涵盖了２级渠道的优化布局问题，而且该模型得到的方案要大于　

等于１棵最小生成树。为了能利用成熟的最小生产树理论的求解方法，该文通过创建虚拟点概念去除渠道优　

化布局模型和传统最小生成树模型的区别，运用凸壳理论讨论求解该模型的４种情况，编写求解该模型的　

ＬＩＮＧＯ程序，然后将基于最小生成树的渠道优化布局模型用于案例，得到了研究区渠道布局方案。该方案的　

工程量是１６　０９５　ｍ　，而采用渠道布局原则得到的渠道布局方案的工程量是１６　９３８．２５　ｍ　。结果表明基于最小　

生成树的渠道优化布局模型能得到成本更少的渠道布局方案，即最大程度地控制土地整治费用。研究为控制　

土地整治项目的费用提供了一条有效途径。　关键词：渠道；优化系统；土地复垦；布局；最小生成树模型；凸壳理论；ＬＩＮＧＯ　

ｄｏｉ：１０．１１９７５￣．ｉｓｓｎ．１００２－６８１９．２０１７．０１．０１７　中图分类号：Ｆ３０１．２４　文献标志码：Ａ　文章编号：１００２～６８１９（２０１７）一０１—０１２４—０７　

许自昌．基于最小生成树的渠道系统优化布局模型［Ｊ］．农业工程学报，２０１７，３３（１）：１２４—１３０．　

ｄｏｉ：１０．１１９７５￣．ｉｓｓｎ．１００２—６８１９．２０１７．０１．０１７　ｈｔｔｐ：／／ｗｗｗ．ｔｃｓａｅ．ｏｒｇ　Ｘｕ　Ｚｉｃｈａｎｇ．Ｏｐｔｉｍａｌ　ｍｏｄｅｌ　ｏｆ　ｃｈａｎｎｅｌ　ｌａｙｏｕｔ　ｂａｓｅｄ　ｏｎ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅｓ［Ｊ］．Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆ　ｔｈｅ　Ｃｈｉｎｅｓｅ　Ｓｏｃｉｅｔｙ　ｏｆ　Ａｇｒｉｃｕｌｔｕｒａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ（Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｆｔｈｅ　ＣＳＡＥ），２０１７，３３（１）：ｌ２４—１３０．（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）　ｄｏｉ：１０．１１９７５，ｉ＿ｉｓｓｎ．１００２—６８１９．２０１７．０１．０１７　ｈｔｔｐ：／／ｗｗｗ．ｔｃｓａｅ．ｏｒｇ　

第３２卷第ｌ２期　

２０１０年１２月　电子与信息学报　

Ｊｏｕｒｎａｌ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃｓ＆Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ｖｏ１．３２ＮＯ．１２　

Ｄｅｃ．２０１０　

基于高维空间最小生成树自适应覆盖模型的可拒绝分类算法　

胡正平　许成谦　贾千文　

（燕山大学信息科学与工程学院秦皇岛０６６００４）　

摘要：在高维窄问样本较少的情况下，基于统计模型的可拒绝分类方法难以对样本分布的复杂几何形体构建合理　

的覆盖模型。为此，该文提出基于高维空间最小生成树自适应覆盖模型的可拒绝分类模型。该模型采用最小生成树　刻画高维空间样本点分布，将图形的边作为新增虚拟样本以提供更好的同类样本分布描述。通过将同类相近样本划　

分到一个连通几何覆盖区域内，将不同类的相近样本归于不同几何覆盖区域内，实现对不『￣ｔ）ｌｌ练类的覆盖。为了克　

服因不合理虚拟样本造成分类器拒识性能的下降，引入自适应调整覆盖半径策略，实现对训练类的紧致性覆盖。对　

于测试样本，根据训练类覆盖边界便可对其作出拒识或者接受的处理，针对交叉覆盖的接受样本，再根据数据场策　

略确定其真正归属类别。实验结果表明本文方法合理有效。　

关键词：信号处理；可拒绝分类模型；高维　问；最小生成树；自适应覆盖　

中图分类号：ＴＰ３９１．４　文献标识码：　Ａ　文章编号：１００９～５８９６（２０１０）１２—２８９５—０６　

ＤＯＩ：１０．３７２４／ＳＰ．Ｊ．１１４６．２００９．０００２１　

Ａ　Ｃｌａｓｓｉｆｉｃａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　Ｒｅｊｅｃｔ　Ｏｐｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ａｄａｐｔｉｖｅ　

Ｍｉｎｉｍｕｍ　Ｓｐａｎｎｉｎｇ　Ｔｒｅｅ　Ｃｏｖｅｒｉｎｇ　Ｍｏｄｅｌ　ｉｎ　Ｈｉｇｈ－ｄｉｍｅｎｓｉｏｎａｌ　Ｓｐａｃｅ　

Ｈｕ　Ｚｈｅｎｇ－ｐｉｎｇ　Ｘｕ　Ｃｈｅｎｇ－ｑｉａｎ　Ｊｉａ　Ｑｉａｎ—ｗｅｌｌ　

（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙａｎｓｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｑｉｎｈｕａｎｇｄａｏ　０６６００４，Ｃｈｉｎａ）　

NOIP提⾼组CSP-S复赛需掌握的算法

1、排序算法（快排、选择、冒泡、堆排序、⼆叉排序树、桶排序）

2、DFS/BFS 也就是搜索算法，剪枝务必要学！ 学宽搜的时候学⼀下哈希表!

3、树

①遍历

②⼆叉树

③⼆叉排序树（查找、⽣成、删除）

④堆（⼆叉堆、左偏树、堆排序）

⑤Trie树4、图（图论建模）

①最⼩⽣成树

②最短路径

③计算图的传递闭包

④连通分量（其中要掌握并查集技术）

强连通分量tarjin⑤拓扑排序、关键路径

⑥哈密尔顿环

⑦欧拉回路（USACO 3.3 题1 Fence）

⑧Bell-man Ford、SPFA（能解决负权回路）（USACO 3.2 题6 Butter）

⑨⼆分图（匈⽛利算法）(USACO 4.2 题2 stall)5、动态规划（背包问题只是其中⼀种）

①线性动规

②区间动规

③树形动规

④图形动规6、分治（掌握了动规分治就好学了）

7、贪⼼

8、位运算（可以⽤来进⾏优化）

——————————————————————————————————————————————————————————————————————————————————————

补充：

时间复杂度（渐近时间复杂度的严格定义，NP问题，时间复杂度的分析⽅法，主定理）

排序算法（平⽅排序算法的应⽤，Shell排序，快速排序，归并排序，时间复杂度下界，三种线性时间排序，外部排序）

数论（整除，集合论，关系，素数，进位制，辗转相除，扩展的辗转相除，同余运算，解线性同余⽅程，中国剩余定理）

指针（链表，搜索判重，邻接表，开散列，⼆叉树的表⽰，多叉树的表⽰）

按位运算（and，or，xor，shl，shr，⼀些应⽤）

图论（图论模型的建⽴，平⾯图，欧拉公式与五⾊定理，求强连通分量，求割点和桥，欧拉回路，AOV问题，AOE问题，最⼩⽣成树的三种算法，最短路的三种算法，标号法，差分约束系统，验

证⼆分图，Konig定理，匈⽛利算法，KM算法，稳定婚姻系统，最⼤流算法，最⼩割最⼤流定理，最⼩费⽤最⼤流算法）