英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
地图着色算法的性能评价
Murat Aslan*1, Nurdan Akhan Baykan1
2016.9.3 被收录
摘要：地图着色问题(GCP)在解决最小不同数量颜色图中相邻区域的着色问题方面越来越受到人们的重视。它用于解决各种现实世界的问题，如地图着色，时间表和调度。地图着色与顶点着色和边着色两方面相关联。这两种类型着色的目的是在没有冲突的情况下对整个图进行着色。因此，相邻的顶点或相邻的边缘必须用不同的颜色着色。用于GCP的最小可能颜色的数量称为色数。随着图中顶点或边数的增加，问题的复杂性也随之增加。正因为如此，每一种算法都无法找到问题的色数，而且在它们的执行次数上也可能有所不同。由于这些构造，GCP是已知的NP难问题.为了解决gcp问题，人们发展了各种启发式和元启发式方法。在本研究中，我们描述了第一次拟合(FF)、最大度排序(LDO)、威尔士和鲍威尔(WP)、关联度排序(IDO)、饱和度(DSATUR)和递归最大优先(RLF)算法。 文献中提出的顶点着色算法，并在DIMACS提供的基准图上进行了测试。从求解质量和执行次数两个方面比较了算法的性能。实验结果表明，虽然RLF和DSATUR算法对GCP是足够的，但是FF算法普遍存在不足。在寄存器分配、流量监管、Mycielski、斯坦福英里、图书和游戏图上，WP算法在最短时间内找到了最优解。另一方面，在Leighton、平坦、随机(DSJC)和Stanford Queen图上，RLF算法优于其他算法。
关键词：色数，地图着色算法。
- 介绍：
图论是一个用顶点（节点）和边（弧）[ 1 ]来表示的问题。否则，图着色问题(GCP)就是图中相邻顶点或边必须用不同颜色着色的问题[2]。GCP是Francis Gutrie提出的作为四个颜色的问题。四色问题已经被F. Gutrie描述为解决在地图上着色相邻区域使用的不同颜色的最小数目问题[3]。
地图着色与顶点着色和边着色两方面相关联。这两种类型着色的目标是在没有冲突的情况下对整个图进行着色。因此，相邻的顶点或边缘必须用不同的颜色着色。如果两个节点之间至少有一个链路(边)，则称为相邻顶点。如果检查图1，可以看到V2和V4顶点之间没有边。因此，这些顶点不是相邻的顶点。但是，图中的其他顶点是相邻的，因为彼此之间至少有一条边。在本研究的背景下，我们描述了图中的顶点着色问题。如果一个无向=(V，E)图正在检查；V是顶点集，E是边集。图1给出的图，顶点集V={v1，v2，v3，v4}，边集E={e1，e2，e3，e4，e5}。此外，R={1，2，hellip;..，k}是用于对顶点着色的一组颜色。在这种情况下，如果整个图着色而没有冲突，则使用不同颜色的最小数目来执行。它被称为“k-着色图”[4]。这种不同颜色的最小数目称为色数。色数用chi;(G)[5，6]表示。
图1.四顶点五边图
图着色问题主要用于解决基于计算机的应用和问题。图着色算法可用于解决许多工程应用和现实世界问题[2]。其中一些问题是地图着色[7]，时间表和调度问题[8，9]，寄存器分配问题[10，11]，数独问题[12]和频率分配问题[13]。
随着图中顶点或边数的增加，问题的复杂性也随之增加。正因为如此，每一种算法都无法找到问题的色数，也可能是 他们的执行时间不同。由于这些条件，GCP是已知的NP-硬问题[14].因此，为了给gcp提供更好的解决方案，许多隐式和元隐式算法都是发展起来的。 通用算法一般适用于顶点数目较少的问题。另一方面，对于复图元化算法可以找到更好的解[15]。
禁忌搜索(TS)算法[16]、模拟退火(SA)算法[17]、遗传算法(GA)[7]、蚁群算法(ACO)[18]、Cuckoo(COA)算法[15]是一些偏健康的 用于图着色问题的算法。当图G中的顶点用贪婪算法着色时，用算法的选择和着色方法来解决着色问题。这些算法被称为贪婪的阿尔戈算法。 由于算法的选择，对每个操作步骤的有效性进行了最佳选择。贪婪算法一般为顶点着色提供了有效和充分的结果[15]。在这项研究中，我们描述了First Fit（FF）[ 19 ]，最大程度排序（LDO）[ 19 ]，威尔士和鲍威尔（WP）[ 5 ]，关联度排序（IDO）[ 19 ]，递归最大的第一（RLF）[ 20 ]和程度的 文献中针对顶点着色问题提出的饱和(DSATUR)[21]算法，并在DIMACS[22]提供的基准图上进行了测试。从算法的性能和执行时间两个方面对算法的性能进行了比较。
2、顶点着色问题
如果图中的顶点用不同的颜色着色，而不考虑它们的邻接，那么这个图将使用不同颜色的数目来着色，这些颜色等于顶点的数目。然而，对于GCP来说，这不是一个好的解决方案。因为，GCP的目的是为不同颜色的相邻顶点寻找最小颜色数。
随着图中顶点或边数的增加，图的复杂度也随之增加。正因为如此，用尽可能少的不同颜色给整个图着色变得困难。因此，我们需要一些特殊的方法来着色这些图。由于特殊的方法，这些图可以用最小的不同颜色着色。
文献中的算法使用邻接矩阵对图的顶点进行着色。基于顶点之间是否存在边的条件生成邻接矩阵[1]。对于G图，顶点集显示在V={v1，v2，hellip;的集合中。.....，vn}.图的邻接矩阵由方程1生成。A表示邻接矩阵。
选择要着色的顶点的另一个重要约束是顶点度。无向无权图中顶点的度等于连接到顶点的边的总数。它用deg(Vi)[1]表示。图2中给出的图有七个顶点和九个边。
图2.七顶点图
表1显示了图2中所示的图的邻接矩阵，表2显示了该图的顶点度。
表1.邻接矩阵
表2.顶点度
3、图中的顶点着色算法
在研究的这一部分，我们描述了一些算法的步骤，已经在文献中提出的顶点着色问题。此外，这些算法将在图2中的图表上进行测试。然后给出了顶点的选取顺序和每个顶点的颜色。
3.1.第一拟合算法(FF)
对于给定的G图，顶点的集合描述为V={v1，v2，hellip;...，vn}和颜色的集合描述为R={r1，r2，hellip;、Rk}。算法的步骤：
步骤1：创建一个颜色集。(最初颜色集是空的)。
步骤2：选择V集中的第一个顶点作为起始顶点。所选顶点用第一种颜色着色，并将此颜色添加到颜色集中。
步骤3：选择V集中的下一个顶点进行着色。
步骤4：对于选定的顶点，从邻接矩阵中找到它的相邻顶点。给出所选顶点的颜色集中的颜色，而不是所选顶点的相邻顶点的颜色。如果颜色集中的颜色不适合对所选顶点着色，则定义新颜色。新颜色将添加到颜色集并指定到选定的顶点。如果存在未着色顶点，则返回到步骤3。
表3显示了图2所示的结果。表3给出了顶点及其颜色的选择顺序。根据表3，第一个着色顶点是A，颜色R1是这个顶点。最后一个着色顶点是G，给出了这个顶点的颜色R3。
表3.用FF算法求解着色图的结果
3.2.Welsh Powell算法(WP)
对于给定的图G，顶点的集合描述为V={v1，v2，hellip;，vn}和顶点的颜色集合描述为R={r1，r2，hellip;。、Rk}。WP算法的步骤：
步骤1：计算每个顶点的顶点度，并将顶点度添加到度集deg（vi）中，例如i = 1,2，hellip;，n。
步骤2：选择在度集deg(Vi)中具有最大度的未着色顶点进行着色。最初，颜色集中的第一个颜色被选择为活动颜色。
步骤3: 所选顶点用活动颜色着色。之后，从邻接矩阵中找出非着色顶点即着色顶点的不相邻顶点，这些顶点是添加到V集中（V={V1,V2,...,Vn}）。
·具有最大度的未着色顶点被选中用于着色。这个顶点用活动颜色着色。之后，该顶点的相邻顶点从lsquo;中删除。重复该步骤，直到所有顶点都在“V”集合中着色。
步骤4：如果未着色顶点的存在，在颜色设置下一个颜色作为活跃的颜色，并且返回到步骤2。否则程序终止，因为图中所有顶点都是彩色的。
表4显示了图2所示的结果。表4给出了顶点及其颜色的选择顺序。
表4.用WP算法求解着色图的结果
|
A |
B |
C |
D |
E |
F |
G |
|
|
Selected order |
7 |
4 |
1 |
6 |
5 |
2 |
3 |
|
Vertex color |
3 |
2 |
1 |
2 |
2 |
1 |
1 |
3.3.最大度排序算法
对于给定的图，顶点的集合描述为V={v1，v2，hellip;，vn}和顶点的颜色集描述为R={r1，r2，hellip;。、Rk}。LDO算法的步骤：
步骤1：创建一个颜色集(最初颜色集为空)。计算每个顶点的顶点度，并将顶点度添加到度集deg(Vi)中，使i=1,2,...,n。
步骤2：选择在度数集deg(Vi)中具有最大度的未着色顶点进行着色。首先，尝试用颜色集合中的颜色对选定的顶点进行着色。如果颜色是 是空的，或者颜色集中的颜色是不合适的(从相邻顶点使用的颜色集中的所有颜色)对顶点的颜色，定义了一个新的颜色。新的颜色被添加到颜色集，并指定到选定的顶点。
步骤3：如果存在未着色的顶点，则返回到步骤2。否则，程序将被终止。
表5显示了图2所示的结果。表5给出了顶点及其颜色的选择顺序。
表5.用IDO算法求解着色图的结果
|
A |
B |
C |
D |
E |
F |
G |
|
|
Selected order |
4 |
2 |
1 |
5 |
3 |
6 |
7 |
|
Vertex color |
3 |
2 |
1 |
2 |
2 |
1 |
1 |
3.4.关联度排序算法
对于给定的图，顶点的集合描述为V={v1，v2，hellip;，vn}和顶点的颜色集合描述为R={r1，r2，hellip;。、Rk}。I
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[464953]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
您可能感兴趣的文章
- GIS矢量地图的鲁棒水印方案外文翻译资料
- 中国相似地理位置发达地区房价影响因素的差异——以西安高新区和沣渭新区为例外文翻译资料
- 集成数据在城市土地利用变化时空动态监测的应用——以印度金奈都市为例外文翻译资料
- 全球地表水及其长期变化的高分辨率制图外文翻译资料
- 造成沿海大型城市内涝灾害的主要因素识别——以中国广州为例外文翻译资料
- 基于SFPHD框架的中国快速城市化地区城市生态系统健康综合评价方法外文翻译资料
- 基于绿地演变的未来城市地表热岛强度的多情景模拟预测外文翻译资料
- 中国大陆272个城市地面和冠层城市热岛强度的长期趋势外文翻译资料
- 与孟加拉湾热带气旋有关的中国低纬度高原远距离降雨事件外文翻译资料
- 新丰江水库流域GPM IMERG降水产品评价及水文效用研究外文翻译资料
