图节点着色问题中的禁忌搜索算法
09-03-25 作者：编辑：校方人员
图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题。目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。
本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性。禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有效的应用于一些典型NP问题，如TSP。但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。
1图节点着色问题
图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的
给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集，其中(i,j)表示有连接(i,j)的一条边。若，且V i内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…,V n)为V的一个划分。图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,V n)为V的一个划分。
通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。故通常的算法在解决图节点着色问题这样的NP完全问题时，存在很大的瓶颈，难以得到满意的结果。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。
来表示。这样便可用一个行向量来作为解的数据结构，其中下标1,2,…n依次代表各个顶点，向量中下标对应的分量对应所着色，着色相同的即在同一划分集
V i。如例子的解可表示为：s=[2 3 1 3 1 1]，共3种颜色。
2.2领域的选择
首先确定解的变化形式。一般而言，变化形式分为解的简单变化、向量分量的变化和目标值的变化[3]。鉴于解的数据结构，采用分量变化形式，即对于顶点i，其颜色值从s[i]变为j，其中j属于颜色集C。对于领域，每一个解s的领居由那些满足上面的变化且只有一个分量变化的解组成，每一个分量可以选择m个
颜色中的一个，那么对每一个解，共有n*(m-1)个邻居。例如，对于例子中的解
s=[2 3 1 3 1 1]，它的一些领居为s1=[1 3 1 3 1 1],s2=[3 3 1 3 1 1],s3=[2 1 1 3 1
1],s4=[2 2 1 3 1 1]等。解的领域即为所有这些邻居组成的集合。
2.3目标函数的选择和候选集的构造
对于图节点着色问题，目标函数的构造是一个难点。由图论的知识，对一个正常点着色，各个顶点与其相邻的顶点所着颜色不同，即各个顶点同与之有边相连的顶点不在同一个划分集V i中，则：E(V1)+ E(V2)+…+ E(V n)=0，其中E(V i)
表示顶点集V i中包含的边数。那么选取目标函数为：f(s)=E(V1)+ E(V2)+…+ E(V n)，对于那些非正常点着色的不可行解，f(s)>0。在进行禁忌搜索时，每次从领域中
以目标函数值最小为依据来选取解。在禁忌搜索完毕时，给出目标函数值最小的解，若为0则得到一个正常点着色方案，若不为0，我们亦可以得到一个较好的方案，这也是用禁忌搜索来解决着色问题的优点之一。
实际编程中还要设置候选集，以便从中选取下一个最优解。鉴于解的形式和目标函数，可用(n*(m-1))*(n+1)的矩阵来表示，其每行表示解的一个邻居和其
对应的目标函数值。
2.4禁忌表和特赦规则的构造
禁忌表的构造和特赦规则的选取通常是禁忌搜索算法的难点，这也是禁忌搜索算法运用于通信系统中时的一个瓶颈。首先，禁忌对象的选择通常也有三种形式：解的简单变化、分量对换的变化和目标值的变化。由于简单变化的禁忌对象
太少，计算时间过多，而目标值变化的对象过多，难以得到全局最优，故选择分量对换。那么禁忌表设为L*3的矩阵，其第一列储存分量所在下标i，对应图中的某点，第二列储存此点的颜色，即s[i]，第三列储存用来交换的颜色j。对于禁忌表长度，鉴于此参数较难设置，我们用经验式L=sqrt(n*(m-1))，在实际运用时可以通过实验来比较选取该值。对于特赦规则，其设置的好坏直接影响进行全局最优化时的效果。考虑当前解s对应的候选集中的最优解s*，若它被禁而同时它对应的目标函数值满足f(s) 2.5算法终止原则 设置两目标值无改进的最大允许迭代次数k_max和目标值下界fl来保证算法的有穷性。 2.6算法实现的框架 2.6.1主函数的设计 设计好算法后，现在不难给出算法的设计框架。在具体编程时，把一些功能放到外部函数中实现，只在主函数中留出接口。下面是主函数的框架,使用的是MATLAB的伪代码。 初始化：a，m，n为a的维数；%图的邻接矩阵、颜色数、顶点个数 k，best_k，k_max，fl；%迭代步数、最优解所在步、最大允许迭代 数、下界L=n*m^.5取整，h=zeros(L,3)；%禁忌表的设置 s=ones(1,n)，s_best=s，s_now=s，best；%形式、最优解、当前解、最终解 V=zeros(1,n+1)，A=f(s_now)-1；%候选集、特赦值、f为目标函数开始：当f(s_now)>fl且(k-best_k k=k+1；%迭代步数增加 生成s_now的候选集V，其中的元素s是非禁忌或者特赦f(s) 在V中选择使目标函数值最小的解s_best 若f(s_best) 若h未满，将对应的交换加入下一行，否则，覆盖第一行；%更新禁忌表 若f(s_best) s_now=s_best；继续。结束 2.6.2候选集生成函数的设计 初始化：r=1；%候选集矩阵的行下标 循环：i=1:n，j=[1:s_now(i) s_now(i+1):m] temp=s_now，temp(i)=j；%临时变量，储存当前解 change=[i,s_now(i),j]；%对换的变化方式 若禁忌表中没有一行和change相同或者是特赦f(temp)<=A V(r,1:n)=temp，V(r,n+1)=f(temp)；%前n行储存解最后一行储存目标值 r=r+1；end %增加迭代次数，继续 3 图节点着色问题的特例-List着色 对一般着色，每个顶点都可从颜色集C中选取任一个颜色，而当限制了每个顶点专属的颜色集时，称为List着色。如下例： 图论中的定理指出，对任意存在List着色的图，其所需颜色数在区间[ +1]内。对于List着色，针对此问题的算法在各个文献中不多见。通过上面讨论的禁忌搜索算法的设计，我们可以看出，只改变领域的构造规则，便可以简单的实现List着色。具体实现是对每个顶点只选取那些变换，其变换后的颜色仍然存在于自己的颜色集中，而其他所有步骤同一般着色问题。例如，对于例4.1的解s=[1 3 1 2 2](其解的下标依次对应于点x1、x2、x3、y1、y2所着颜色)，其领居选择为s1=[2 3 1 2 2],s2=[1 2 1 2 2],s3=[1 3 3 2 2],s4=[1 3 1 1 2]和s5=[1 3 1 2 3]。由此可见，对禁忌搜索算法扩展，只变换领域的选择就能够较好的实现List着色，当不存在正常的List着色时，算法给出使目标函数值最小的着色方案，这是一般的算法难以媲美的。 表1 仿真实验数据 由此可知，对于n=50、100，平均所需色数为12、20，且实验所得解的目标函数值都为0，说明所得解为可行解。对于概率分析的结果，我们所得解同最优解的偏差在2%以内。 再用其他算法采取同样的随机实验。用回溯法时，对于n=50或100实验在一个小时内都不能得出结果。而采用Welsh-Powell算法时，当n=1000时，平均色数为122，所需时间在10内，但对于概率分析的结果，平均所需色数为85。 5 结束语 实验可看出，回溯法时间复杂性太差，Welsh-Powell算法虽然时间复杂性较好，但得出的结果并非最优，当n较大时尤为明显。而我们设计的禁忌搜索算法解决节点着色问题具有较好的结果最优和较小时间复杂性。 参考文献 [1] 张先迪,李正良.图论及其应用.北京,高等教育出版社,2005 [2] 王红梅.算法设计与分析.北京,清华大学出版社,2006 [3] 邢文训,谢金星.现代优化计算方法(第二版).北京,清华大学出版社,2005 [4] 张晓琴,黄玉清.基于禁忌搜索启发式求解背包问题算法.成都,电子科大学报,Vo1.34,No.3,Jun.2005 [5] 刘于江,喻泽峰.一种求解旅行商问题的禁忌搜索算法.江西理工大学学报,Vol.27,No.4,Aug.2006 [6] 常蓬浩,王晓兰,艾莉等.图节点着色问题的变换及算法.甘肃,甘肃科技,Vol.22,No.l1,Nov.2006 [7] Biggs N. Algebraic Gragh Theory. London. Cambrige University Press, 1993 [8] Hertz A, de Werra D. The tabu search metaheuristic.how we use it. Annals of Mathematics and Artifical Intelligence, 1990 禁忌搜索算法浅析 摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，可以有效地解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。 关键词:禁忌搜索算法；组合优化；近似算法；邻域搜索 1禁忌搜索算法概述 禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。 TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 2禁忌搜索算法的基本思想 禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索，TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解，但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法保证全局优化型。 禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁 算法设计课程设计 题目图着色问题 姓名学号 专业年级 指导教师职称 2014年 12月 4日 图的m着色问题 1 摘要 (3) 2 图的着色问题 (4) 2.1 图的着色问题的来源 (4) 2.2 图的着色问题的描述 (4) 3算法的基本思想 (4) 3.1 求极小覆盖法----布尔代数法 (4) 3.2 穷举法－Welch Powell着色法 (4) 3.3 回溯法 (4) 3.4 贪心法 (4) 3.5 蚁群算法 (5) 4算法步骤 (5) 4.1 求极小覆盖法----布尔代数法 (4) 4.2 穷举法－Welch Powell着色法 (4) 4.3 回溯法 (4) 4.4 贪心法 (4) 4.5 蚁群法 (4) 5 理论分析（复杂度比较）、实验性能比较 (7) 5.1 复杂度分析 (4) 5.2 实验性能比较 (4) 6 心得体会 (8) 7参考文献 (8) 8 附录 (8) 摘要 图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态搜索方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。 关键词：图着色 c++代码 2、图的着色问题 2.1图的着色问题的来源 1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。” 用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这就是源于地图着色的四色猜想问题。这里所指的相邻区域，是指有一整段边界是公共边界。如果两个区域只相遇于一点或有限多点，就不叫相邻。因为用相同的颜色给它们着色不会引起混淆。 用四种颜色着色的世界地图： 采用四种颜色着色的美国地图： 2.2图的着色问题的描述 （一）图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。 （二）通常所说的着色问题是指下述两类问题： 算法分析与设计实验报告第七次附加实验 } } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5 当输入图如下时： 1 2 3 4 5 附录： 完整代码（回溯法） //最大团问题回溯法求解 #include cout<<"最大团：（"; for(int i=1;i 禁忌搜索算法评述(一) 摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法 1引言 工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化1]。 迄今为止,TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景2~9,11~15]。目前关于TS 的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。 禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。 2禁忌搜索算法的基本流程 TS算法一般流程描述1]: (1)设定算法参数,产生初始解x,置空禁忌表。 (2)判断是否满足终止条件?若是,则结束,并输出结果;否则,继续以下步骤。 (3)利用当前解x的邻域结构产生邻域解,并从中确定若干候选解。 (4)对候选解判断是否满足藐视准则?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“bestsofar”状态,然后转步骤(6);否则,继续以下步骤。 (5)判断候选解对应的各对象的禁忌情况,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。 (6)转步骤(2)。 算法可用图1所示的流程图更为直观的描述。 3禁忌搜索算法中的关键设计 3.1编码及初始解的构造 禁忌搜索算法首先要对待求解的问题进行抽象,分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略,主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示2],十进制编码将问题的解用一个十进制串来表示3],实数编码将问题的解用一个实数来表示4],在某些组合优化问题中,还经常使用混合编码5]、0-1矩阵编码等。 禁忌搜索对初始解的依赖较大,好的初始解往往会提高最终的优化效果。初始解的构造可以 实验二用回溯法求解图的m着色问题 一、实验目的 1 2、使用回溯法编程求解图的m着色问题。 二、实验原理 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。 回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。 回溯法从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 三、问题描述 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。设计一个算法，找出用m种颜色对一个图进行着色的不同方案。 四、算法设计与分析 用邻接矩阵a来表示一个无向连通图G=(V,E)。用整数1,2,…,m来表示m种不同的颜色。x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。 在回溯算法Backtrack中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色方案，因此当前已找到的可m着色方案数sum增1。当i≤n时，当前扩展结点Z是解空间树中的一个内部结点。该结点有x[i]=1,2,…,m。对当前扩展结点Z的每一个儿子结点,由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。 五、实验结果 源程序： #include 基于禁忌搜索算法的车辆路径选择 摘要：本文从VRP的提出背景与求解方法出发，阐释了禁忌搜索算法的原理与影响算法性能的关键因素，进而将禁忌搜索算法的思想运用于解决车辆路径问题，在VRP问题初始解的基础上，用禁忌搜索算法优化车辆配送路线，设计出直观且策略易于理解的客户直接排列的解的表示方法，最后将该算法用C语言实现并用于求解VRP问题，测试结果表明该算法可行且解的质量较高。 关键词：车辆路径问题；禁忌搜索；邻域；禁忌表 1.引言 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（Vehicle Routing Problem简记VRP）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且VRP问题属于NP-hard问题，求解比较困难，因此启发式算法成为求解VRP问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解VRP提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。 2.车辆路径问题的禁忌搜索算法 2.1 车辆路径问题的描述 车辆路径问题的研究目标是对一系列送货点或取货点，确定适当的配送车辆行驶路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。参见下图2.1所示：其中0表示配送中心，1～８表示客户编号。 图2.1 车辆路径问题 在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量的货物需求，且每个客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最 目录 一、摘要 (2) 二、禁忌搜索简介 (2) 三、禁忌搜索的应用 (2) 1、现实情况 (2) 2、车辆路径问题的描述 (3) 3、算法思路 (3) 4、具体步骤 (3) 5、程序设计简介 (3) 6、算例分析 (4) 四、禁忌搜索算法的评述和展望 (4) 五、参考文献 (5) 禁忌搜索及应用 一、摘要 工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 二、禁忌搜索简介 禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的meta-heuristic算法。 迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念。 三、禁忌搜索的应用 禁忌搜索应用的领域多种多样，下面我们简单的介绍下基于禁忌搜索算法的车辆路径选择。 1、现实情况 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（vehicle routing problem简记vrp）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且vrp问题属于np-hard问题，求解比较困难，因此启发式算法成为求解vrp问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解vrp提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最 算法设计与分析课程设计 题目：用回溯法分析着色问题 学院：理学院 专业：信息与计算科学 班级：09信科二班 姓名：蔡秀玉 学号: 200910010207 用回溯法分析着色问题 目录 1 回溯法 (3) 1.1回溯法的概述 (3) 1.2 回溯法的基本思想 (3) 1.3 回溯法的一般步骤 (3) 2 图的m着色问题 (3) 2.1图的着色问题的来源 (3) 2.2通常所说的着色问题 (3) 2.3图的着色问题描述 (3) 2.4回溯法求解图着色问题 (5) 2.5图的m可着色问题的回溯算法描述 (6) 2.5.1回溯算法 (6) 2.5.2 m着色回溯法递归 (8) 2.5.3 m着色回溯法迭代 (9) 2.5.4例题利用回溯法给图着色 (11) 2.6复杂度分析着色回溯法迭代 (12) §1 回溯法 1.1回溯法的概述 回溯法是一种系统地搜索问题解的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 1.2回溯法的基本思想 回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 1.3回溯法的一般步骤 用回溯法解题的一般步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 §2 图的m着色问题 2.1图的着色问题的来源 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得 第8章回溯法 (1) 8.1概述 (1) 8.1.1 问题的解空间树 (1) 8.1.2 回溯法的设计思想 (2) 8.1.3 回溯法的时间性能 (3) 8.1.4 一个简单的例子——素数环问题 (4) 8.2图问题中的回溯法 (5) 8.2.1 图着色问题 (5) 8.2.2 哈密顿回路问题 (8) 8.3组合问题中的回溯法 (10) 8.3.1 八皇后问题 (10) 8.3.2 批处理作业调度问题 (13) 习题8 (16) 第8章回溯法 教学重点回溯法的设计思想；各种经典问题的回溯思想教学难点批处理作业调度问题的回溯算法 教学内容 和 教学目标 知识点 教学要求 了解理解掌握熟练掌握问题的解空间树√ 回溯法的设计思想√ 回溯法的时间性能√ 图着色问题√ 哈密顿回路问题√ 八皇后问题√ 批处理作业调度问题√ 8.1 概述 回溯法（back track method）在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，对于解空间树的某个结点，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该结点为根结点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解，所以，适用于求解组合数较大的问题。 8.1.1 问题的解空间树 复杂问题常常有很多的可能解，这些可能解构成了问题的解空间（solution space），并且可能解的表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题，一般情况下，将问题的可能解表示为满足某个约束条件的等长向量X=(x1, x2, …, x n)，其中分量x i（1≤i≤n）的取值范围是某个有限集合S i={a i,1, a i,2, …, a i,r i }，所有可能的解向量构成了问题的解空间。例如，对于有n个物品的0/1背包问题，其可能解由一个等长向量{x1, x2, …, x n}组成，其中x i=1（1≤i≤n）表示物品i装入背包，x i=0表示物品i没有装入背包，则解空间由长度为n的0/1向量组成。当n=3时，其解空间是： 图的m着色问题 1．问题描述 给定无向量图G顶点和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G图中每条边的两个顶点着不同的颜色。这个问题是图的m 可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色问题。2．算法设计 一般连通图的可着色法问题并不仅限于平面图。给定图G=（V，E）和m种颜色，果这个图不是m可着色，给出否定回答，如果这个图是m的可着色的，找出所有不同的着色法。 下面根据回朔法的递归描述框架backtrack设计图的m着色算法。用图的邻接矩阵a表示无向量连通图G=（V，E）。若（i，j）属于图G=（V，E）的边集E，则a[i][j]=1，否则a[i][j]=0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用x[i]表示，数组x[1：n]是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第I （1<=i<=n）层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。 在算法backtrack中，当i>n时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数sum增1。 当I 图的m着色问题 问题描述： 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m 可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。 编程任务： 对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。 数据输入： 由文件input.txt给出输入数据。第1行有3个正整数n，k和m，表示给定的图G 有n 个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G的一条边(u,v)。 结果输出: 程序运行结束时，将计算出的不同的着色方案数输出到文件output.txt中。 输入文件示例输出文件示例 input.txt output.txt 58448 12 13 14 23 24 25 34 45 /*图的m着色问题求解程序（回溯算法）*/ #include 图节点着色问题中的禁忌搜索算法 09-03-25 作者：编辑：校方人员 图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题。目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。 本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性。禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有效的应用于一些典型NP问题，如TSP。但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。 1图节点着色问题 图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的 给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集，其中(i,j)表示有连接(i,j)的一条边。若，且V i内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…,V n)为V的一个划分。图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,V n)为V的一个划分。 通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。故通常的算法在解决图节点着色问题这样的NP完全问题时，存在很大的瓶颈，难以得到满意的结果。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。 禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索 中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个没有兔子留守的地方优越性太突出，超过 了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达 procedure tabu search; begin initialize a string vc at random,clear up the tabu list; cur:=vc; repeat select a new string vn in the neighborhood of vc; if va>best_to_far then {va is a string in the tabu list} begin 实验四回溯算法 一、实验目的 1)理解回溯算法的基本原理，掌握使用回溯算法求解实际问 题。 二、方法原理 回溯法是一种类似穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回退，尝试别的路径。 三、实验设备 PC机一台，C语言、PASCAL语言、Matlab任选 四、掌握要点 搜索到解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则进入该子树，继续按深度优先的策略进行搜索。 五、实验内容 实验内容：（二选一）1）编写程序实现4后问题的求解；2）编写程序实现用3种颜色为图2着色问题； 图2 六、实验要求 1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法； 2)编写上机实验程序，作好上机前的准备工作； 3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）； 4)分析和解释计算结果； 5)按照要求书写实验报告； 源代码：着色问题 #i n c l u d e i n t T F(i n t c o l o r,i n t i n d e x,i n t m[][M A X],i n t p[]){ f o r(i n t i=0;i 6.2基于均衡原理的LRP 算法设计 6.2.1基于均衡原理的LRP 算法整体流程 基于均衡原理的LRP 算法整体流程如下： step1：初始化，设置整体收敛性判断参数δ； step2：随机生成一组LRP 选址问题的解D ，求出相应的目标值F ； step3：根据上层解D ，利用Frank-Wolfe 算法（见6.2.3节）求出各客户的 货物总量Q j 及客户在各配送中心的货物均衡分配量x j i ,； step4：根据D 及x j i ,运用禁忌算法求解VRP 问题(见6.2.4节)，得出各配送 中对各客户的单位货物配送费用C j i ,； step5：根据 x j i ,及公式（6-8）求出下层 x j i ,与 d i 的关系y d x j i i j i W ,,+ =； step6：将LRP 模型上层目标函数中用代替，并代入下层求得的Q j 和C j i ,，运用禁忌算法 求得新的LRP 选址规划的解'Z 及目标函数'F （见6.2.2节）； step7：如果δ<-F F ' ，转step8，算法结束，D 、F 为LRP 的最终解和解值；否则 '':,:F F D D ==，转step3； step8：算法结束。 6.2.2 LRP 选址规划的禁忌算法 模型上层是基于0-1整数规划的选址问题。由于选址问题是NP-hard ，如果 用精确算法求解，对节点数目的限制将有严格的要求。本章根据模型的特点， 采用禁忌算法优化产业选址问题。 1．解的构造和初始解的生成 采用二进制编码，编码长度为潜在的配送中心地点数量N T ，对于编码中位置i ，1表示选中i 点作为厂址，0表示没有选中。对于解中任意点i ，产生随机数δ，如果N T N /≥δ，则置i 点为0，否则置1。重复以上步骤m 次，得到初始解。 2．邻域的搜索 根据本章选址问题的特点，设计了三种邻域操作，分别为自身取反、2-swap 交换和2-opt 交换。 1）．自身取反。为单点操作，即选择解中i 点，对该点的值取反； 2）．2-swap 交换。为双点操作，选择解中两点进行交换，其它位置的值不变。例如解001101中的2、6点被选中，则2-swap 交换后变为：011100； 3）．2-opt 交换。为多点操作，选择解中两点进行交换，同时两点之间的值逆序改变。例如解001101中的2、6点被选中，则2-swap 交换后变为：010110； 1 第七章 回溯 7.1 回溯法的思想方法 7.1.1 问题的解空间和状态空间树 一、解空间 问题的解向量为),,,(21n x x x X 。i x 的取值范围为有穷集i S 。把i x 的所有可能取值组合，称为问题的解空间。每一个组合是问题的一个可能解 例：0/1背包问题，}1,0{ S ，当3 n 时，0/1背包问题的解空间是： {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)} 当输入规模为n 时，有n 2种可能的解。 例：货郎担问题，},,2,1{n S ，当3 n 时， }3,2,1{ S 。货郎担问题的解空间是： {(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),┅,(3,3,1),(3,3,2),(3,3,3)} 当输入规模为n 时，它有n n 种可能的解。 考虑到约束方程j i x x 。因此，货郎担问题的解空间压缩为： {(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)} 当输入规模为n 时，它有!n 种可能的解。 二、状态空间树：问题解空间的树形式表示 当4 n 时，货郎担问题的状态空间树。 图7.1 n=4时货郎担问题的状态空间树 4 n 时，0/1背包问题的状态空间树 2 图7.2 n=4时背包问题的状态空间树 7.1.2 状态空间树的动态搜索 一、可行解和最优解 可行解：满足约束条件的解，解空间中的一个子集 最优解：使目标函数取极值（极大或极小）的可行解，一个或少数几个 例：货郎担问题，有n n 种可能解。!n 种可行解，只有一个或几个解是最优解。 例：背包问题，有n 2种可能解，有些是可行解，只有一个或几个是最优解。 有些问题，只要可行解，不需要最优解，例如八后问题和图的着色问题 二、状态空间树的动态搜索 l _结点（活结点）：所搜索到的结点不是叶结点，且满足约束条件和目标函数的界， 其儿子结点还未全部搜索完毕， e _结点（扩展结点）：正在搜索其儿子结点的结点，它也是一个l _结点； d _结点（死结点）：不满足约束条件、目标函数、或其儿子结点已全部搜索完毕的结 点、或者叶结点，。以d _结点作为根的子树，可以在搜索过程中删除。 例7.1 有4个顶点的货郎担问题，其费用矩阵如图7.3 所示，求从顶点1出发，最后回到顶点1的最短路线。 ∞ ∞ 1 7 8 ∞ 5 1 7 2 ∞ 6 2 5 3 ∞ 图7.3 4个顶点的货郎担问题的费用矩阵及搜索树 7.1.3 回溯法的一般性描述 题的解向量),,,(110 n x x x X ， i x 的取值范围i S ，},,,{.1.0.i m i i i i a a a S 。 问题的解空间由笛卡尔积110 n S S S A 构成。 无时限单向配送车辆优化调度问题的禁忌搜索算法无时限单向配送车辆优化调度问题，是指在制定配送路线时不考虑客户对货物送到（或取走）时间要求的纯送货（或纯取货）车辆调度问题。 无时限单向配送车辆优化调度问题可以描述为：从某配送中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足一下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量； （2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离； （3）每个客户的需求必须满足，且只能由一台配送车辆送货。 一、禁忌搜索算法的原理 禁忌搜索算法是解决组合优化问题的一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。 在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。 二、算法要素的设计 1.禁忌对象的确定 禁忌对象是指禁忌表中被禁的那些变化元素。由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。 一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。 根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。 2.禁忌长度的确定 禁忌长度是指被禁对象不允许被选取的迭代步数，一般是给被禁忌对象x一个数l（称为禁忌长度），要求x在l步迭代内被禁，在禁忌表中采用Tabu(x)=l记忆，每迭代一步，该指标做运算Tabu(x)=l-1，直到Tabu(x)=0时解禁。关于禁忌长度l的选取，可归纳为以下几种情况。 （1）l为常数，可取l=10、（n为领域中邻居的总个数）。这种规则容易在算法中实现。 （2）。此时，l是可以变化的数，其变化的依据是被禁对象的目标函数值和领域的结构。、是确定的数，确定的常用方法是根据问题的规模N，限定变化区间；也可以用领域中邻居的个数n确定变化区间。 禁忌长度的选取同实际问题和算法设计者的经验有紧密联系，同时它也会影响计算的复杂性，过短会造成循环的出现，过长又会造成计算时间的增加。 3.候选集合的确定 候选集合由领域中的邻居组成，常规的方法是从领域中选择若干个目标函数值或评价值最佳的邻居。禁忌搜索算法浅析
图着色
回溯法实验(最大团问题)
禁忌搜索算法评述(一)
用回溯法求解图的m着色问题
论文-禁忌搜索算法
禁忌搜索和应用
用回溯法分析着色问题
回溯法
图的m着色问题回溯法
m着色问题
图节点着色问题中的禁忌搜索算法
禁忌搜索算法摘录
回溯算法(解决着色问题)
#i n c l u d e #d e f i n e T R U E1 #d e f i n e F A L S E0 #d e f i n e M A X5 #d e f i n e C O L O R C O U N T3禁忌搜索算法公式
算法设计与分析学习提纲,第七章回溯
禁忌搜索算法
相关主题
文本预览