回溯法详解之【图着色】和【N皇后】问题

我就是我 2022-12-27 01:44 235阅读 0赞

### 文章目录 ###

*   *   *  一、回溯法
         *  二、图着色
         *   *  2.1 问题
             *  2.2 算法描述
             *  2.3 代码及测试结果
         *  三、N皇后
         *   *  3.1 问题
             *  3.2 算法描述
             *  3.3 代码及测试结果

--------------------

### 一、回溯法 ###

**回溯法**（back track method）在包含问题的所有可能解的解空间树中，从根节点出发，按照深度优先的策略进行搜索，对于解空间的某个节点，如果该节点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该节点为根节点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解，所以，适用于求解组合数较大的问题。

1.  在隐式树上的深度优先遍历
    
     *  状态转换方便
     *  使用深度优先遍历，直接使用了**系统栈保存结点信息**，编码更简单。这一点是广度优先遍历做不到的
     *  如果使用广度优先遍历，得自己编写结点类和使用队列
2.  理解回溯
    
     *  从深层结点回到浅层结点 ，必须“回到过去”
     *  “回溯”理解为“**状态重置**”、“撤销选择”、“回到过去”、“**恢复现场**”
     *  状态空间很大的时候，我们可能只需要其中的某些状态（一般都在叶子结点），因此全局使用一份状态变量即可
     *  在每一个结点都使用新的状态变量的时候，不必回溯
3.  善用剪枝，提前结束搜索
    
     *  提前知道此路不通，就“拐弯”，这一步操作称为剪枝
     *  搜索算法状态空间庞大，剪枝是必须的

回溯法实际上属于蛮力穷举法，当然不能指望它有很好的最坏时间复杂性，遍历具有指数阶个结点的解空间树，在最坏的情况下，时间代价肯定为指数阶。

回溯法的有效性往往体现在当问题规模n很大时，在搜索过程中对问题的的解空间树实行大量剪枝

### 二、图着色 ###

#### 2.1 问题 ####

给定无向连通图G=(V, E)，求最小的整数m，用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。输出染色后的一种可能的结果

【**应用实例**】机场停机位分配

本次算法示例测试的图结构如下所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

#### 2.2 算法描述 ####

输入：图G=(V, E)，图结点vchar，m种颜色

输出：结点对应染色情况(vchar\[i\]，color\[i\])

1.  将数组color\[n\]初始化为0
2.  k = 0
3.  while(k >= 0)
    
     *  3.1 依次考察每一种颜色，若顶点k的着色与其他顶点的着色不发生冲突，则转至步骤3.2；
        
        否则，搜索下一个颜色
     *  3.2 若顶点已全部着色，则输出数组color\[\]，返回
     *  3.3 若顶点k是一个合法着色，则k=k+1，转至步骤3处理下一个顶点
        
        3.4 否则，重置顶点k的着色情况，k=k-1，转至步骤3回溯

#### 2.3 代码及测试结果 ####

具体代码如下所示

class NoDirGraph{
        
    	char[] vchar;     //顶点
    	int[][] arc;      //邻接矩阵保存无向图边
    	int[] color;      //保存对应结点的颜色
    	
    	public NoDirGraph() {
        
    		
    	}
    	
    	public NoDirGraph(char[] vchar, int[][] arc) {
        
    		this.vchar  = vchar;
    		this.arc = arc;
    		this.color  = new int[vchar.length];
    	}
    	
    	/*** 用m种颜色给此图顶点着色 ***/
    	public void paintColor(int m) {
        
    		int k = 0;   //从第0个结点开始填色
    		int n = vchar.length;
    		while(k >= 0) {
        
    			color[k] = color[k] + 1;    //取下一种颜色
    			while(color[k] <= m) {
        
    				if(isOk(k)) {
        
    					break;
    				}else {
        
    					color[k] = color[k] + 1;  //搜索下一种颜色
    				}
    			}
    			if(color[k] <= m && k == n - 1) {
        
    				this.printColor();
    				break;
    			}
    			if(color[k] <= m && k < n - 1) {
        
    				k = k + 1;              //处理下一个结点
    			}else {
        
    				color[k--] = 0;         //回溯
    			}
    		}
    	}
    	
    	/*** 判断结点k颜色是否与其连接结点颜色冲突 ***/
    	public boolean isOk(int k) {
        
    		for(int i = 0; i < k; i++) {
        
    			if(arc[k][i] == 1 && color[i] == color[k]) {
        
    				return false;
    			}
    		}
    		return true;
    	}
    	
    	/*** 输出结点对应颜色  ***/
    	public void printColor() {
        
    		for(int i = 0; i < vchar.length; i++) {
        
    			System.out.println("(" + vchar[i] + "," + color[i] + ")");
    		}
    	}
    	
    }

主函数邻接矩阵以及调用代码如下所示

public class Main {
        
    	public static void main(String[] args){
        
    		char[] vchar = {
        'A', 'B', 'C', 'D', 'E'};
    		int[][] arc = {
        {
        0, 1, 1, 0, 0}, 
    				       {
        1, 0, 1, 1, 1},
    				       {
        1, 1, 0, 0, 1},
    				       {
        0, 1, 0, 0, 1},
    				       {
        0, 1, 1, 1, 0}};
    		NoDirGraph graph = new NoDirGraph(vchar, arc);
    		graph.paintColor(3);
    		
    	}
    }

程序输出结果以及可视化后如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

### 三、N皇后 ###

#### 3.1 问题 ####

在nxn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同一斜线上，输出符合条件的结果数

【**解题思路**】显然，棋盘的每一行必须摆放一个皇后，我们用一个大小为n的整型数组x\[\]来保存每一行的皇后保存的列位置，若对于皇后i和皇后j，它们不能处于同一列（x\[i\] != x\[j\]），不能处于同一斜线上，即斜率不能为1或者-1（|i - j| !=|x\[i\] - x\[j\]|），判断冲突函数为isclash（）

#### 3.2 算法描述 ####

输入：皇后的个数n

输出：解个数

1.  `初始化解向量x[n] = {-1,..., -1}`
2.  `k = 1`
3.  `while（k >= 1）`
    
     *  3.1 把皇后k摆放在下一列的位置，即x\[k\]++
     *  3.2 从x\[k\]开始依次考察每一列，如果皇后k摆放在x\[k\]位置不发生冲突，则转至步骤3.3；
        
        否则x\[k\]++试探下一列
     *  3.3 若n个皇后已经全部摆放，则输出一个解
     *  若尚有皇后没摆放，则k++，转至步骤3摆放下一个皇后
     *  若x\[k\]出界，则回溯，x\[k\] = -1, `k--`，转至步骤3重新摆放皇后k
4.  `退出循环`

#### 3.3 代码及测试结果 ####

具体见下述代码中backtrack函数

class Queue {
        
    	 public int n;
    	 private int count;
    	 private int[] x;
    	 
    	 public Queue() {
        
    		 
    	 }
    	 
    	 public Queue(int n) {
        
    		 count = 0;
    		 this.n = n;
    		 x = new int[n];
    		 Arrays.fill(x, -1);    //将位置初始化为-1
    	 }
    	 
    	 public void backtrack() {
        
    		 int k = 0;
    		 while(k >= 0) {
        
    			 x[k]++;            //在下一列摆放皇后k
    			 while(x[k] < n && isclash(k)) {
        
    				 x[k]++;
    			 }
    			 if(x[k] < n && k == n - 1) {
            //得到一个解输出摆放结果并+1
    				 count++;
    				 String board = this.getBoard();
    				 System.out.println(board);
    			 }
    			 if(x[k] < n && k < n - 1) {
          //尚有皇后未摆放，摆放下一个皇后
    				 k++;
    			 }else {
        
    				 x[k--] = -1;             //重置x[k]，回溯，重新摆放皇后k
    			 }
    		 }
    	 }
    	 
    	 private boolean isclash(int k) {
        
    		 //考察皇后k放置在x[k]位置是否发生冲突
    		 for(int i = 0; i < k; i++) {
        
    			 if(x[i] == x[k] || Math.abs(i - k) == Math.abs(x[i] - x[k])) {
        
    				 return true;       //冲突返回true
    			 }
    		 }
    		 return false;
    	 }
    	 
        /*** 输出棋局摆放信息 ***/
    	 private String getBoard() {
        
    		 StringBuffer sb = new StringBuffer();
    		 for(int i = 0; i < n; i++) {
        
    			 for(int j = 0; j < n; j++) {
        
    				 if(j == x[i]) {
        
    					 sb.append("♛");
    				 }else {
        
    					 sb.append("❤");
    				 }
    			 }
    			 sb.append("\n");
    		 }
    		 return sb.toString();
    	 }
    	 
        /*** 得到总结果数 ***/
    	 public int getCount() {
        
    		 return this.count;
    	 }
    }

主函数中调用皇后数为4代码如下

public static void main(String[] args){
        
        Queue queue = new Queue(4);
    	queue.backtrack();
    	System.out.println("共有 " + queue.getCount() + " 种解法");
    }

程序输出结果如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]

【参考资料】：《算法设计与分析（第2版）》清华大学出版社

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1702ec84adf8496f92b082b291d880b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201207103433486.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2020120710350659.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw==,size_16,color_FFFFFF,t_70#pic_center