# 图染色算法

**Repository Path**: z517359234/graph-coloring-algorithm

## Basic Information

- **Project Name**: 图染色算法
- **Description**: 启发式算法，HEAD算法，MACol算法，禁忌搜索，图染色。
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2023-09-16
- **Last Updated**: 2023-09-16

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 图染色算法-HEAD' + MACol

#### 项目说明： 使用java编写的图染色问题算法
#### 项目环境： jdk8
#### 项目参数： 自行调整相关算法类中static变量

#### 启动说明： 原始图文件路径为/resource/DSJC500.5.col,如有需要可自行替换。在/src目录下的三个类可以直接启动main函数

## 问题简介：
   图着色问题（Graph Coloring Problem, GCP） 又称着色问题，是最著名的NP-完全问题之一。道路着色问题（Road Coloring Problem）是图论中最著名的猜想之一。
图的m-着色判定问题——给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色?
图的m-着色优化问题——若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的最小色数m的问题称为m-着色优化问题。


HEAD算法：
该算法的基本思想如下：
生成两个初始解，对这两个解进行正反两次GPX操作。GPX交叉之后生成的解我们用来进行禁忌搜索，将本轮最优的解存进精英解中，再将精英解与最优解进行比较，确定最优解，之后在满足某些情况的条件下，将解1替换成上一轮的精英解，执行这个过程直到满足退出条件（轮数达到或者冲突为0）。


# 参考文献：
[1] Hertz, A., de Werra, D.: Using Tabu search techniques for graph coloring.Computing 39(4), 345–351(1987)
[2] Zhipeng Lü , Jin-Kao Hao: A memetic algorithm for graph coloring 
European Journal of Operational Research 203 (2010) 241–250
[3] Laurent Moalic , Alexandre Gondran: Variations on memetic algorithms for graph coloring problems J Heuristics (2018) 24:1–24