GRASP算法解决图的凸重着色问题

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）379-391www.elsevier.com/locate/entcs图的凸重着色问题的GRASPAna Paula dos Santos Dantasa，1，2 Cid Carvalho deSouzaa，1，2 Zanoni Diasa，1，2a巴西坎皮纳斯大学计算研究所摘要在本文中，我们认为着色是一个函数，它赋予一个颜色的顶点，而不管颜色的它的邻居。凸再着色问题是要找出使着色凸化所需的最少数量的再着色顶点，也就是说，由所有具有相同颜色的顶点形成的每个集合都诱导出一个连通子图。该问题是最常见的研究考虑树，由于其起源于系统发育树的研究，但在本文中，我们专注于一般图，并提出了一个GRASP启发式解决问题所在我们目前的计算实验，我们的启发式和比较，从文献中的一个线性规划模型。在这些实验中，GRASP算法重新着色了与文献中的模型相似数量的顶点，并且使用了相当少的时间。 我们还介绍一组问题的基准实例关键词：凸重着色，GRASP，组合优化。1引言凸邻接问题起源于系统发生树的研究。系统发育树重建了一组具有共同特征的物种的进化历史。这些树的叶子是已知的有机体，其余的顶点是假设的祖先。这种树的一个重要特征是，相似的生物体预计会出现在彼此附近[9]。在系统发育树中，物种的共同特征可以表现为不同的状态，每个物种只表现出一种可能的状态。通过用不同的颜色表示每个状态，我们可以建立一个着色1本工作得到了国家发展科学委员会的支持。（304727/2014-8、400487/2016-0、425340/2016-3和140466/2018-5 ） ， 圣保罗州 Amparo`a 渔业 基 金 会 （ 2013/08293-7 ， 2015/11937-9 ， 2017/12646-3 ， 2017/16246-0 ， 和2018/04760-3），C o rdenadécilaçãodeA perfeidécilaçoamentodoPess oaldoEnsinoSu preior和CAPES/COFECUB计划（831/15）。2电子邮件：ana. students.ic.unicamp.br，cid@ic.unicamp.br，zanoni@ic.unicamp.brhttps://doi.org/10.1016/j.entcs.2019.08.0341571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。380美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379的进化树。由于类似的生物体在这样的树中应该保持接近，所以同样颜色的顶点也应该在树中彼此接近在图形术语中，不幸的是，许多系统发育树并不具有这种特性，这是因为在构建系统发育树或对生物体进行分类时存在错误[8]。考虑到树的结构是可靠的情况所有相似的生物都彼此接近凸重着色问题的目的是找到凸重着色距离。由于其起源，该问题主要在树上研究。Moran和Snir[12]证明了树上的版本是NP-困难的。Chopra等人[4]提出了一个整数规划模型来求解树上的凸邻接，与以前的方法相比，该模型已知的最佳近似因子为树的问题是2 + λ，由Bar-Yehuda等人提出。 [1]的文件。许多版本的问题被认为是通过修改：（i）图的类，其上的着色应用，如一般的图和路径;或（ii）如何着色应用。Kammer和Tholey[10]讨论了这种情况的一个例子，他们研究了映射计算机网络的一般图的问题，并对哪些顶点可以重新着色以及哪些顶点只能是无色的进行了限制。本文主要研究一般图的凸包围问题，对包围没有任何限制。这个版本的问题也被证明是NP难的[13]。据我们所知，只有精确的算法已被提出来解决这个问题，到目前为止，但没有计算结果的报告。我们的贡献是一个算法的基础上，这种变化的meta-economistics GRASP。除了详细介绍该方法外，我们还定义了一类实例这个问题可以作为基准。本文件的其余部分安排如下。在第2节中，我们给出了贯穿全文的凸优化问题的基本定义。在第3节中，我们讨论了目前可用于解决该问题的方法在第4节中，我们详细介绍了所提出的算法。在第5节中，我们报告了我们的实验并讨论了结果。最后，在第六节中，我们得出了我们的结论，并指出了未来的研究方向。2定义一个图G被定义为一个有序对（V，E），其中V是顶点集，EV×V作为边的集合。我们说两个顶点u和v是相邻的，或邻居，如果边（uv）在E中。S∈V诱导的子图是指顶点集为S，且边都是（uv）∈E且u，v∈S的图.让我们用一个整数来表示一种颜色，用符号表示颜色的缺失。图G=（V，E）的一个着色是一个函数C：V→ C，美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379381拉吉097352641 8097352641 8097352641 8(a)初始 颜色- (b)凸反射 (c)最佳回收率ingoringoringFig. 1.实例的例子。图1（a）显示了一个彩色图。图1（b）和1（c）显示了可能的替代方案。颜色到G的顶点，其中C是颜色的集合。G的一个部分着色C：V→ C <${n}是一个允许顶点未着色的着色函数，即不给它赋颜色，色类c是所有具有该颜色的顶点的集合c∈ C。如果一个颜色的色类导出一个连通子图，则称该颜色是凸的，否则称该颜色是坏的。一个着色是凸的，如果每个颜色都是凸的。给定图G和它的一个着色，（G，C）被称为着色图。 着色图（G，C）的一个着色CJ是G的一个扩环.给定一个着色图（G，C）和G的一个邻接环CJ，RC（CJ）是（G，C）的着色顶点的子集颜色在装饰中，即， R C（CJ）={v ∈ V |C（v）= CJ（v）}。注意虽然（G，C）中的未着色顶点不在RC（CJ）中，但集合中可能包含被C着色但不被CJ着色的顶点。现在，设w：V→Q+是一个函数，它将成本分配给V中的相邻顶点。凸规划问题是定义如下。定义2.1C凸 RE着色问题（CRP）输入：图G、颜色集合C、部分着色C和代价函数 w;2、求一个最小代价的凸包围C，即min（v∈RC（C′）w（v））。图1显示了凸优化问题的一个实例。 假设所有的成本都是一个。图1（a）显示了一个有三种颜色的彩色图。图1（b）中的包围四个顶点（{0，3， 4， 8}）。图1（c）中的仿射是最优的，并且仅仿射三个顶点（{0， 2，3}）。3阶线性规划模型Cam p Pleaselo等. [3]将CRP建模为具有指数约束的整数规划。Elena [14]也给出了这个问题的ILP公式，但是变量的数量是指数级的，并建议了一个列生成算法来解决仅限于树的情况的模型。这两种配方的计算实验集中在系统发育树。由于Pricing Subproblem的[14]不处理一般的图，我们的实验只涉及由Cam p Pillelo等人的计算。 [3]的第11段。Cam Pomelo的模型由等式1至4给出。在该公式中，如果C（v）=c，则常数wv，c等于w（v），否则等于0。cRP的未加权版本要求对所有v∈V，w（v）=1。二进制变量xv，c被设置为1当且仅当c是分配给顶点v的颜色。为了理解这个模型，回想一下，对于一对（u，v）不相邻的顶点，（u，v）顶点切割是一组顶点Z，382美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379ΣΣΣΣ当从G中移除时，留下u和v在单独的分量中。如果Γ（u，v）是G中所有极小（u，v）顶点割的集合，则模型为：最大wv，c xv，c（1）v∈V c∈CS.T.x v，c≤ 1<$v ∈ V（2）c∈Cxu，c+xv，c−xz，c≤1<$uv∈/E，Z∈Γ（u，v），c∈ C（3）z∈Zxv，c∈{0， 1}<$v∈V，< $c∈C（4）等式1将目标函数定义为最大化保持其初始颜色的顶点数量，这相当于最小化切换颜色的顶点数量等式2强制每个顶点接收最多一种颜色。等式3保证任何两个不相邻的相同颜色的顶点是连接的。等式4将决策变量xv，c的值限制为二进制。Cam p Pleaselo等.[3]给出了该公式正确性的证明，以及多面体的研究。我们实现了该模型，并使用它来评估我们提出的启发式的结果。4一种贪婪随机自适应求解方法在本节中，我们提出了一种基于贪婪随机自适应搜索过程（GRASP）[7]求解一般图中的CRP的算法。该过程的每次迭代由两个按顺序执行的阶段组成。第一阶段建立一个可行的解决方案，而第二阶段则对该解决方案进行局部搜索重复迭代，直到达到停止条件（通常是迭代总数），并返回找到的最佳解决方案初始阶段的构造算法也是迭代的，并且具有三个关键组成部分。第一个是贪婪组件：在每次迭代中，都有一个部分解可用，并且要添加到其中的候选元素被放入一个列表，根据贪婪标准进行排序，该标准衡量一个元素与其他可能的元素相比有多好。第二个关键组成部分是随机化：而不是在先前排序的列表的顶部挑选候选人，而是形成一个限制候选人列表（RCL），其中只有一定比例的最佳候选人，从中随机选择一个。第三个关键组成部分是自适应性：每次迭代都受到前一次迭代的影响，因为每次选择都会修改解决方案的状态。我们选择这种元启发式方法是因为它简单，调谐参数，即，考虑用于选择的最佳候选者的百分比和停止条件。抓取的另一个优点是它有可能与其他技术相结合，例如可变邻域搜索和并行化[15]。接下来，我们描述我们掌握的解决cRP的主要成分。4.1 贪婪随机自适应解。我们手术中的一个关键手术美国邮政Dantas等人/理论计算机科学电子笔记346（2019）3793830 9 75 24631 8(a) 输入图(b)输出图图二、做心理医生。图2（a）是手术前的图表，图2（b）显示了新的图表。就是顶点的收缩。将顶点u收缩为相邻顶点v将u从图中移除，并将其邻接添加到v的邻接。在这种情况下，v被称为代表u。图2说明了操作，其中顶点3收缩为顶点1。在收缩之前（图2（a）），顶点{0， 1， 5， 6， 9}与顶点3相邻，顶点{3， 8}与顶点1相邻。图2（b）中的结果图，其中顶点3被删除，顶点1变得相邻，不仅是它的旧邻居，而且是顶点3的邻居构造阶段在算法1中详细描述。 贪婪选择将顶点相邻化，旨在获得大的单色分量。该算法在一个着色图（H，D）上运行，该着色图（H，D）由原始图G及其着色C初始化。接下来，H的每个单色分量被收缩成单个顶点。 然后，重复以下步骤，直到H中没有坏颜色为止：根据贪婪准则对顶点进行排序，根据贪婪准则在最佳候选者的一部分中选择顶点v，切换v的颜色，最后，将其具有相同颜色的邻居收缩到其中。对所选顶点重新着色的详细说明如下。当一个解被构造后，G的所有顶点要么在H中，要么由H的一个顶点表示。为了提取G的一个包围圈，我们将来自H的顶点v的颜色赋给它在G中的副本和v所代表的顶点。我们设想了两个备选标准来选择、排序和重新着色候选顶点。一个叫做比率，另一个叫做联合。Ratio准则将每一个顶点v∈H作为候选，使得D（v）=/它基于两个值：重量和比率。一个顶点的权值由它所代表的顶点的个数顶点的比率是其邻里最常见的颜色除以邻里的大小。候选项的排序按照权重的升序对顶点进行排序，并按照比率的降序打破联系。因此，排序后的候选列表的第一个顶点是具有最小权重的顶点，并且在平局的情况下，是具有最大比率的顶点。创建RCL后，选择顶点v，并根据其邻居颜色的频率选择其新颜色如果最常见的颜色出现了不止一次，那么v接收这个颜色。如果没有两个邻居v具有相同的颜色，但是在它的邻接中有凸颜色，v接收这个颜色;否则，v是未着色的。图3举例说明了比率标准。考虑图3（a）的初始着色，每个顶点的权重为1，因为没有进行收缩。该比率基于相同的拓扑计算。例如，顶点3有五个相邻的顶点，其中三个具有相同的颜色， 所以它的比例是3/ 5。图3（b）显示了使用比率标准排序的顶点0 9 73 5 26 41 8384美国邮政Dantas等人/理论计算机科学电子笔记346（2019）3790 9 75263418c=1c=1c=1u=2u=2u =12 3 1算法1. GRASP建设阶段建筑（G，C）设D是CQ着色备份副本设H是GQ图备份的副本用相同的颜色收缩H的所有相邻顶点而Ddo中有一个不好的颜色L←来自H的候选顶点的排序列表(a) 初期着色(b) 第一排序w=1w =1w =1w =1r=1. 0 r =1。0 r =1。r =0。61682RCL←最佳候选人的百分比w=1w =1w =1w =1r=0。6 r =0。5 r =0。5 r =0。5从RCL中随机选择一个v改变D中v的颜色3045w=1w =1r =0。5 r =0。5收缩v的相邻顶点，把同样的颜色变成Vend whilew=1w =1w =1w =1r=1. r =0。5 r =1。r =0。61082C′←将D展开为G的一个可积函数w=1w =1r =0。5 r =0。5returnC′5 7w=1w =3r =0。5 r =0。696(c) 后缩(d) 二排序Alg. 1. 抓好建设阶段。.图三. 施工阶段使用比率临界值。c=1u=16c=1c=1c=1c=1u=1u=1u=0u =0c=1u=168 9 0 4c=1c=1c=3u=1u =0 u =2c=1c =1u=0u=09 0 25 7(a) 初始颜色-（d）第二次ing(b) 第一排序(c) 后缩排序图四、施工阶段采用联合准则。在每个顶点之上，我们有它们各自的权重（w）和比率（r）值。假设我们考虑30%的最佳候选者（那些用虚线轮廓的候选者图3（b））中随机挑选一个。此外，假设顶点6（图3（b）中的虚线和阴影）被选择为重新着色。 顶点6用其邻域上最频繁的颜色重新着色，即，顶点3和顶点4的颜色。接下来，顶点3和4收缩为6，如图3（c）所示。图3（d）显示了这个排序如何影响构造过程的下一次迭代的排序。注意，顶点6的权重是3，因为现在它代表顶点3，4和它自己。并准则将颜色不凸或至少有一个邻居颜色不凸的每个顶点视为候选。同样，排序过程依赖于两个值。第一个是顶点着色的成本，由它所代表的顶点数量给定，并且以前没有重新着色。第二个是顶点v的联合因子，它是添加到颜色分量的顶点的最大数量，如果v被分配给同一颜色。 该数量可以计算如下。 给定颜色c，c相对于v的因子是v的邻居的权重之和，颜色c不包括它们中最大的。v的联合因子被定义为颜色相对于v的最大因子。 如果c是 与此值相关联的颜色，新的颜色v变为c。联合准则优先考虑具有较小包围成本的顶点，并且在联合因子的降序图4解释了联合标准的使用。图4（a）描绘了图的初始着色。在这种情况下，每个顶点只代表它自己，还没有顶点被重新着色，所以，每个顶点的成本是1。计算联合因子0973 526418097352641 80 93 52724861c=1c=1c=1u=2u=1u =13 1 5美国邮政Dantas等人/理论计算机科学电子笔记346（2019）3793850 9 73 5 226 4∞180 9 73 5 26 4∞1 8−2 2 12∞（一）（b）第（1）款（c）第（1）款(d)(e)(f)图五.图5（a）的邻接的简单（图5（b））和扩展（图5（c）、5（d）、5（e）和5（f））邻域。如上所述为了简化一个这样的计算，考虑顶点3。它有五个邻居，三个颜色相同，两个颜色不同。由于每个顶点的权重为1，因此黄色的因子为1+ 1 + 1− 1 = 2，蓝色的因子为1+1 1 = 1。顶点3的并集因子是两者中最大的，如果选择要重新着色，它将接收黄色。图4（b）显示了顶点的排序我们再次认为前30%是最好的。现在假设顶点2是随机选择的。它将被重新着色为红色，它的红色邻居将缩小到它里面。图4（c）显示了结果图。在下一个排序阶段，图4（d），顶点2的权重为4，因为除了它自己，它还代表了顶点{4， 7， 8}，但是排序的代价只有3，因为顶点2已经被重新着色了。4.2 本地搜索局部搜索例程在每个解被构造以探索解的邻域以搜索局部最大值之后执行。我 们 提出了两个邻域：简单邻域和扩展邻域.这些街区在下面详细介绍。基本思想是恢复顶点的颜色变化，即，找到一个重新着色的顶点，并将其返回到原来的颜色。 简单和扩展之间的区别在于它们如何找到这些顶点。给定一个着色图的凸包围，通过寻找一个被重新着色且可以从其新的色类中移除而不断开的顶点，构造一个简单邻域.如果找到这样的顶点v如果v与用v用它原来的颜色重新着色。重复使用简单邻域的局部搜索过程，直到不再有顶点可以将其颜色改变回来。图5（a）和图5（b）示出了该邻域的示例图5（a）中的轮廓顶点意味着它被重新着色。轮廓的颜色 顶点2已重新着色，如果从其当前颜色类中删除，将不会断开它的连接。此外，2与具有原始颜色的顶点相邻，因此，它可以恢复。注意，我们也可以选择3。图5（b）展示了新的边界。由于没有更多的顶点可以恢复，该过程以比开始的一个单位便宜一个单位的一个替代品结束。扩展邻域是通过系统地去除所有顶点的颜色来构造的，这些顶点被重新着色，并且可以从它们的新类中去除而不会断开它们。在移除每个可能的顶点的颜色之后，我们覆盖未着色的顶点，并找到一条到达其原始颜色的路径。此路径必须仅包含未着色的顶点。 然后，我们选择具有最小路径的顶点归去来兮，道也。这个寻找路径和连接的过程0 9 73 5 26 41 80 9 73 5 26 41 810 9 73 5 226 4∞180 9 73 5 26 4∞1 8386美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379∈∈重复，直到没有顶点可以连接到其原始颜色。图5（c）将图5（a）中的着色图作为输入，图5（c）是扩展局部搜索的未着色阶段的结果，其中白色顶点未着色。在这个图中的每个未着色的顶点v上，给出了从v到具有其原始颜色的顶点的最小距离。请注意，对于顶点1，这个距离是∞，因为不存在仅由连接1到蓝色顶点的未着色顶点组成的路径。由于顶点9具有最小的这样的距离，所以它的颜色被改变回来，并且如图5（d）所示计算新的路径。 下一个最小距离是2，顶点4或7的颜色会变回原来的颜色。 假设我们恢复顶点4的颜色。 图5（e）描绘了该操作的结果。 最后，顶点7恢复到其原始颜色，并获得图5（f）中的最终颜色，成本降低了3个单位。5计算结果本节报告了我们用ILP进行计算实验的结果模型和抓取算法。5.1 线性规划模型首先，我们描述了实施细节的形式模拟提出了由凸轮padelo等人。 [3]（ILP）并给出了计算测试的结果。该模型是用C++编程语言编写的，使用g++（5.4版）编译，用C++11编译，并由IBM的CPLEX（12.8版）求解。实验在IntelRCoreTMi7 3.40GHz机器上进行，内存为32GB，运行Ubuntu18.04 LTS。我们为求解器设置了30分钟的时间限制，并将预解和多线程设置设为0。由于公式具有指数数量的限制，我们实现了一种方法，该方法放松了对等式3的限制，并在稍后将其添加为惰性约束。为了识别违反的约束，我们从输入图G构建有向图D，使得对于每个顶点v V（G），我们将两个顶点v+和v-添加到由弧（v-，v+）连接的V（D），并且对于每条边e = uvE（G），我们将弧（u+，v−）和（v+，u−）相加。对于每个颜色c，我们为D的弧分配权重，并使用网络高效建模和优化库（LEMON）中的实现执行最小切割/最大切割算法[6]。对于形式为（w-，w+）的每条弧，权重是xw，c的值，对于其他每条弧，权重是1。如果从u+到v-的最大切流小于1，则最小割弧形成顶点割集。由于没有一般图表的实验结果报告在文献中，我们寻求为CRP生成硬实例。在预审中-在初步研究中，我们注意到，坏颜色的数量大大影响了一个实例的困难。考虑到这点，我们试图找到一些极端的案例不好的颜色类别，并注意到，一个适当的着色，即， 其中没有两个相同颜色的顶点相邻，满足这个要求。所以我们建立100个Erdos-Renyi连通随机图，每个n∈ {10，20，.，100}和美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379387180015001200900600300010203040506070809010086420102030405060708090100数量的顶点(a) 平均时间数量的顶点(b) 平均间隙见图6。 执行ILP模型后获得的平均值。p∈{0. 1，0。二，0。5}，其中n是图的顶点数，p是添加边的概率，因此是图的对于这些图中的每一个，我们基于Bondy和Murty [2]中引入的贪婪算法产生了适当的着色。 从这样的着色开始，我们应用一个平衡的过程，将顶点从最大的颜色类移动到最小的颜色类，同时保持适当的着色属性。我们的基准可以在www.example.com上找到www.loco.ic.unicamp.br/files/instances/convex-recoloring。图6（a）和6（b）分别显示了用于解决每个对（n，p在每一个图中，x轴表示顶点数n，每条线表示不同的密度p。 图6（a）显示，当我们增加图的密度时，实例对于模型变得更容易，因为它们在时间限制之前被解决。我们还观察到重新着色的顶点和惰性约束的总数减少了。当一个实例在时间限制之前完成执行时，这意味着它找到了一个最佳解决方案，并且差距为零。相反，达到时间限制的实例具有正间隙。图6（b）显示了所有实例大小的平均间隙。为了检查前面的实例是否由于使用了正确的着色而确实很难，我们创建了类似的实例，但使用了不同的着色。这些实例具有相同数量的颜色，每个颜色类的顶点分布相同，并且每个类都是坏的。 我们创建了n∈ {10，20，.100}且p∈ {0。1，0。2}，我们可以保证上述性质的值。该模型在时间限制之前将所有实例求解为最优，需要更少的推理和更少的惰性约束。5.2 抓。第4.1节讨论了构建解决方案的两组标准。本节分析了这两组测试的结果。它们是使用编程语言C++实现的，编译器使用C++11和-O3，编译器g++（版本5.4）。下面报告的实验是在与ILP模型相同的机器上运行的，并且使用相同的实例。在执行实验之前，需要调整两个抓取 第一个是停止条件。 对于这个版本，我们使用了2n2次迭代，其中n是输入的顶点数。第二个参数是在随机选择候选人时要考虑的百分比，为此，我们使用了R包迭代竞赛自动算法配置（irace）[11]。为了设置irace，我们随机选择了20%的实例，并将它们分为训练集（80%）和测试集（20%）图的密度相等，p = 0.1 p = 0.4p= 0.2p = 0.3p = 0.5p= 0.1p = 0.4p = 0.2p= 0.3p = 0.5时间（秒）差距（%）388美国邮政Dantas等人/理论计算机科学电子笔记346（2019）37920−2−4−6−8−10−12−141020304050607080 90100数量的顶点(a) 比20−2−4−6−8−10−12−141020304050607080 90100数量的顶点(b) 联盟图第七章为每个条件添加随机化后，重新着色的顶点数的在这个样本中。由irace返回并在实验中使用的值是13。954%的比率标准和10。229%，符合欧盟标准。我们的第一个实验是将每个标准与它们的纯粹贪婪版本进行比较，该版本选择排序列表的第一个元素，而不是RCL中的随机元素。我们这个实验的目的是证明使用随机化的解决方案会更好。我们执行了一个抓取版本，没有任何局部搜索和纯粹的贪婪算法。图7（a）和图7（b）分别显示了在比率和联合标准下添加抓取随机部分后，重新着色顶点数量的差异来自图7的图的x轴示出了输入图的顶点的数量，并且框指示在添加随机化之后重新着色的顶点的数量的差异。所有密度都表示在一起，这些图表。对于比率准则，图7（a）显示，有一些情况下，贪婪比随机版本更好，也就是说，贪婪解决方案重新着色的顶点更少。在图中，这些是值大于零的实例。该图表明最好使用随机化。为了确认存在显著差异，我们进行了Wilcoxon符号检验。我们的零假设是两种方法之间没有统计学上的显著差异我们测试的z统计量值为-59。83，考虑到置信水平为0。95，我们必须有z<-1。96拒绝零假设[5]。因此，我们可以拒绝零假设。对于联合准则，图7（b）表明，对于每一个实例，随机化版本至少与纯贪婪版本一样好我们还进行了Wilcoxon-59。06，也拒绝零假设。接下来，我们执行实验来测量在每次抓取迭代中使用局部搜索的影响，以改进两个标准的解决方案。我们用4.2节中定义的每个局部搜索邻域执行每个标准。 由于我们现在有三种方法（无局部搜索，简单局部搜索和扩展局部搜索），我们使用Iman-Davenport测试来比较这些方法。Iman-Davenport统计量F F遵循F分布，具有（k−1）和（k−1）（N−1）个自由度，其中N为实例数，k为方法数。零假设与之前的测试相同。对于3种方法和5000个实例，以及0.95的置信水平，我们需要FF>3.00. 我们比较的解决方案的比率标准使用这个测试，并发现FF= 25。44，因此我们拒绝零假设。使用相同的测试对于联合准则的解，我们发现FF=4。81，再次拒绝null方向（顶点）方向（顶点）美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379389CD1 23CD1 2 3比率−扩展比率−简单(a) 比比率−无并-扩展并集-单(b) 联盟联合−无图八、每个标准的不同局部搜索邻域的临界差异（CD）3210−1−2−3−410203040506070809010010310210110010−110−210−310−4102030405060708090100数量的顶点(a) 重着色顶点数量的顶点(b) 时间图第九章最佳抓取方法与ILP模型的比较假说. 因此，我们得出结论，局部搜索对解决方案的质量有重大影响接下来，我们使用每个标准执行Nemenyi事后检验。这些测试的图示见图8（a）和8（b）。 Nemenyi测试使用平均等级测量方法之间的临界差异（CD）。在这些图中，如果两种方法之间没有显著差异，则表示这些方法的垂直线由水平线段连接。这些数字表明，对于比率标准，没有等效的方法。对于联合准则，使用扩展邻域的准则和不使用任何局部搜索的准则具有显著差异。同样从Nemenyi测试中，我们可以提取具有最佳平均秩的方法是使用扩展邻域进行局部搜索的方法的信息。我们现在调查，如果从每个标准的最佳方法的组合产生一个更好的结果。 该组合按顺序执行每个方法的所有2n2次抓取为了回答这个问题，我们首先计算了一次比其他的要好，我们发现联合是大约40个中最好的。0%的实例数和比率，在4. 5%，其余情况为平局。然后，我们应用Iman-Davenport统计检验比较比率标准，工会标准和组成。如果F F > 3，我们可以拒绝零假设。00.因为我们发现F F= 576。83，我们认为执行两个标准比只使用其中一个标准更好执行事后Nemenyi测试，我们发现这些方法中没有两种是等效的，并且组合物具有最好的平均秩。我们的最终实验是比较最佳抓取方法与整数线性规划模型的解决方案。图9（a）和9（b）分别比较了解的值和执行时间。图9（a）报告了相对于ILP模型的抓取对于n ≤ 60的所有情况，最优解都是已知的，在这种情况下，抓取平均重新着色为3。比最优解多21%的顶点。对于n> 60的实例，抓持平均重新着色2。顶点数比方向（顶点）PLI组合物时间（秒）390美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379由ILP模型返回的解决方案。图9（b）描述了抓取和模型的运行时。注意，y轴的刻度是对数的。我们可以看到，随着顶点数量的增加，模型6结论本文提出了解决一般图的凸包围问题的一种思路两组贪婪的标准被认为是创建解决方案。实验表明，两者的结合比单独使用效果更好. 我们还实现了Camp Pillelo等人[3]提出的整数编程模型，并将其用于比较目的。我们发现，GRASP产生的解决方案，重新着色一个b出相同的nu mber的顶点作为凸轮pavelo的模型，只使用一小部分的时间。到目前为止，我们的实现仅包括基本步骤由于它已经显示出很好的性能，我们打算继续使用新技术（如路径重连）来改进它。我们还旨在调整启发式来解决不同的排序问题，如限制性重新着色问题[10]。引用[1] Bar-Yehuda河，I. Feldman和D.林志光，一种改进的凸树近似重，理论计算。系统43（2008），pp.3比18[2] 邦迪，J. A.和联合S. R. Murty，[3] Cam ppalelo，M. B、A. S. Freire，K. R. 利马山口F. S. Yella和Y. 王文，《凸形着色问题：多面体、刻面和计算实验》，数学。程序. 156（2016），pp.303-330[4] Chopra，S.，B. Filipecki，K.李，M。柳，S. Shim和M. V. Vyve，一个扩展的形式化的凸重新着色问题的树，数学程序。165（2017），pp. 529-548.[5] De mBasar，J.，多个数据集上分类器的统计比较，J。 马俊雄学习. Res. 7（2006），pp.1-30[6] 去你的，B.，A. Jüttner和P. Kov 'acs，LEMON-anO penSourceC++GraphTemplateLibrary，Electron.注意Theor。Comput. Sci. 264（2011），pp.23[7] Feo，T.A. 和M.G. C. 贪婪随机自适应搜索程序，J。全球优化6（1995），pp. 109-133[8] Frenkel，Z.，Y.基特岛Izhaki和S. Snir，凸重新着色作为一种进化标记，分子。系统进化107（2017），pp.209-220[9] 戈德堡湖，澳-地一、P. W.戈德堡角A. Phillips，E. Sweedyk和T. Warnow，Minimizing phylogeneticnumber to find good evolutionary trees，in：Combinatorial Pattern Matching（1995）。102-127[10]Kammer，F.和T.Tholey，最小凸染色的复杂性，离散应用。数学160（2012），pp. 810-833[11] L 'o pez-Ib'anpezez，M.， J. 杜布瓦拉科斯特湖 P'erezC'aceres，T. Stutzle和M. Birattari，I ra cePackage：自动算法配置的迭代竞赛，Oper。Res. 透视。3（2016），pp.43比58[12] 莫兰，S。和S. Snir，Convex Recolorings of Strings and Trees：Definitions，Hardness Results andAlgorithms，J.Comput. 系统Sci. 74（2008），pp.850-869美国邮政Dantas等人/理论计算机科学电子笔记346（2019）379391[13] Moran ， S. ， S. Snir 和 W.- K. 树 和 网 络 的 部 分 凸 重 着 色 ： 紧 上 界 和 下 界 ， ACM Trans.Algorithms7（2011），p.四十二。[14] 伊 卡 拉 山口F. 美 国 ， “Graph Colorings and Digraph Su b divisions，”博 士 论 文 ， InstitutodeMatem'aticae E stat'ıstica，Uni veradadedeSaoPaulo（2017）.[15] Resistance，M. G.和C. C. Ribeiro，283-319