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

github地址

禁忌搜索算法原理及实现

图着色问题

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

禁忌搜索算法

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

代码实现

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

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

核心代码实现

  1. findmove实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    //找最佳禁忌或者非禁忌移动
    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实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //更新值
    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. 结果
    tabucol-result

禁忌算法注意点

  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. 随机数

    1
    2
    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. 按行读取文件,并按空格分割

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /* 
    @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++内置类型最大值宏定义

    1
    2
    #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. 二维数组申请释放
    指针:
    申请:

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

    释放:

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

    vector:

    1
    2
    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级别优化
    编译运行:

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

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

参考

  1. 华科,吕志鹏教授,启发式优化
-------------本文结束感谢您的阅读-------------
鼓励鼓励!