共查询到17条相似文献,搜索用时 62 毫秒
1.
用图的着色方法求解考试时间安排问题 总被引:2,自引:0,他引:2
无向图的m着色问题已被证明为NP-难度问题,若已知图由带权值的团所构成,可用m种颜色对该图进行着色.给出了一种能在多项式时间内进行的新算法,可得到一个可接受的方案.此算法改善了求解的时间复杂度,通过一个考试时间安排的实例说明了本算法的可行性、实用性和优越性. 相似文献
2.
考试自动安排系统在高校教务管理中处于重要位置,也是一个难题.提出一种基于关系着色图RCC(Relationship Coloring Chart)的Timetabling算法,探讨了该算法在考试时间安排中的应用,开发了某高校业余大学考试自动安排系统,并解决了较大数量学生补考的复杂安排问题. 相似文献
3.
粒子群优化算法是近年来发展起来的一种元启发式的搜索算法,是目前解决组合优化问题的最有效的算法之一.针对考试时间表问题(ETP),通过基于时间序列的粒子编码方式和新的更新算子,建立ETP问题的粒子群求解模型,并结合简化邻域搜索算法给出了改进策略.仿真实验结果表明所提算法及策略的有效性. 相似文献
4.
针对图着色对顶点划分的本质特征,提出了基于度的种群初始化方法和交集杂交算子;为加快算法的收敛速度,设计了新的贪婪局部搜索算子来改进杂交产生的后代个体。在此基础上,提出了图着色问题的一种新的混合遗传算法,对10个标准算例的仿真结果表明,新混合遗传算法可以获得问题高质量的解,是一种有潜力的算法。 相似文献
5.
求图着色问题的新算法 总被引:4,自引:0,他引:4
图着色问题是NP-难度的问题。基于两种传统的启发式算法,提出了两种新的求解策略,由此给出了求图着色问题的两个新算法。与传统算法相比,其中一个新算法在时间复杂度不变的条件下,解的质量有明显提高;另一个则在时间复杂度稍有增加的前提下,进一步较显著地提高了所得解的质量。 相似文献
6.
7.
针对考试时间安排问题,提出了一种离散化蛙跳求解算法,并结合简化邻域搜索算法给出了两种改进策略。该算法借助蛙跳算法优化机理,采用基于时间序列的编码方式和新的个体产生方法扩展了传统蛙跳算法的求解模型。仿真实验表明了所提算法及策略的有效性。 相似文献
8.
基因学习算法解图的着色问题 总被引:1,自引:0,他引:1
本文在PBIL算法及自私基因算法的基础上,提出一个适应性更广、搜索能力更强的优化搜索算法:基因学习算法。该算法从各基因位的初始等位基因概率出发,通过一系列的概率采样、群体选择与局部搜索、概率学习等操作,逐步缩小概率搜索空间,直至收敛。本文将该算法用于求解图的着色问题,取得了非常好的结果 相似文献
9.
在构造了一种新型的“类发夹”式探针的基础上,给出了图的顶点着色问题的一种DNA算法。利用顶点的适当编码,该算法直接生成可满足解空间,无须在全体解空间中进行各种过滤过程,使用常规的生物操作完成可满足解空间的产生及最终解的分离。 相似文献
10.
Grover量子搜索算法是针对非结构化搜索问题设计的著名量子算法,可用于解决图着色、最短路径排序等问题,也可以有效破译密码系统。图着色问题是最著名的NP-完全问题之一,文中首先将图着色问题转化为数学上的无向图;然后采用布尔表达式将其转换为布尔可满足性问题,介绍了量子线路图解决布尔表达式的步骤原理以及图着色问题向布尔可满足性问题的转换过程;最后在IBMQ云平台上,对三节点的2-着色问题以及4-着色问题进行模拟仿真。实验结果验证了使用Grover算法求解图着色问题的可行性,在搜索空间为8的2-着色问题和搜索空间为64的4-着色问题中,分别以近82%和97%的成功概率搜索到目标项。文中使用Grover算法解决了4-着色问题,拓展了该算法在此问题领域上的实验规模,且改进了现有实验的量子线路,使量子位成本更低,结果的成功率更高,展示了Grover算法在大型搜索问题中显著的加速效果。 相似文献
11.
12.
图着色问题(GCP)是NP完全问题.近年来求解GCP的启发式局部搜索算法引起人们的关注,GSAT是最著名的局部搜索算法之一.许多局部搜索算法引入跳出局部极小的机制来提高搜索效率,权值学习是一种被广泛采用的方式之一.我们从一些权值学习局部搜索算法抽象出一个通用的权值学习算法(SWLA),进一步把SWLA和GSAT相结合提出了最小冲突权值学习算法(MCWLA),算法还应用还原策略和“权值交叉”算子来提高搜索后期的效率.算法在求解一些难解测试范例时显示出较高的效率,能求得GSAT及SWLA无法求得的最优解. 相似文献
13.
本文利用图论模型的转化,改进传统贪心算法,设计了一种新的求解高校排考问题的图算法.改进后的算法可以更好应对在现实学分制环境下,跨年级、跨专业、主辅修等复杂的选课因素.为了解决传统算法中仅靠人工优化来实现的软约束目标,改进后的图算法首先将排考图着色模型,转化为无向赋权图的分团覆盖模型,通过深度优先策略和赋权机制,求解同时满足排考硬约束条件和软约束条件的排考方案.经过数据验证,改进算法的排考效果,在排考效果上优于传统贪心算法,在时间效率上优于人工排考方式.改进后的新算法在近年我校的期末考务工作中发挥了一定作用. 相似文献
14.
15.
16.