共查询到20条相似文献，搜索用时 484 毫秒
1.
This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given. 相似文献
2.
3.
本文主要研究基因无方向的基因组重排的反转排序问题.本文算法基于断点图的概念,给出一个时间复杂性为O(maxb3(π),nb(π)),空间复杂性为O(n)的求解近似最优解的算法,其中n为基因组中基因个数,π=(π1,π2,...πn)表示n个基因的一种排列,b(π)表示排列π中的断点数.数据试验的结果表明,该近似算法可以求得较好的结果. 相似文献
4.
This paper proposes an algorithm for building weighted directed graph, defmes the weighted directed relationship matrix of the graph, and describes algorithm implementation using this matrix. Based on this algorithm, an effective way for building and drawing weighted directed graphs is presented, forming a foundation for visual implementation of the algorithm in the graph theory. 相似文献
5.
用邻矩阵生成加权有向图 总被引：1，自引：0，他引：1
1IntroductionWith rapid development of computer technology,re-search onthe graphtheory has provided a great deal ofadvanced results .However ,one can not find manyre-searches on visual build of graphs based on adjacencymatrix or relationship matrix of the graph , althoughsuch research is useful in the teaching of graph theoryand other practical applications .Take weighted direct-ed graph as an example , only after building a graphusing adjacency or relationship matrix ,can one visual-ly and ef… 相似文献
6.
刘淋 《黄冈师范学院学报》2013,(6):18-21
利用遗传算法实现对图论中无向图的消圈。将无向图转化为二进制的染色体个体,对于出现圈的图,算法巧妙地采用关联矩阵列向量线性相关性进行判断,对含有圈的个体进行惩罚使其进入下一代的概率微小,促使算法能较快的收敛。算法在设计过程中,进行多种遗传机制的测试,在遗传的控制参数上也都适当进行调整,使其达到较为满意的结果。将该算法应用测试后表明,算法能够有效进行消圈,并输出最优解。在交通规划的实际问题中,能很好地体现其优势。 相似文献
7.
8.
9.
高炜 《昆明师范高等专科学校学报》2012,(6):5-9
若删除G中任意一个独立集后得到的图依然是分数（g,f,m）-消去图,则称G为分数ID-（g,f,m）-消去图．将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论：1）阶为n的图G满足n≥12k＋6m-11,6（G）≥n/3＋k＋m,且／NG（x）UG（y）/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-（k,m）-消去图;2）若δ（G）≥（an/2a＋b）＋（b2（i-1）/a＋2m,n〉（（2a＋b）[i（a＋b）＋2m-2]）/a,且/NG（x1）u…uNG（x1）/≥（a＋b）n/2a＋b,对V（G）的所有独立集{x1,……,xi}都成立．则G是分数ID-（g,f,m）-消去图． 相似文献
10.
本文详细介绍了基于寄存器分配的三种软件水印算法,QP,QPS,QPI。这三种算法都是通过为冲突图添加边的方式在程序中嵌入水印的。根据图染色的寄存器分配理论,我们提出了一种新的软件水印算法一二次染色算法（STC）,此算法并不需要添加任何额外的边,只是通过为图中的部分顶点二次着色方式来嵌入水即的。与前面三种算法比较,STC算法更简洁,更有效。 相似文献
11.
本文定义了图的直接和的概念,讨论了图的直接和中Hamilton圈的存在性。当图本身存在Hamilton圈时,它的直接和中的Hamilton圈也存在;设图G是n阶图,如果它的极大Hamilton子圈与Cn-1同构,那么它的直接和存在Hamilton圈;本文还研究了极大Hamilton子圈同构于Cn-2的n阶图并得到了三个充分条件。本文最后用超立方体Q4为例展示了这些命题的应用。 相似文献
12.
13.
通过对图、完全图和正则图概念的介绍,详细地描述了图嵌入的方法,同时对主成分分析、线性鉴别分析、局部保持投影、保持近邻嵌入、L1图及其嵌入等经典的特征提取算法进行了详细的代数推导,列出了详细的推导过程,得出这些经典算法可以用图嵌入理论来解释的结论,最后得出特征提取算法的核心在于算法的图构造. 相似文献
14.
15.
基于图搜索策略的数独问题算法与实现 总被引：1，自引：0，他引：1
李昊 《通化师范学院学报》2009,30(10):43-45
图搜索策略是解决传统人工智能问题的有效方法．该文使用状态空间表示方法以及图搜索策略,提出了一种有效的解决数独问题（Sudoku）的算法,采用递归和回溯,进一步提高了算法的效率,并结合Excel和VBA给出了算法的具体实现。 相似文献
16.
In this paper we describe a system for visualizing correctness proofs of graph algorithms. The system has been demonstrated for a greedy algorithm, Prim's algorithm for finding a minimum spanning tree of an undirected, weighted graph. We believe that our system is particularly appropriate for greedy algorithms, though much of what we discuss can guide visualization of proofs in other contexts. While an example is not a proof, our system provides concrete examples to illustrate the operation of the algorithm. These examples can be referred to by the user interactively and alternatively with the visualization of the proof where the general case is portrayed abstractly. 相似文献
17.
冯俊文 《天津大学学报(英文版)》2001,7(2):101-108
每个具有非对称权重的有向图均可用一个称为“扩展表”的矩阵或表格来表示 .讨论了扩展表中的“圈”和“生成表”的概念及其基本特性 ,给出了一种寻找有向图最小生成树的表格方法——最小生成表法 .研究了最小生成表算法在最优能力集扩展问题中的应用 ,给出了一个算法的具体示例 ,并分析了有关的需研究的问题和可能的拓展 相似文献
18.
合理有效地管理实验设备有利于提高设备的利用率,现将时间图查询用于实验设备的管理,可以丰富查询的语义,提高设备的查询效率。将设备的使用情况抽象成一个大的时间图,将用户的查询请求转换为一个查询图,利用图匹配技术查询出相关的结果。为实现查询图的匹配,提出了3种相关算法:朴素匹配算法(NM)、基于BFS的点匹配算法(BVM)和拓扑剪枝匹配算法(TPM)。在TPM算法中设计了2种索引:TV-索引和TE-索引,分别用于快速定位节点和边上的关系,并从结构和语义两个角度对匹配过程进行了剪枝。最后,设计了对比实验,通过实验验证了3种算法的性能。 相似文献
19.
介绍了传递闭包的Warshall算法,从矩阵自乘的角度给出了传递闭包Warshall算法的一种证明新思路,针对最短路径的求解问题,给出了一个基于闭包的改进算法,并对算法思想进行了分析,先利用列定向的传递闭包,再利用矩阵自乘求出最短路径矩阵,最后结合无向图连通分支问题,讨论了Warshall算法的应用. 相似文献
20.
图形填充技术是图形处理中重要的技术,其相关算法及效率的研究是本领域的热点问题,讨论几种主要的基于光栅显示器的填充算法,并提出了一种对扫描线填充算法的改进。 相似文献