基于粘贴和删除系统的图着色问题分析(英文)

图着色问题是图与组合优化中的一个NP-完全问题．现有算法在求解图着色问题时,计算复杂性随着待解问题规模的增大呈指数增长．粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器．文中将图着色问题和图的坏边数结合起来,将图着色问题转化成搜索最长序列的问题,然后利用粘贴系统和删除系统的并行性,得到了图的色数及其所有色类．与已有求解图着色问题的DNA算法相比,新的算法具有较低的复杂性．     

基于粘贴模型的两类全排问题的DNA算法

基于粘贴模型的巨大并行性,分别给出了线性全排列和圆周全排列问题的粘贴DNA算法;分析了两类问题的DNA算法的不同之处;通过一个实例给出了实验操作步骤,并对生化实验进行了模拟,得出了正确的结果,从而证明了算法的可行性。最后,对算法的操作复杂度进行了分析。     

一类禁位排列问题的粘贴DNA算法

提出了广义的分离操作和广义的多级分离操作的概念,简要说明了二者的区别,并给出了其实现方法。基于粘贴模型的巨大并行性,给出了一类禁位排列问题的粘贴DNA算法,分别使用扩展的分离操作和扩展的多级分离操作实现了该算法。通过一个实例说明了给出的实验操作步骤,并对生化实验进行了模拟,得出了模拟结果,从而证明了该算法的可行性。最后,对算法的操作复杂度进行了分析。     

基于密集神经网络的灰度图像着色算法

针对在灰度图像着色领域中，传统算法信息提取率不高、着色效果不理想的问题，提出了基于密集神经网络的灰度图像着色算法，以实现改善着色效果，让人眼更好地观察图片信息的目的。利用密集神经网络的信息提取高效性，构建并训练了一个端到端的深度学习模型，对图像中的各类信息及特征进行提取。训练网络时与原图像进行对比，以逐渐减小网络输出结果的信息、分类等各类型的损失。训练完成后，只需向网络输入一张灰度图片，即可生成一张颜色饱满、鲜明逼真的彩色图片。实验结果表明，引入密集网络后，可有效改善着色过程中的漏色、细节信息损失、对比度低等问题，所提算法着色效果较基于VGG网络及U-Net、双流网络结构、残差网络（ResNet）等性能优异的先进着色算法而言取得了显著的改进。     

求图着色问题的新算法

图着色问题是NP-难度的问题。基于两种传统的启发式算法，提出了两种新的求解策略，由此给出了求图着色问题的两个新算法。与传统算法相比，其中一个新算法在时间复杂度不变的条件下，解的质量有明显提高；另一个则在时间复杂度稍有增加的前提下，进一步较显著地提高了所得解的质量。     

最大匹配问题的粘贴DNA算法

最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。     

着色Petri网模型检测工具的扩展及其在Web服务组合中的应用

Web服务组合的形式化描述和验证是一个重要的研究问题.为了更好地完成验证工作,提出了扩展着色Petri网的模型检测方法.首先,在着色Petri网原有的基于CTL的局部模型检测算法基础上,给出了获取模型检测证据/反例的算法,并在着色Petri网模型检测工具--CPN Tools--中使用ML(meta language)语言实现了这些算法,然后将扩展后的CPN模型检测工具应用在Web服务组合的验证问题中.该方法不仅可以验证Web服务组合是否存在逻辑错误,还能告诉用户发生错误的原因,为Web服务组合的验证提供了技术上的保障.实验表明对着色Petri网的模型检测工具的扩展是正确、有效的.     

有向图k顶点导出子图的DNA粘贴算法

在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题。DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术。文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法。首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图。仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间。     

模糊着色Petri网及其在工作流建模中的应用

Petri网是当前工作流建模中广泛采用的工具之一，针对工作流过程定义中模糊信息的描述和处理问题，提出模糊着色Petri网的描述方法，并给出基于模糊着色Petri网的推理过程，最后给出一个简单业务流程的基于模糊着色Petri网的工作模型，并对该模型进行了分析。     

粘贴模型在两类特殊问题中的改进算法研究

为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法.对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选.通过具体实例说明了该算法的可行性.     

A NEW APPROACH TO THE VERTEX COLORING PROBLEM

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.     

基于神经网络图着色的阅读器防冲突算法

阅读器冲突问题严重影响了RFID系统的性能,降低了识别率。使用图着色方法将频率或时隙等资源合理分配,可以防止阅读器冲突的发生。但是图着色问题是一个NP难题,利用神经网络良好的非线性逼近能力,提出基于神经网络图着色的阅读器防冲突算法。分析了阅读器冲突类型及解决方法,给出了算法的详细步骤、公式推导和能量函数,并通过计算机仿真验证了算法的有效性。     

路图的Smarandachely全染色算法*

设f是简单图G的一个正常的k-全染色,若G中任意两点的点及其关联边的颜色构成的集合互不包含,则称f为G的k-Smarandachely全染色,这样的k中最小者称为G的Smarandachely全色数。针对路图的Smarandachely全染色问题,提出了一种新算法。算法采用三元组编码方式将问题进行转化,按照给定规则生成三元组队列,并对该队列内部排序进行变换调整。同时,给出两个判断函数,根据函数的值判断是否得到问题的解。实验结果表明,该算法可以有效地解决路图的Smarandachely全染色问题。     

多目标优化的图的邻点可区别均匀V-全染色算法

图的邻点可区别均匀V-全染色（AVDEVTC）是指在满足邻点可区别V-全染色的基础上,还要保证每种颜色的使用次数相差不超过1,把完成AVDEVTC所用的最少颜色称为图的邻点可区别均匀V-全色数（AVDEVTCN）。针对图的AVDEVTC问题,提出了一种基于多目标优化的染色算法。设计了一个总目标函数和四个子目标函数,在染色矩阵上通过每个点的颜色集合的迭代交换操作,使得每个子目标函数都达到最优,进而满足总目标函数的要求,完成染色。经过理论分析和实验对比表明,8个顶点以内的所有简单连通图都存在AVDEVTC,且图的AVDEVTCN介于最大度加1与最大度加2之间。实验结果表明,该染色算法能够在较短的时间内正确地计算出1000个顶点以内的图的AVDEVTCN。     

Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling

This paper investigates the robust graph coloring problem with application to a kind of examination timetabling by using the matrix semi-tensor product, and presents a number of new results and algorithms. First, using the matrix semi-tensor product, the robust graph coloring is expressed into a kind of optimization problem taking in an algebraic form of matrices, based on which an algorithm is designed to find all the most robust coloring schemes for any simple graph. Second, an equivalent problem of robust graph coloring is studied, and a necessary and sufficient condition is proposed, from which a new algorithm to find all the most robust coloring schemes is established. Third, a kind of examination timetabling is discussed by using the obtained results, and a method to design a practicable timetabling scheme is presented. Finally, the effectiveness of the results/algorithms presented in this paper is shown by two illustrative examples.     

基于深层聚合结构网络的灰度图像彩色化方法

当前灰度图像彩色化方法普遍存在边界晕染、细节丢失和着色效果枯燥等问题。针对以上问题,提出了一种基于改进的深层聚合结构网络的灰度图像彩色化方法。将深层聚合结构网络引入图像彩色化领域中,且在传统网络基础上加入长连接,在缓解网络梯度消失问题的同时提升其特征利用率,从而提升算法模型对图像边界和细节的处理能力。另外,模型融合生成对抗网络结构,搭建判别网络,动态评价图片彩色化质量,缓解着色枯燥的问题。实验证明,该方法相比于传统彩色化方法,减轻了着色时边界漏色问题,还原了更多的图像细节,图像颜色更为丰富。     

一种改进的颜色敏感图论着色算法

针对认知无线电频谱分配的公平性问题,提出一种改进的颜色敏感图论着色算法。该算法根据用户频谱效益生成与频谱分配相关的权重,通过该权重对颜色敏感的图论着色算法进行修正,保证频谱分配的公平性。仿真实验结果表明,改进算法网络总效益虽有所下降,但频谱使用的公平性有较大的改善。     

Acyclic orientation graph coloring for software-managed memory allocation

This paper presents a novel compiler algorithm,called acyclic orientation graph coloring(AOG coloring),for managing data objects in software-managed memory allocation.The key insight is that softwaremanaged memory allocation could be solved as an interval coloring problem,or equivalently,an acyclic orientation problem.We generalize graph coloring register allocation to interval coloring memory allocation by maintaining an acyclic orientation to the currently colored subgraph.This is achieved with some well-crafted heuristics,including Aggressive Simplify that does not necessarily preserve colorability and Best-Fit Select that assigns intervals(i.e.,colors)to nodes by possibly adjusting the colors already assigned to other nodes earlier.Our algorithm generalizes and subsumes as a special case the classical graph coloring register allocation algorithm without notably increased complexity:it deals with memory allocation while preserving the elegance and practicality of traditional graph coloring register allocation.We have implemented our algorithm and tested it on Appel’s 27921 interference graphs for scalars(augmented with node weights).Our algorithm outperforms Memory Coloring,the best in the literature,for software-managed memory allocation,on 98.64%graphs,in which,the gaps are more than 20%on 68.31%graphs and worse only on 0.29%graphs.We also tested it on all the 73 DIMACS weighted benchmarks(weighted graphs),AOG Coloring outperforms Memory Coloring on all of the benchmarks,in which,the gaps are more than 20%on 83.56%graphs.     

Fractional Path Coloring in Bounded Degree Trees with Applications

This paper studies the natural linear programming relaxation of the path coloring problem. We prove constructively that finding an optimal fractional path coloring is Fixed Parameter Tractable (FPT), with the degree of the tree as parameter: the fractional coloring of paths in a bounded degree trees can be done in a time which is linear in the size of the tree, quadratic in the load of the set of paths, while exponential in the degree of the tree. We give an algorithm based on the generation of an efficient polynomial size linear program. Our algorithm is able to explore in polynomial time the exponential number of different fractional colorings, thanks to the notion of trace of a coloring that we introduce. We further give an upper bound on the cost of such a coloring in binary trees and extend this algorithm to bounded degree graphs with bounded treewidth. Finally, we also show some relationships between the integral and fractional problems, and derive a 1+5/3e≈1.61—approximation algorithm for the path coloring problem in bounded degree trees, improving on existing results. This classic combinatorial problem finds applications in the minimization of the number of wavelengths in wavelength division multiplexing (wdm) optical networks.     

蚁群算法在考试安排中的应用

蚁群算法是一种新的进化算法，目前的研究表明该算法具有许多优良的性质，它为组合优化等问题提供了新的思路。利用蚁群算法对考试课程安排这一实际问题进行求解。综合了图论中的着色和运筹学中的背包问题。通过实例的解决和分析，说明了该算法的优越性。