算法设计与分析 实验三 回溯法求解地图填色问题(下)

简介: 算法设计与分析 实验三 回溯法求解地图填色问题

(4)矩阵记录可行解避免多次搜索


①算法描述:

在进行回溯搜索过程中,每次对点进行颜色合法性检查时都要遍历当前点,每一次每一层的搜索都需要检查合法性,成千上万次操作将大大提高这部分的时间消耗。而每次拓展节点时,新节点与原节点都会有公共边,因而点的可用性不会差别特别大,因此,可以设计一个数组对每个点的可用性进行检测并存储,从而避免多次对可用性的检测。


②具体实现:

为了存储每个点的颜色可用性,设置了colorMatrix进行存储。其中,colorMatrix[i][1]表示第i点1颜色是否可用(可用为1,反之为0),colorMatrix[j][2]表示第j点2颜色是否可用(可用为1,反之为0)。特殊地,colorMatrix[i][0]表示第i点共有几种可用颜色

因此对于每个点回溯时,只需通过colorMatrix遍历点i的可用颜色,再删除邻接点colorMatrix可用颜色并继续搜索即可。完成搜索则恢复该可用颜色即可。


a.搜索函数:


//backtrack to search
void backtrack(Map &map, int index, int rest) {
    //judge if find the solution
    if (rest == 0) {
        //store the solution
        result.push_back(vector<int>(map.colorArray + 1, map.colorArray + 1 + map.vNum));
        for (int i = 0; i < map.vNum; i++) {
            ofs << result[result.size() - 1][i];
        }
        ofs << endl;
        return;
    }
    //dissatisfied solution: check each valid color
    for (int i = 0; i < map.colorType; i++) {
        if (map.colorMatrix[index][i + 1] == 0) {
            //if the color solution is invalid
            if (deleteColor(map, index, i) != -1) {
                recoverColor(map, index, i);
                continue;
            }
            //search point[index]
            map.colorArray[index] = i;
            //backtrack to search
            backtrack(map, next(map), rest - 1);
            //recover the validation of the color and return
            map.colorArray[index] = -1;
            recoverColor(map, index, i);
        }
    }
    return;
}

首先回溯函数中对是否为解进行判断,如果是解,则将结果存入结果容器中,并直接返回。

如果当前不为可行解,且当前点没有合法可用颜色,则进入下一个点的判断。如果有可用颜色,则对当前节点的可用颜色进行拓展,并使用colorMatrix对颜色情况进行记录,搜索前删除该可用颜色,搜索后恢复该可用颜色。


b.恢复颜色函数:

void recoverColor(Map &map, int index, int color) {
    MapNode candidate = map.vArray[index];
    MapNode *tmp = candidate.next;
    while (tmp) {
        int candidateIndex = tmp->value;
        //if the point is uncolored and its adjacent point is not colored with that color
        if (map.colorArray[candidateIndex] == -1 && map.colorMatrix[candidateIndex][color + 1] == 1 + index) {
            map.colorMatrix[candidateIndex][color + 1] = 0;
            if (map.colorMatrix[candidateIndex][0] == 0) {
                map.colorMatrix[candidateIndex][0]++;
                return;
            }
            map.colorMatrix[candidateIndex][0]++;
        }
        tmp = tmp->next;
    }
}

对于每个搜索的点,当他下一个邻接点不为空时,则进行搜索。首先判断当该点未涂色且该点邻接点颜色合法时,则可以认为该点的当前涂色合法,将colorMatrix对应值加一并返回即可。


c.删除颜色函数:


int deleteColor(Map &map, int index, int color) {
    MapNode candidate = map.vArray[index];
    MapNode *tmp = candidate.next;
    while (tmp) {
        int candidateIndex = tmp->value;
        //if the point is uncolored and its adjacent point is not colored with that color
        if (map.colorArray[candidateIndex] == -1 && map.colorMatrix[candidateIndex][color + 1] == 0) {
            map.colorMatrix[candidateIndex][color + 1] = 1 + index;
            map.colorMatrix[candidateIndex][0]--;
            if (map.colorMatrix[candidateIndex][0] == 0)
                return candidateIndex;
        }
        tmp = tmp->next;
    }
    return -1;
}


对于每个搜索点,如果该点的下一个邻接点的可涂色颜色为0,则返回当前点的序号,如果不存在下一个邻接点,则返回-1。对于邻接点可涂颜色不为0的情况,则更新邻接点可涂颜色直至搜索到末端点。


(5)数据结构的选择:

①算法描述:

对于储存图的数据结构,常见的有邻接表和邻接矩阵两种。因此如何选择合适的数据结构也将从一定程度上节省程序的运行时间。


对于邻接矩阵,寻找相邻区域时需要遍历所有区域;对于邻接表而言,可以直接获取相邻区域。由于本地搜索程序与深度优先搜索类似,而采用邻接表的深度优先搜索的时间复杂度为O ( n + e ) ( e 为 边 数 ) O(n+e)(e 为边数)O(n+e)(e为边数),采用邻接矩阵的深度优先搜索的时间复杂度为O ( n 2 )。因此在搜索时,可以采用邻接表进行搜索。但对于邻接表而言,对于一些数据的存储没有邻接矩阵方便,因此可以采用邻接矩阵和邻接表共用的方式对图结构进行存储。

②具体实现:


struct Map {
    int vNum;          //number of vertex
    MapNode *vArray;   //adjacency list
    int *colorArray;   //store type of color, -1 for uncolored
    int colorType;     //type of color
    int *oldToNew;     //change after sort by degree, origin id-> new id
    int *newToOld;     //change after sort by degree, new id-> origin id
    bool **matrix;     //adjacency matrix
    int **colorMatrix; //store the validation of each point and number of valid colors
};


使用colorMatrix二维矩阵存储各个点的颜色可用情况,使用vArry存储邻接表,使用colorArray存储点的涂色情况。

③运行并测试:

对给定的大数据(450点5色)进行填涂,并将可行解全部输出,将程序运行20次取时间平均值做表如下:


优化前 优化后
240.5s 169.4s


这证明,使用邻接表存储数据并进行优化是有效的优化方式。


3、时间与效率分析:


利用以上算法优化,完成不同规模下数据的试涂色记录并整理如下(搜索结果在‘result’文件夹中):


(1)三组数据的涂色:


①得到第一个可行解:



450点5色
450点15色 450点25色
时间消耗 860.1ms 386.4ms 210.6ms



可以看到随着可用颜色的增多,涂色消耗时间依次缩短。这是由于可用颜色更多,搜索过程中更容易搜索到可行解,无需进行多次搜索就可以找到可行解。

②得到全部可行解(15色和25色全部可行解个数超过10^9无法一定时间内得到完备搜索结果):



450点5色
时间消耗 61.199s
可行解个数 3840


可以看到采用贪心剪枝,置换剪枝,向前探查剪枝,矩阵记录并选择邻接表进行数据存储这5种优化后,实现了从最开始未优化时短时间内无法完成完备搜索变为在一分钟左右的时间即可完成全部搜索,算法的效率得到极大提升。


(2)自行生成地图涂色并分析:


通过随机数,自行生成了不同规格的地图,对于每个地图,均将程序运行10次并取平均值作为实际值。对于每次比较时,均需要保证其余变量的值不变,在有解的情况下,分析统计作表如下:


①图规模对运行时间的影响:


100点5色 200点5色 300点5色 400点5色
时间消耗 1,943ms 10,673ms 24,164ms 60,561ms


ef5669d18a1241f78491e758971af5b9.png


图的规模极大影响了搜索的规模,规模小的图要比规模大的图的搜索时间小的多。

通过上图,可以看到,当地图规模成线性级增长时,时间消耗大致成指数型增长。并且,随着数量级的增长,指数增长速率放缓,这是因为多种剪枝策略对大数据下优化作用更明显。

②合法涂色数对运行时间的影响:


200点5色 200点7色 200点9色
时间消耗 10.7s 74.6s 592.1s


3ffefba3f0e745aa9ee0b264434bec24.png


合法的颜色数极大的影响了搜索的规模,合法颜色少的图要比合法颜色多的图的搜索时间小的多。

通过分析可知,若对于某图涂色的存在可行解向量image.pngimage.png存在n ! 种等效可行解向量。因此,当合法颜色数增多时,可行解数量大致成阶乘型(指数)增加。

此外,随着合法颜色数的增长,指数增长速率增大,这是因为由于合法颜色数的增加导致可剪枝数降低,搜索树成指数级增长,剪枝策略的优化作用减弱。


③图的边密度对运行时间的影响(在400点5色下进行测试):


边密度5% 边密度7.5% 边密度10%
时间消耗 60,561ms 10,832ms 736ms


e77cd05e751b483a942464c55a47dc97.png

边密度影响了可行解的个数,也影响了剪枝的效率。边密度越大,剪枝效率越高。边密度越小,搜索树的每一支就会更深。

从上图以及上表中可以看出,随着边密度的提高,时间消耗指数级急速降低。这是剪枝效率大大提升的原因。

④图的连通分量对运行时间的影响(在400点5色下进行测试):


联通分量 1 3 5
时间消耗 60,561ms 54,831ms 48,265ms


b540bb6c91aa4dcea17c6337cb34e683.png

联通分量从一定程度上影响了搜索树的规模。当搜索过程中搜索完一个极大连通图后,搜素会从下一个极大连通图的最大度节点开始搜索,而不是从原节点上继续拓展,类似于重新从根节点伸展出一颗新的搜索树,降低了上一级的节点拓展。从一定程度上节省了时间。

通过分析上图以及上表,可以看到连通分量确实对图的运行时间有影响,并且连通分量越大,算法运行时间越短。


四、实验结论或体会


常规算法的算法效率往往较低,需要进行优化

对于回溯搜索算法,搜索时应优先选择限制较多的分支进行拓展搜索

可以通过数学方法对算法进行优化。例如本实验中借助图论中轮换的思想完成了优化。

除了算法本身,选择合适的数据结构也可以在一定程度上降低程序的运行时间。

算法优化过程中,算法的正确性验证必不可少。在本题中,每种优化策略都经过了理论和实际进行验证。


五、思考


轮换替换思想的推广:


1、算法描述:

通过对运行结果中可行解的分析以及对涂色逻辑的分析我们可以知道,对于m个合法颜色,规模为n的图的一个解向量如果为


image.png


也都为可行解。

image.png

此外,对于不可行的搜索节点也同理,当找到搜索树的某一枝无解后,可以利用轮换,将所有等效解全部剪枝剪掉,这大大降低了程序的运行时间。


2、运行并测试:


采用轮换进行剪枝的策略和上面几种已经介绍的剪枝策略,对450点5色地图进行涂色并计时,发现仅需要不到一秒的时间即可完成全部3840个点的搜索,与之前大约一分钟左右的时间相比,算法效率得到极大提升。


附录


完成本次实验后课余时间,尝试了一些其他的优化手段,并重新写了代码。算法效率得到极大提升,可以在50ms内求解出450个点的5种颜色的全部3840个可行解,将代码附上,供大家参考。


#include <iostream>
#include <time.h>
using namespace std;
#define COLOR 5    //颜色数
#define VERTEX 90     //点数
#define EDGE 500   //边数
class Vertex {
public:
    int color;
    int state[COLOR + 1];  //颜色状态,1为可选,非1为不可选
    int choice;  //可选颜色数,即state中1的数量
    int restrain;  //相邻数量
    Vertex() {
        color = 0;
        for (int i = 0; i < COLOR + 1; ++i) {
            state[i] = 1;
        }
        choice = COLOR;
        restrain = 0;
    }
};
int map2[VERTEX + 1][256];  //图的邻接表
long long int sum = 0;   //记录解的个数
long Start;
long End;
int ColorFirst(Vertex *S) {
    int maxRestrain = 0, maxIndex = 0;
    for (int i = 1; i <= VERTEX; ++i) {
        if (S[i].restrain > maxRestrain) {
            maxRestrain = S[i].restrain;
            maxIndex = i;
        }
    }
    S[maxIndex].color = 1;
    maxRestrain = 0;
    int next = 0;
    for (int k = 1; k <= map2[maxIndex][0]; ++k) {
        int j = map2[maxIndex][k];
        S[j].choice--;
        S[j].restrain--;
        S[j].state[1] = -maxIndex;
        if (S[j].restrain > maxRestrain) {
            maxRestrain = S[j].restrain;
            next = j;
        }
    }
    return next;
}
int getNext(Vertex *S) {
    int min = COLOR;
    int next = 0;
    for (int i = 1; i <= VERTEX; ++i) {
        if (S[i].color == 0) {
            if (S[i].choice == min) {
                if (S[i].restrain > S[next].restrain) {
                    min = S[i].choice;
                    next = i;
                }
            } else if (S[i].choice < min) {
                min = S[i].choice;
                next = i;
            }
        }
    }
    return next;
}
//搜索函数
int DFS(Vertex *S, int now, int count, int used) {
    if (count == VERTEX) //到达叶子,找到一个着色方案
    {
        sum += S[now].choice;
        /*if (sum > 1000000000) {
            End = clock();
            cout << End - Start << endl;
            exit(1);
        }*/
        return S[now].choice;
    } else {
        int s = 0;
        for (int i = 1; i <= COLOR; i++) {
            if (S[now].state[i] == 1) {
                int ss = 0;
                S[now].color = i;
                bool isNew = i > used;
                //剪枝
                for (int k = 1; k <= map2[now][0]; ++k) {
                    int j = map2[now][k];
                    if (S[j].color == 0 && S[j].state[i] == 1) {
                        /*S[j].state[i] = -now;
                        S[j].choice--;
                        S[j].restrain--;*/
                        if (S[j].choice == 1) {
                            goto BACK;
                        } else {
                            S[j].state[i] = -now;
                            S[j].choice--;
                            S[j].restrain++;
                        }
                    }
                }
                if (isNew)
                    ss = DFS(S, getNext(S), count + 1, used + 1);
                else
                    ss = DFS(S, getNext(S), count + 1, used);
                BACK:
                for (int k = 1; k <= map2[now][0]; ++k) {
                    int j = map2[now][k];
                    if (S[j].state[i] == -now) {
                        S[j].choice++;
                        S[j].restrain++;
                        S[j].state[i] = 1;
                    }
                }
                S[now].color = 0;
                if (isNew) {
                    s += ss * (COLOR - used);
                    sum += ss * (COLOR - used - 1);
                    break;
                }
                s += ss;
            }
        }
        if (sum > 100000000) {
            End = clock();
            cout << End - Start << endl;
            exit(1);
        } else
            return s;
    }
}
int main() {
    Vertex S[VERTEX + 1];
    FILE *fp;
    int command;
    cin >> command;
    if (command == 1) {
        if ((fp = fopen("G:\\MapData\\MapR_5_90_500.txt", "r")) == NULL)  //打开文件
        {
            printf("Can not open file!\n");
            exit(1);
        }
    } else if (command == 2) {
        if ((fp = fopen("G:\\MapData\\MapR_5_100_500.txt", "r")) == NULL)  //打开文件
        {
            printf("Can not open file!\n");
            exit(1);
        }
    } else if (command == 3) {
        if ((fp = fopen("G:\\MapData\\MapR_5_110_500.txt", "r")) == NULL)  //打开文件
        {
            printf("Can not open file!\n");
            exit(1);
        }
    } else if (command == 4) {
        if ((fp = fopen("G:\\MapData\\MapR_5_120_500.txt", "r")) == NULL)  //打开文件
        {
            printf("Can not open file!\n");
            exit(1);
        }
    }
    int u, v;
    char ch;
    for (int i = 1; i <= EDGE; i++) {
        fscanf(fp, "%c%d%d\n", &ch, &u, &v);
//        map[u][v] = map[v][u] = 1;
        map2[u][0]++;
        map2[u][map2[u][0]] = v;
        map2[v][0]++;
        map2[v][map2[v][0]] = u;
        S[u].restrain++;
        S[v].restrain++;
    }
    cout << "OK" << endl;
    fclose(fp);
    Start = clock();
    int a = DFS(S, getNext(S), 1, 0);
    End = clock();
    cout << "TIME:" << End - Start << endl;
    cout << "ANSWER:" << a << endl;
    return 0;
}
相关文章
|
1月前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
58 4
|
23天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
1月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
105 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
30天前
|
算法
PID算法原理分析
【10月更文挑战第12天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
1月前
|
算法
PID算法原理分析及优化
【10月更文挑战第6天】PID控制方法从提出至今已有百余年历史,其由于结构简单、易于实现、鲁棒性好、可靠性高等特点,在机电、冶金、机械、化工等行业中应用广泛。
|
1月前
|
算法 安全 Go
Python与Go语言中的哈希算法实现及对比分析
Python与Go语言中的哈希算法实现及对比分析
40 0
|
1月前
|
算法
计科一二班算法数据结构实验9答案
计科一二班算法数据结构实验9答案
14 0
|
26天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
12天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。