匹配限制着色排课模型

在简化的情况下,排课问题可以转化为二分图的边着色问题,但它只解决了教师、班级的排课,未涉及教室问题,离实际应用有很大差距。该文使用扩展的边着色理论,同时考虑教师、班级和教室三者的关系,提出了使用匹配限制着色来解决完整的课表安排问题。     

探索拓扑编码中的图格与传统格的联系

已知不存在解决某些格困难问题的多项式量子算法,无色图格和着色图格是受格理论启发而产生的多学科交叉的产物.拓扑编码中的一个无色图格或着色图格是建立在图的运算和一组顶点不交的连通图或连通着色图构成的图格基上.基于口令认证或数字文件加密,介绍数字串拓扑认证问题,用拓扑编码给出一种非对称加密系统.拓扑编码可以形成一个公钥对应多个私钥,多个公钥对应多个私钥的非对称加密系统;拓扑编码中的拓扑认证需要两个不同领域的数学知识,而且可以产生指数级别的算法.基于图的边连接运算、顶点重合运算等运算,研究了具有优美全着色的着色图格基存在性,建立了边连接图格和F-图格等无穷图格,并证明这些图格对优美全着色具有封闭性.定义了特殊着色图的拓扑向量,建立了图格与非负整数传统格之间的一个联系,为抗量子计算提供可行的技术;说明没有多项式算法解决数字串分解问题,又因为图同构问题是NP-困难,从而拓扑编码建立的图格具有抗超大计算机和量子计算机的计算功能.     

文件时间问题——2003年第5期题解

问题描述见2003年第5期杂志。算法分析通过解读招聘问题我们不难发现它是一道简单的关于有条件的分类或划分问题,解这种问题的方法有很多。在这里我们介绍用图的着色和集合划分来解它。 1.图的着色在本问题中,我们把每一个部门作为顶点,如有应聘者同时应聘几个部门时,在这些部门之间相互连一条边,这样就得到一个图。我们对图的顶点进行着色,同色顶点安排在同一场面试,这样得到的着色数即为需要安排的最少场次。这样招聘     

双层板布线分层与借孔压缩的图论方法

本文提出的先布线、再通过图论方法分层的布线策略可以使线路布得比较均匀,大大压缩借孔数目。文中引入了“色边权”、“色次”等概念,证明了有关最大偶子图的一些引理和最佳着色的充要条件,给出了一个最佳着色算法,并提出解决借孔压缩问题的两个实用方法。     

高校排课问题的图论模型及算法

针对排课系统的缺陷,提出了尊重学生学习规律,按照课程的重要程度和重要课程分配的时间间隔,利用图论的边着色理论,对排课资源进行建模,并给出了有效的多项式时间算法,使得排课问题的解决更加合理与人性化。     

健壮性着色问题的最优解研究

健壮性图着色问题(Robust Graph Coloring Problem-RGCP)是经典图着色问题的一种新的扩展。RGCP则着重针对着色方案的健壮性,使之能处理现实中经常出现的不可预见的突发事件,即需要考虑补边出现的情况。对RGCP在特殊情况下的最优解进行了研究,由此推导与证明了平均颜色定理,以及推广到一般RGCP求解的优化。     

基于轮廓边拟合的软影映射算法

针对实时软影映射算法在绘制大面积光源时绘制效率不高的问题,提出一种基于轮廓边拟合的快速软影映射算法.该算法在场景阴影映射图中的固定尺寸的块内拟合轮廓边直线,并用一种层次化的数据结构来保存拟合的轮廓边直线;再利用反投影轮廓边直线的方法快速地计算着色点的可见性,生成真实的软影效果.实验结果表明,与现有的算法相比,文中算法在不显著降低软影质量的基础上有效地提高了绘制效率.     

基于Grover算法的图着色问题求解

Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法，可用于解决图着色、最短路径排序等问题，也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一，文中首先将图着色问题转化为数学上的无向图；然后采用布尔表达式将其转换为布尔可满足性问题，介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程；最后在IBMQ云平台上，对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性，在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中，分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题，拓展了该算法在此问题领域上的实验规模，且改进了现有实验的量子线路，使量子位成本更低，结果的成功率更高，展示了Grover算法在大型搜索问题中显著的加速效果。     

基于模糊控制的和积算法在图形着色中的应用

采用集中式遗传算法解决图形着色问题存在遗传算子影响群体多样性而使算法本身容易陷入局部收敛等情况,针对该问题,A.Farinelli等提出了利用和积算法解决图形着色问题.然而基于和积算法的着色图的初始冲突教会因图的复杂度或结点规模的加大而大幅增多,从而降低了和积算法效率.为此提出了基于模糊控制的和积算法,利用模糊控制减少着色图中的冲突.实验结果表明,与和积算法及集中式的遗传算法相比该算法在着色效果和算法效率上都有了显著的提高.     

图画着色的设计与实现

以“画图软件”为背景,基于Visual C++和MFC,提出了图画着色功能并予以实现.图画着色功能主要解决图画局部区域的选取以及着色等问题,这样实现的图画着色功能具有良好的可扩展性,适用于其它画图软件的应用.     

基于粘贴模型的图顶点着色问题的DNA算法

为了用生化实验的方法解决图的顶点着色问题,基于粘贴模型的巨大并行性,将着色问题转化为可满足性问题,提出一个基于粘贴模型的DNA算法。通过一个实例给出了操作步骤,并对生化反应过程进行了模拟,得出具体的着色方案,证明了该算法的可行性。     

车载网络的索引编码技术研究

在车载网络中,由于无线信道的脆弱性与车辆的高移动性,广播信息往往不能正确到达和接收。为解决该问题,提出一种基于索引编码的消息广播方案。该方案将索引编码应用于车载网络的信息广播中,可实现更高效的信息分发。给出一种基于分布式反馈机制以收集边信息,使用改进的图着色算法在边信息中寻找最大团,并运用最大团进行索引编码。仿真实验结果表明,该方案可以有效地减少最少传输次数,从而节约无线信道带宽,提高广播效率。     

基于图着色的大规模MIMO系统中动态导频分配

针对大规模多输入多输出（MIMO）系统中存在的导频污染问题,提出一种基于图着色的动态导频分配方案。为了更加合理地分配导频、减小导频污染,首先,利用小区间协作,将不同小区的用户通过带权值的边相连来构建边权值干扰图,以此来描述多小区用户间的导频污染程度;然后,在传统的图着色理论基础上,利用相连用户边权值不同的特点,优先为受导频污染严重的用户分配导频资源。理论分析和仿真结果表明,所提的导频分配方案不同于现有的分布式导频分配方案,在考虑所有小区导频复用的情况下,基于图着色集中式地分配导频,能够减小小区间用户的干扰,提升大规模MIMO系统的上行可达和速率。     

最大流算法发现Web社团的改进

提出了一种更好的分配边容量的方法,即不是给每条边分配一个相同的常量值,而是为不同的边依据信息的重要度来动态分配不同的边值,较好地解决最大流算法发现Web社团中的主题漂移问题。     

最大流算法发现web社团改进

提出了一种更好的分配边容量的方法,即不是给每条边分配一个相同的常量值,而是为不同的边依据信息的重要度来动态的分配不同的边值,较好的解决最大流算法发现web社团中的主题漂移问题。     

基于群论的柏拉图立体着色方案三维模型构造

提出用柏拉图立体的空间旋转群来完成柏拉图立体着色方案三维模型构造的思想,解决与对称性直接相关的着色方案三维模型的构造问题;提出一种柏拉图立体旋转群群元新的分类方法;提出群元抽象对称性、局部色数和饱和色数3个新概念;提出对抽象对象进行抽象着色方案的构造,然后再将抽象着色方案映射到具体的轮换上,最后映射到三维模型空间去的构造方法,设计了实现该方法的算法,并用Visual C++6.0和Direct 3D实现了算法及三维模型可视化.软件运行结果验证了所提出的方法及算法的正确性.     

一种求解图着色问题的蚁群遗传算法

遗传算法在图着色问题上已经得到广泛的应用,但对于顶点数较多的图,使用此类算法进行着色的结果就显得不够理想,运行效率也不够高。由于遗传算法具有全局收敛性,蚁群算法具有局部收敛性,因此,将遗传算法和蚁群搜索算法融合,提出一种新的解决图着色问题的蚁群遗传算法。该算法先利用蚁群算法快速地为遗传算法搜索到较好的初始解,然后利用遗传算法进一步遗传优化,同时在优化解上加强信息素强度,并反馈给蚁群搜索。实验结果表明,改进的算法在解决顶点数较大的图着色问题上有明显的优势。     

图形着色问题的分布式势博弈算法

现有典型的分布式算法在解决大规模图形着色问题时,必须维持节点间的通信连接,在邻接节点增长时效率和可求解规模下降明显。为此,将多代理技术平台下的图像着色问题转换为博弈模型,采用自适应学习算法,逐步优化代理自身状态行为以达到系统的最优状态,即纳什均衡点。实验结果表明,较现有的分布式算法,该算法不但具有更高的求解效率,能够解决更大规模的图形着色问题,而且对邻接节点规模变化的适应能力进一步提高。     

基于访问控制的动态着色技术在攻击检测中的研究

内存腐烂攻击在软件安全攻击中占据着较大的比重。近来,动态着色技术得到了越来越多的关注,这种技术通过在访问内存时检测指针的完整性来抵御攻击。然而,存在一类可以绕过指针完整性检查的策略来进行攻击的实例,比如数组的越界访问攻击。提出了一种基于动态着色跟踪分析的方法来解决这类已有着色技术不能检测的问题。其思想是,借助于内存访问控制的思路,首先像已有的动态着色技术那样,在内存访问时对指针进行完整性检查,然后检查指针将要访问的内存区域是否处于指针合理的访问范围之内。原型系统是基于Valgrind的,并不需要源码,因此可以用于很多商业软件。初步实验验证结果表明,该方法可以有效地检测出很多类型的攻击,系统的性能损耗接近于Memcheck这种常用的内存错误检测工具。     

多层板的最佳分层

本文介绍如何运用最佳二着色原理来解决多层板的最佳分层问题。同时对此算法的复杂性进行了估计。由此引出了准佳二着色的概念,并给出了算法实现流程图和程序实现的实际结果。