禁忌搜索算法解决图着色问题

github地址
个人博客地址

禁忌搜索算法原理及实现

图着色问题

对给定图G=(V,E)的每个顶点着色,要求每个相邻的顶点不同色，求最小需要的颜色数。

禁忌搜索算法

禁忌搜索算法，是一种局部搜索算法，通过采用禁忌表，逃脱了局部最优解，得到全局最优解。禁忌搜索算法先针对问题初始化一个解决方案S，和目标值O。下一步在S邻域中挑选可以使得目标值O最小的禁忌或者非禁忌移动。同时将本次移动记录在禁忌表中，设定一个禁忌值tt，当迭代次数小于禁忌值时本次移动属于禁忌移动，否则属于非禁忌移动。算法终止条件是求出解，或者达到设定的迭代次数。

tt=iter+f+r(10)$$tt=iter+f+r(10)$$

其中 iter是迭代次数，f是初始冲突值，也是需要优化的目标函数，r是1-10的随机值。

算法流程：
（1）生成初始解决方案S，计算冲突值f(S)
（2）初始化邻接颜色表M,禁忌表T,历史最佳冲突best_f
（3）判断是否满足终止条件不满足继续执行，满足则停止
（4）构造S的邻域，用N(S)表示
（5）计算领域N(S)中所有一步移动的△值
（6）找到具有最小△值的最佳禁忌或者非禁忌移动
（7）如果满足愿望条件则执行最佳禁忌移动，否则执行最佳非禁忌移动
（8）更新解决方案，冲突f，历史最佳冲突best_f，禁忌表，邻接颜色表
（9）执行步骤（3）

邻接颜色表M：NXK的数组,N为结点数，K为颜色数。M[i][j]表示i结点的邻接节点中,具有j颜色的节点的数目。
每次移动，冲突增量△f = M[i][j]-M[old_i][old_j]，等于新颜色的M[i][j]减去旧颜色的M[i][j]，邻接颜色表
i的所有邻接节点，新颜色j列的值+1，旧颜色old_j列的值-1。

禁忌表T：NXK的数组,NXK的数组,N为结点数，K为颜色数。初始为0,每次迭代从i的旧颜色old_j移动到新颜色j,T[i][j]
的值设定为一个禁忌值tt(如前所述)。

领域N(S): S的下一次移动所有的可能结果，对于本问题就是依次移动每个节点至除了当前颜色的每个颜色，如果当前颜色与邻接节点的颜色冲突已经为0则不需要移动。

愿望条件：最佳禁忌移动的目标值小于历史最佳冲突best_f且小于当前非禁忌移动的值,则可接受禁忌移动的值，否则接受非禁忌移动的值。

代码实现

TabuSearch(){ 
    int u, vi, vj, iter = 0;
    Initialization() ;//初始化
    while( iter < MaxIter) {
        FindMove(u,vi,vj,delt) ;//找到最佳禁忌移动或者非禁忌移动
        MakeMove(u,vi,vj,delt) ;//更新相应值
    }
}

备注：单纯的禁忌搜索算法求解图着色，可不用设定其迭代次数，一直运行即可。

核心代码实现

1. findmove实现

   //找最佳禁忌或者非禁忌移动
   void findmove() {
       delt = 10000;//初始为最大整数
       int tmp;//临时变量
       int tabu_delt = 10000;
       int count = 0, tabu_count = 0;
       int A = best_f - f;
       int c_color;//当前结点颜色
       int *h_color;//邻接颜色表行首指针
       int *h_tabu;//禁忌表行首指针
       int c_color_table;//当前结点颜色表的值
       for (int i = 0; i<N; i++) {//11.3
           c_color = sol[i];//6.1%
           h_color = adj_color_table[i];
           c_color_table = h_color[c_color];
           if (h_color[c_color] > 0) {//17.6
               h_tabu = tabutenure[i];
               for (int j = 0; j < K; j++) {
                   if (c_color != j) {//cpu流水线
                       //非禁忌移动
                       tmp = h_color[j] - c_color_table;
                       if (h_tabu[j] <= iter) {//22.6
                           if (tmp <= delt) {//分支预判惩罚 6.0
                               if (tmp < delt) {
                                   count = 0;
                                   delt = tmp;
                               }
                               count++;
                               equ_delt[count - 1][0] = i;
                               equ_delt[count - 1][1] = j;
                           }
                       }else {//禁忌移动
                           if (tmp <= tabu_delt) {//6.0
                               if (tmp < tabu_delt) {
                                   tabu_delt = tmp;
                                   tabu_count = 0;
                               }
                               tabu_count++;
                               equ_tabudelt[tabu_count - 1][0] = i;
                               equ_tabudelt[tabu_count - 1][1] = j;
                           }
                       }
                   }
               }
           }
       }
       tmp = 0;
       if (tabu_delt<A && tabu_delt < delt) {
           delt = tabu_delt;
           tmp = rand() % tabu_count;//相等delt随机选择
           node = equ_tabudelt[tmp][0];
           color = equ_tabudelt[tmp][1];
       }
       else {
           tmp = rand() % count;//相等delt随机选择
           node = equ_delt[tmp][0];
           color = equ_delt[tmp][1];
       }
   }

2. makemove实现

   //更新值
   void makemove() {
       f = delt + f;//更新冲突值
       if (f < best_f) best_f = f ;//更新历史最好冲突
       int old_color = sol[node];
       sol[node] = color;
       tabutenure[node][old_color] = iter + f + rand() % 10 + 1;//更新禁忌表
       int *h_graph = g[node];
       int num_edge = v_edge[node];
       int tmp;
       for (int i = 0; i<num_edge; i++) {//更新邻接颜色表
           tmp = h_graph[i];
           adj_color_table[tmp][old_color]--;
           adj_color_table[tmp][color]++;
       }
   }

3. 结果
   

禁忌算法注意点

1. 历史最优冲突best_f，取最小值，取其他值，可能使得收敛过慢。
2. 采用迭代次数与禁忌表比较，而不是每次迭代禁忌表非零值-1，然后比较与0的大小，增加了时间复杂度。

实现过程中做的优化

代码优化

1. 采用邻接表
   邻接表的时间复杂度比二维数组的时间复杂度更低，如果边少，会低很多。
   代码中做法是：采用二维数组，并另使用一个一维数组存放每行的长度。
2. 采用数组
   vector耗时是数组的5.6倍（对于此问题而言）。
   struct耗时也比数组多。
3. 二维数组按行访问
   c++中二维数组按行存储，为了提高cpu Cache命中率，实现按行访问。
   代码中的具体做法是：外重循环取二维数组行首地址，内重循环使用行首地址访问。
4. 提高分支预判命中
   循环内部，让分支条件尽可能为真，或为假，有规律，让cpu可命中。
   代码中的具体做法是：if(c_color!=j)这是大部分为真的情况。

编译优化

1. g++ tabu.cpp O2 -o tabu,采用O2（代码速度)最快编译。vs->属性->c/c++->优化->O2。

工具优化

1. 采用vs的profile查找耗时的代码，分析优化

实践中用到的知识

1. 随机数

   srand((unsigned)time(NULL));
   rand();

   time(NULL)返回64bit时间，rand()超int范围，采用debug x64后正常。
   真实原因是指针访问错误，滞后的原因。
   rand()在每次被调用的时候，它会查看：
   1） 如果用户在此之前调用过srand(seed)，给seed指定了一个值，那么它会自动调用srand(seed)一次来初始化它的起始值。
   2） 如果用户在此之前没有调用过srand(seed)，它会自动调用srand(1)一次。
   注：秒的随机不够精确，程序运行很快秒随机在1000个循环之内可能不会改变，使用毫秒clock()，微妙随机。

2. 按行读取文件，并按空格分割

   /* 
   @in, src: 待分割的字符串 
   @in, delim: 分隔符字符串 
   @in_out, dest: 保存分割后的每个字符串 
   */  
   void split(const string& src, const string& delim, vector<string>& dest)  
   {  
       string str = src;  
       string::size_type start = 0, index;  
       string substr;  
       index = str.find(delim, start);    //在str中查找(起始：start) delim的任意字符的第一次出现的位置  
       while(index != string::npos)  
       {  
           substr = str.substr(start, index-start);  
           dest.push_back(substr);
           start = index + 1;  
           index = str.find(delim, start);    //在str中查找(起始：index) 第一个不属于delim的字符出现的位置  
       }  
       substr = str.substr(start, index);  
       dest.push_back(substr);
   } 
   int main(){
       ifstream infile("test.txt", ios::in);  
       vector<string> results;  
       string delim(" ");  
       string textline;  
       if(infile.good())  
       {  
           while(!infile.fail())  
           {  
               getline(infile, textline);  
               split(textline, delim, results); 
           }  
       }  
       infile.close();
       return 0;
   }

   参考:
   string.find
   string.find_first_of
   读取文件行并分割行中字符串：C/C++以及python实现

3. C++内置类型最大值宏定义

   
   #include<climits>
   
   INT_MAX

   参考：
   C++内置类型最大值宏定义

4. 0xC0000005: 读取位置 0x0000000000000000 时发生访问冲突
   0xC0000005: 读取位置 0x0000000000000040 时发生访问冲突
   访问冲突原因：
   指针越界：将指针数据依次输出，模拟访问

5. 内存分配异常处理
   try{}catch(const bad_alloc &e){}

6. Critical error detected c0000374
   有时候因为malloc / new / whatever检测到堆损坏，往往这个损坏在程序中以前就已经发生了，但是崩溃一直延迟到下一次调用new / malloc。
   错误很可能是数组越界，指针地址损坏等引起。可通过模拟访问输出每个地址的数据，进行检查。

7. 程序已退出,返回值为 0 (0x0)
   引用头文件时多加一个#include “stdlib.h ”
   在return 0前加一个system(“pause”);

8. 输出到文件的数据过多时
   为避免影响程序时间，可采用采样输出，比如隔10000输出一次

9. 二维数组申请释放
   指针：
   申请：

   int **array = new int*[N];
   for(int i = 0;i < N;i++)
       array[i] = new int[K];

   释放：

   for(int i = 0;i < N;i++)
       delete []array[i]
   delete []array;

   vector:

   vector<vector<int>> v;
   v = new vector(M,vector<int>());

10. a debugger is attached to but not configured to debug this unhandled exception. to debug this exception detach the current debugger in Visual Studio
    如果Visual Studio配置为只调试托管的异常，并且您获得的异常是本地的，则可能会出现此警告。 转到您的项目的属性，调试选项，并将调试器类型从托管只更改为混合（托管和本机）。

11. cpu cache对程序性能的影响
    由于计算机的内存是一维的，多维数组的元素应排成线性序列后存入存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间的关系不变。
    所以采用顺序存储方法表示数组。c/c++二维数组按行优先存储，所以尽量让二维数组按行访问优先，避免跨行访问，提高cpu cache命中率。
    以矩阵乘法为例，了解cpu cache对程序性能的影响
    cpu cache对程序性能的影响
    如何用 Cache 在 C++ 程序中进行系统级优化（二）
    如何用 Cache 在 C++ 程序中进行系统级优化（一）

12. 代码里写很多if会影响效率吗?
    现代处理器先执行if条件，如果不对在回滚切换到其他分支，所以尽量让if语句,要么一直true,要么一直false，有规律可循
    代码里写很多if会影响效率吗?
    分支预判代价
    快速和慢速的 if 语句：现代处理器的分支预测

13. vs c++连接器配置优化
    设置：项目->属性->c/c++->优化->优化->/O2
    一般使用/O2而不使用/Ox
    /O2与/Ox区别
    vs 优化
    Microsoft Visual Studio C++ 编译器选项设置

14. “/Ox”和“/RTC1”命令行选项不兼容 或者 ml.exe 退出
    “/Ox”和“/RTC1”命令行选项不兼容,将/RTC1改为默认值，或者禁用优化

15. cpu cache介绍
    L1,L2,L33级别缓存：
    L1一个核两个一个指令一个数据
    L2一个cpu一个
    L3同一卡槽的cpu共享一个
    计算机体系结构2—-缓存cache

16. java/c++谁快
    java虽然解释执行，但可针对特定处理器优化。下面两篇文章说java快。
    但相同程序开了O2优化后，C++比java快。
    Java VS C/C++ 运行速度的对比
    c++vsjava

17. 安装g++编译器尝试g++O3级别优化
    编译运行：

    g++ tabu.cpp -O3 -o tabu
    tabu.exe

    O2比O3快，但是O3比vs的O2快
    windows 下 gcc/g++ 的安装
    GCC/G++乱码的完美解决方案

参考

1. 华科，吕志鹏教授，启发式优化