首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 140 毫秒
1.
NP难度问题的求解一直是计算机科学技术的一个瓶颈任务。自20世纪70年代以来的研究结果表明,求解NP难度问题不存在既完整严格又不太慢的求解算法。三角形Packing问题是NP难的。给出了泊位的定义,并给出了求解三角形Packing问题的拟物策略。以拟物策略为基础发展出拟物算法。实验结果表明,拟物算法具有较高的完整性。  相似文献   

2.
讨论了任意多边形区域的三角形分解问题,提出了一种扇形扫描方法。该方法沿着多边形轮廓搜索各个可行的目标三角形,逐步将多边形未分解区域缩小,最终完成三角形分解。给出了分解实例。  相似文献   

3.
图像表示是图像处理和模式识别领域里的一个重要研究内容.借助于三角形和矩形布局问题的思想,提出一种三角形和矩形NAM(非对称逆布局的模式表示模型)的二值图像表示方法,同时给出编解码算法的形式化描述,并分析了该算法的总数据量.理论分析和实验结果均表明:与流行的线性四元树表示方法相比,三角形和矩形NAM表示方法能更有效地减少节点数和数据存储空间,是二值图像模式的一种良好的表示方法.  相似文献   

4.
基于三角形移去准则的多面体模型简化方法   总被引:32,自引:2,他引:32  
本文提出了一种新的基于三角形移去准则的多面体模型简化方法,该方法主要由三部分组成:(1)计算与三角形相关的三角形板;(2)根据三角形移去准则判断三角形是否应删除;(3)对删除三角形后遗留的空洞进行局部三角化。本文给出的实例说明了该方法的有效性。  相似文献   

5.
该文针对等腰直角三角形剖分问题给出了皮亚诺分形编码方法及相关性质,通过这些性质可快速查找三角形的顶点和邻接三角形.文章并对这些性质给出了较为严格的证明.  相似文献   

6.
王卓  索勃  潘巍 《计算机应用》2017,37(12):3397-3400
经典GT算法是三角形并行枚举算法的MapReduce实现,然而该算法只能枚举全图的三角形结构,对部分顶点构成的三角形结构无法直接进行枚举。针对此问题,提出一种直接枚举部分顶点构成三角形结构的并行算法。首先,通过分析被选点的分布,给出被选点构成三角形的所有组合集合;然后,通过对该集合的筛选,实现对部分点构成三角形结构的直接枚举;最后,将该算法在Spark系统实现,以实现该算法的高效性和广泛性。在人工生成数据集和真实数据集上与GT算法进行对比实验,实验结果表明,所提改进算法的运行时间只有GT算法运行时间的1/3,在Spark上的运行时间仅是Hadoop上运行时间的1/7。该算法可用于更高效地直接生成图中任意点所构成的三角形数据集。  相似文献   

7.
基于曲面三角形网格模型的凸、凹模数控编程算法   总被引:3,自引:0,他引:3  
该文介绍了曲面数控加工编程方法,提出了基于曲面三角形网格模型的数控编程方法,并在此基础上,给出了基于曲面散乱数据的三角形网格模型的凸、凹模数控编程方法,实现了复杂曲面测量模型的凸、凹模数控加工,实验仿真结果表明,该方法能有效地解决复杂曲面的凸、凹模数控加工问题。  相似文献   

8.
四边形网格间接生成方法   总被引:1,自引:0,他引:1       下载免费PDF全文
研究了基于背景三角网格的四边形网格间接生成算法,并针对三角形合并过程中容易残留三角形的缺陷提出了确定侧边的详细算法,该算法主要是依据背景三角网格中边的位置和前沿边的情形,通过背景三角网格中已存在的边、边交换或边分割确定侧边,以避免在三角形合并过程中残留三角形单元。最后给出实例验证了算法的有效性。  相似文献   

9.
求解单位等边三角形Packing问题的近似算法   总被引:7,自引:0,他引:7  
多边形Packing问题不仅具有重要的理论意义,而且也有广阔的应用前景,由于该问题具有NP难度,且具有连续的性质,一般要事先对多边形的放置方位进行限制,例如不允许多边形旋转,然后再进行优化求得近似解,该文采用一种新的思路对多边形Packing问题的一个特例-单位等边三角形Packing问题进行了研究,提出了零自由度动作和零自由度放置策略的概念,并设计了一个近似求解算法-最小损伤法,复杂性分析和计算结果表明该算法是高效的,以此为基础,可能为多边形Packing问题找到类似的求解算法。  相似文献   

10.
基于位平面分解的三角形NAM图像表示   总被引:1,自引:1,他引:0  
位平面分解是一种能够有效地降低图像的复杂性的方法,而三角形Packing 问题是一类特殊的Packing 问题,在许多领域里得到了广泛的应用,有着巨大理论价值和实际意义.因此,借助于位平面分解和三角形Packing问题的思想,以提高多值图像的表示效率为目标,提出了一种基于位平面分解的的三角形NAM(非对称逆布局模式表示模型)的图像表示方法.给出并实现了基于位平面分解的三角形NAM的图像表示算法,理论分析和实验结果表明:与流行的线性四元树表示方法相比,基于位平面分解的三角形NAM表示方法能更有效地减少数据存储空间,是多值图像模式的一种良好的表示方法.  相似文献   

11.
一种求解划分问题的新算法   总被引:1,自引:0,他引:1  
划分问题是VLSI-CAD设计中的基本问题,针对近似划分问题、划分问题、背包问题,提出了一种行之有效的快速算法,其核心思想是基于拟物思路构造目标函数。  相似文献   

12.
13.
The vertex coloring problem is a well-known classical optimization problem in graph theory in which a color is assigned to each vertex of the graph in such a way that no two adjacent vertices have the same color. The minimum vertex coloring problem is known to be an NP-hard problem in an arbitrary graph, and a host of approximation solutions are available. In this article, a learning automata–based approximation algorithm is proposed to solve the minimum vertex coloring problem. The proposed algorithm iteratively finds the different possible colorings of the graph and compares it at each stage with the best coloring found so far. If the number of distinct colors in the chosen coloring is less than that of the best coloring, the chosen coloring is rewarded; otherwise, it is penalized. Convergence of the proposed algorithm to the optimal solution is proven. The proposed vertex coloring algorithm is compared with the well-known coloring techniques and the results show the superiority of the proposed algorithm over the others both in terms of the color set size and running time of algorithm.  相似文献   

14.
In this work the problem of recovering bioelectrical sources on the cerebral volume, from measurement of the potential generated by these sources on the scalp, is studied. This problem is an ill posed problem, since given a measurement on the scalp, there are different bioelectrical sources that produce this measurement and small variations in the input data can produce significant variations in the source localization. The problem is studied through a boundary value problem, which is obtained using a model that describes the head as a conductive layer medium. This model allows relationships between the characteristics of the bioelectrical activity and the EEG to be established. We find in this work conditions under which the inverse solution is unique and we give an algorithm to find it. In the simple case, when the head is modeled through two concentric circles, we give a regularization strategy.  相似文献   

15.
组合优化问题反问题的研究进展   总被引:1,自引:0,他引:1  
本文重点介绍了组合优化问题反问题的研究进展。具体内容包括:线性规划问题反问题、最短路问题反问题、最小费用流问题反问题和网络容量扩充问题反问题的提出背景、研究成果、应用前景及一些可能的研究方向。  相似文献   

16.
随机约束满足问题是经典的NP完全问题,在理论研究和现实生活中有着广泛应用。研究人员发现随机约束满足问题存在相变现象,近几十年来关于此问题相变的研究成果不断涌现。从随机图着色问题和随机可满足问题2个最经典的随机约束满足问题入手,从算法研究、理论物理和数学证明3个方面综述了随机图着色问题和随机可满足问题的相变研究成果。最后对随机约束满足问题相变的研究趋势进行了展望。  相似文献   

17.
While Problem Frames have become a useful approach for requirements analysis, little research has been made to explore how to derive them from a complex problem context. The purpose of this paper is to propose such an approach. The proposed approach consists of three steps to drive the development of Problem Frames. In the first step, business process models are developed to capture the behavioural view of the problem context. In the second step, object analysis models are used to capture the structural view of the problem context. Together, these two views collectively and adequately capture the early context knowledge. These two types of model will then be used in the third step to construct context diagrams and derive Problem Frames. A complex real‐world problem – equity trading problem – is used to illustrate this approach.  相似文献   

18.
关于图同构复杂性的分析   总被引:1,自引:0,他引:1  
戴琼  邹潇湘  谭建龙 《计算机科学》2006,33(11):219-221
图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。  相似文献   

19.
20.
三机以上同顺序Flow-shop问题(PFSP)是著名的NP完全问题.在充分利用PFSP自身特性的基础上,提出一种可变路径的深度优先搜索算法.该算法在搜索过程中根据需要采用两种不同邻域,在必要时将PFSP转化为一个指派问题,自动变更搜索路径,以避免陷入局部最优解.数值仿真实验表明,该算法对于大规模PFSP能取得良好的计算结果.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号