局部搜索法求解K图染色问题（java版）

局部搜索法：K图着色问题

问题描述

对于文件给出的一个有 500 个节点的图形（n500），利用局部搜索算法，求最
少可用几种颜色能对其进行着色？并给出对应的着色方案。

问题分析：

题目的目标是用尽可能少的颜色，将500节点着色，且保证相邻节点间颜色不同；
a) 首先我们可以建立三个颜色集合C1、C2、C3，依次将图1中的每个节点随机放入一个颜色集合中；
b) 计算每个颜色集合中，产生冲突的个数之和作为初始的冲突值initConflicts；
c) 然后根据C1、C2、C3中的冲突节点对应地分别构建初始的冲突节点集合V1、V2、V3
d) 将Vi(i=1,2,3)中产生冲突的节点移动到其他颜色结合中，得到一个领域；
e) 遍历领域中的每一个解，计算conflicts，选取冲突值最小的解；
f) 若conflits大于0，执行步骤b）；否则，输出此时的颜色集合

伪代码：

$input：g[500][500]\leftarrow NodeSet,K=4$
$output:ColorSet[4]$
$bestColorSet\leftarrow InitColorSet$
$bestConflicts\leftarrow InitConflicts$
$currentConflictsSet\leftarrow InitConflictsSet$
$do$
$produce$ $the$ $local$ $solution$ $based$ $on$ $bestColorset$
$foreach$ $solution$ $in$ $N$
$currentConflicts\leftarrow choose$ $the$ $minimum$ $of$ $the$ $conflicts$ $of$ $solution$
$if$ $currentConflicts<bestConflicts$
$bestColorset\leftarrow solution$
$currentConflictsSet\leftarrow produce$ $the$ $conflictsSet$ $based$ $on$ $solution$
$while$ $bestConflicts>0$

简单实例

给定如下一个初始的图节点3着色问题，有初始着色方案如图1所示：

我们可以计算此时的冲突总数为$conflicts=2+1+1=4$,即冲突对$(1,3),(1,4),(7,8),(5,6)$.
我们得到冲突节点集合$conflictSet=\{1,3,4,5,6,7,8\}$.
若我们将节点1的颜色由蓝色变为绿色，如图2所示：

我们可以计算此时的冲突总数为$conflicts=0+1+1=2$,即冲突对$(7,8),(5,6)$.
更新冲突节点集合$conflictSet=\{5,6,7,8\}$.
依次类推，不断地改变冲突节点的颜色，直到总的冲突值为0为止。

局限性

局部搜索算法做每一次更新时，会寻找一个局部最优解，因此算法的收敛速度快，时间复杂度低；但对初始值的选择非常敏感，若初始值选择不合理，很容易陷入局部最优解，无法获得全局最优解。本文用局部搜索算法求解500个节点的图着色问题，求得最少需要4种颜色，只是一个局部最优解；
要求得全局最优解可以使用模拟退火算法，详细内容请参考：
模拟退火算法求解K图着色问题（java版）
实例：

如图所示：
a）若从起始点1开始局部搜索，只能得到局部最优解
b）若从起始点2开始局部搜索，可以得到局部最优解

图节点文本文件

K图着色500个节点文件
提取码：o177

具体实现

1.先定义一个存储节点的颜色集合类

package package_java;
import java.util.ArrayList;
public class ColorSet{
	public  ArrayList node;
	public ColorSet(){
		node = new ArrayList();
	}
	public void add(int newNode){
		node.add(newNode);
	}
	
	public void set(int index, int newNode){
		node.set(index,newNode);
	}
	
	public  int get(int index){
		return (int)(node.get(index));
	}
	
	public int remove(int index){
		return (int)(node.remove(index));
	}
	
	public boolean remove(Object o){
		return node.remove(o);
	}
	public int indexOf(int oldNode){
		return node.indexOf(oldNode);
	}
	public int length(){
		return node.size();
	}
}

2. 主类

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.ArrayList;
import package_java.ColorSet;
import java.util.Random;
public class KGraphColorLocalSearch{
	//	节点数量，颜色数量
	final static int num=500, K=4;
	//	初始化最佳冲突值
	static int bestConflicts=0;
	public static void main(String[] args){
	//	存储节点邻接矩阵
	int[][] g=new int[num][num];
	//	节点文件路径
	String path="D:\\YSA\\Algorithm\\n500.txt";
	//	读取节点文件
	if(!readNodeFile(g,path)){
		System.out.println("fail to read node file !");
	}
	else{
			//	初始化颜色集合，冲突节点集合
			ArrayList<ColorSet> colorList=InitColorSet(num,K);
			ArrayList<ColorSet> conflictsNodeSet=calculateConflicts(g,K,colorList);
			//	输出初始颜色节点集合
			//printNodeSet(K,colorList);
			int steps=0;
			while(bestConflicts>0){
				//	计算最佳的移动节点
				int minDelta=0,src=0,dest=0,moveNode=0;
				for(int i=0;i<K;++i){
					for(int k=0;k<K;++k){
						if(i==k){
							continue;
						}
						ColorSet conflictsNode=conflictsNodeSet.get(i);
						for(int j=0;j<conflictsNode.length();++j){
							int node=conflictsNode.get(j);
							//	计算从颜色i集合将节点node移动到颜色k集合后的冲突差
							int d=calculateOneMoveDeltaConflicts(g,i,k,node,colorList);
							if(d<minDelta){
								src=i;
								dest=k;
								moveNode=node;
								minDelta=d;
							}
						}
					}
					
				}
				// 冲突差值不小于0，说明已得到局部最优解
				if(minDelta==0){
					break;
				}
				// 更新冲突节点集合
				updateConflictsNodeSet(src,dest,moveNode,g,colorList,conflictsNodeSet);
				// 将moveNode从颜色src集合移动到dest集合
				moveNode(src,dest,moveNode,colorList);
				// 更新最佳冲突值，注意minDelta为负数
				bestConflicts +=minDelta;
				System.out.println("第"+(++steps)+"轮:");
				System.out.println("the best conflicts:"+bestConflicts);
				
				/*
				System.out.println(src);
				System.out.println(dest);
				System.out.println(moveNode);
				System.out.println(minDelta);
				printNodeSet(K,conflictsNodeSet);
				*/
			}
			System.out.println("the min conflicts:"+bestConflicts);
			printNodeSet(K,colorList);
				
		}
		
	}
	//	读取节点文件方法
	public static boolean readNodeFile(int[][] g, String path){
		File file=new File(path);
		if(!file.exists()){
			return false;
		}
		ArrayList<String> stringList=new ArrayList<String>();
		try{
			FileReader fr=new FileReader(file);
			BufferedReader br=new BufferedReader(fr);
			String str;
			
			while((str=br.readLine())!=null){
				stringList.add(str);
			}
			br.close();
			fr.close();
		}catch(IOException e){
			e.printStackTrace();
		}
		int m=0,n;
		for(int i=1;i<stringList.size();++i){
			String[] data=stringList.get(i).split("[ ]");
			for(int j=1;j<data.length;++j){
				n=Integer.valueOf(data[j]);
				g[m][n]=1;
			}
			++m;
		}
		return true;
	}
	public static ArrayList<ColorSet> InitColorSet(int n,int K){
		Random rand=new Random();
		rand.setSeed(2004);
		ArrayList<ColorSet> colorList=new ArrayList<ColorSet>(K);
		for(int i=0;i<K;++i){
			ColorSet color=new ColorSet();
			colorList.add(color);
		}
		for(int i=0;i<n;++i){
			int k=rand.nextInt(100)%K;
			ColorSet color=colorList.get(k);
			color.add(i);
		}
		return colorList;
	}
	//	计算从颜色s'r'c集合将节点node移动到颜色的dest集合后的冲突之差
	public static int calculateOneMoveDeltaConflicts(int[][] g, int src,int dest, int node, ArrayList<ColorSet> colorList){
		//	计算节点node在颜色src集合中的冲突数
		ColorSet color= colorList.get(src);
		int inc=0, dec=0;
		for(int i=0;i<color.length();++i){
			if(g[node][color.get(i)]==1){
				++dec;
			}
		}
		//	计算节点node在颜色dest集合中的冲突数
		color= colorList.get(dest);
		for(int i=0;i<color.length();++i){
			if(g[node][color.get(i)]==1){
				++inc;
			}
		}
		return inc-dec;
	}
	//	将moveNode从颜色src集合移动到dest集合
	public static void moveNode(int src,int dest, int node, ArrayList<ColorSet> colorList){
		ColorSet color=colorList.get(src);
		color.remove(color.indexOf(node));
		color=colorList.get(dest);
		color.add(node);
	}
	//	计算总冲突值，生成冲突节点集合
	public static ArrayList<ColorSet> calculateConflicts(int[][] g, int K, ArrayList<ColorSet> colorList ){
		ArrayList<ColorSet> conflictsNodeSet= new ArrayList<ColorSet>(K);
		for(int i=0;i<K;++i){
			ColorSet color=new ColorSet();
			conflictsNodeSet.add(color);
		}
		for(int i=0;i<K;++i){
			ColorSet color=colorList.get(i);
			ColorSet conflictNode=conflictsNodeSet.get(i);
			int conflicts=0;
			for(int j=0;j<color.length()-1;++j){
				int flag=0;
				int row=color.get(j);
				for(int k=j+1;k<color.length();++k){
					int col=color.get(k);
					if(g[row][col]==1){
						if(flag==0){
							conflictNode.add(row);
							flag=1;
						}
						conflictNode.add(col);
						conflicts +=1;	
					}
				}
			}
			bestConflicts +=conflicts;
		}
		return conflictsNodeSet;
	}
	//	更新冲突节点集合
	public static void updateConflictsNodeSet(int src, int dest, int node,int[][] g,ArrayList<ColorSet> colorList, ArrayList<ColorSet> conflictsNodeSet){
		ColorSet conflictsNode=conflictsNodeSet.get(src);
		ColorSet color=colorList.get(src);
		//	移除冲突节点集合中与node冲突的节点，注意若node=41，我们认为与41相邻且大于41的节点算41的出度；只去除出度节点
		for(int i=0;i<color.length();++i){
			int value=color.get(i);
			if(value>node && g[node][value]==1){
				conflictsNode.remove(conflictsNode.indexOf(value));
			}
		}
		//  移除冲突节点集合中node，注意可能存在多个node
		int index;
		while((index=conflictsNode.indexOf(node))!=-1){
			conflictsNode.remove(index);
		}
		conflictsNode=conflictsNodeSet.get(dest);
		color=colorList.get(dest);
		// 向冲突节点中添加node移到dest中后，所产生的冲突节点
		int flag=0;
		for(int i=0;i<color.length();++i){
			int value =color.get(i);
			if(g[node][value]==1){
				if(flag==0){
					conflictsNode.add(node);
					flag=1;
				}
				conflictsNode.add(value);
			}
		}		
	}
	//	输出节点集和
	public static void printNodeSet(int K,ArrayList<ColorSet> nodeList){
		for(int i=0;i<K;++i){
			ColorSet nodeSet=nodeList.get(i);
			int num=nodeSet.length();
			for(int j=0;j<num;++j){
				System.out.print((nodeSet.get(j)+1)+",");
			}
			System.out.println();
			System.out.println();
		}	
	}
}

本文地址：https://blog.csdn.net/shiaiao/article/details/110247210