晓强Deep Learning的读书分享会，先从这里开始，从大学开始。大家好，我是晓强，计算机科学与技术专业研究生在读。我会不定时的更新我的文章，内容可能包括深度学习入门知识，具体包括CV，NLP方向的基础知识和学习的论文；网络表征学习的相关论文解读。当然我每天的读书心得也会分享给大家，可能涉及我们生活各个方面的书籍。我也会不定时回答大家的问题与大家一同进步，共同交流，互相监督，结交更多的朋友。希望大家多留言，多交流，多多关照。我在这里等你一同学习，如果需要相关资料也可以私信我，进入我们的群大家庭。

【晓白】今天学习效率并不如昨天高，但是我们还是要坚持下去的，努力终会有收获。今天上午抽时间写了一篇回溯法的文章。希望大家点赞，关注，支持一下。谢谢精神合伙人的支持和鼓励。如果有准备秋招的同学，也可以来看一下，对大家很有帮助。有任何疑问可以私信，获得我们大家庭的联系方式，多多沟通，共同进步。

第五章 回溯法（Backtrack）

回溯法有“通用的解题法”之称。

回溯法可以求出问题的所有解或任一解。

回溯法的基本思想：

在解空间树中，按照深度优先的策略，从根出发进行搜索。搜索每到达解空间树的一个结点，总是先判断以该结点为根的子树是否肯定不包含问题的解。

如果不包含，则跳过对该子树，一层一层地向它的祖先回溯，直到遇上一个还有未被搜索过的儿子的结点，才转向该结点的一个未曾搜索过的儿子结点，继续搜索；

否则，进入该子树，继续按深优先的策略进行搜索

一、回溯法解题过程

1.问题的解空间

应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。

例：当n=3时,有n种可选物品的0-1背包问题的解空间：

{(0,0,0), (0,1,0), (0,0,1), (1,0,0), (0,1,1), (1,0,1), (1,1,0), (1,1,1)}

2. 解空间树 通常把解空间组织成解空间树。

例如：对于n=3时的0-1背包问题，其解空间用一棵完全二叉树表示，如下图所示。

3. 搜索解空间树的过程

例1： n=3时的0-1背包问题，W={16，15，15}，p={45，25，25}，C=30。在其解空间树上搜索最优解的过程如下图所示。

例2：旅行售货员问题：某售货员要到若干城市推销商 品，已知各城市间的路程（或旅费）。他要选一条从驻地出发，经过每个城市一遍，最后回到驻地的路线使总的路程（总的旅费）最小

综上所述，回溯法解题包含以下步骤:

(1) 针对所给的问题，定义问题的解空间；

(2) 确定易于搜索的解空间结构—解空间树；

(3) 以深度优先的方式搜索解空间树，并在搜索过程中用剪枝函数（约束函数或限界函数）避免无效搜索。

例1和例2中的两棵解空间树是回溯法解题时常遇到的两类典型的解空间树。当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。

例如，n个物品的0-1背包问题相应的解空间树称为子集树。子集树通常有2n个叶结点，其结点总个数为2n+1-1。 遍历子集树的任何算法均需Ω(2n)的计算时间。

当所给的问题确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。 例如，旅行售货员问题相应的解空间树称为排列树。排列树通常有n！个叶结点。遍历子集树的任何算法均需Ω(n!)的计算时间。

二、n后问题

1. 问题描述

n后问题要求在一个n*n格的棋盘上放置n个皇后，使得她们彼此不受攻击。一个皇后可以攻击与之在同一行或同一斜线上的其他任何棋子。因此，n后问题等价于：任何两个皇后不能在同行、同列、同一斜线上。

例子：四皇后问题

给4*4棋盘的行和列分别从左到右和从上到下编号为1，2，3，4，同时也给4个皇后分别编号为1，2，3，4。由于要求不同的皇后不能放在同一行，不失一般性，可设皇后i只放在第i行。

2. 算法设计

对n后问题，可用n元组x[1:n]表示它的解。其中，x[i]表示皇后i放在棋盘的第i行的第x[i]列。

若2个皇后放置的位置分别是(i,x[i])和(k,x[k])，则约束条件为：

x[i]≠x[k] (不在同一列)

x[i]-i≠ x[k]-k ,

i+ x[i] ≠k+ x[k] (不在同一斜线)

即|i- k|≠| x[i] - x[k] |

用回溯法解n后问题时，可以用一棵完全n叉树来表示其解空间。用可行性约束函数Place可剪去不满足行、列和斜线约束的子树。

用回溯法解题的一个显著特征：

问题的解空间是在搜索过程中动态生成的。在任何时刻，算法只保存从根结点到当前扩展结点的路径。若解空间树中从根到叶的最长路径长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。

三、图的m着色问题

1.问题描述

给定一个无向连通图G和m种不同的颜色。用这m种颜色为图G的各顶点着色，每个顶点着一种颜色，是否有使得G中任何一条边的2个顶点着有不同颜色的着色法。这个问题就是一个图的m可着色判定问题。

若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

著名的平面图的4色猜想 -----图的m可着色判定问题的特殊情形。

4色定理-----四色猜想于1976年由三个美国人依靠计算机做出证明。

显式存储整个解空间则需要O(2 h(n))。

2.算法设计

问题： 给定一个连通图G=(V,E)和m种颜色，如果这个图不是m可着色的，就回答“no”, 如果这个图是m可着色的，则要找出所有不同的着色方法。

本问题除了回溯法外，目前还没什么更好的方法。

四、批处理调度问题

1.问题描述

给定n个作业的集合J=(J1,J2,…，Jn)。每个作业Ji都有两项任务要分别在2台机器上完成。每个作业必须先由机器1处理，然后再由机器2处理。

作业Ji需要机器j的处理时间为tij，i=1,2,…,n；j=1,2。

设Fij是作业i在机器j上完成处理的时间。则所有作业在机器2上完成处理的时间和 称为该作业调度的完成时间和。

批处理作业调度问题要求：对于给定的n个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。

可以证明：批处理调度问题存在最佳作业调度使得机器1和机器2上作业以相同次序完成。

例： n=3

批处理回溯算法：

算法分析 Backtrack算法在每个结点处耗费O(1)时间，所以在最坏情况下，整个算法的计算时间复杂性为O(n!)。

五、0-1背包问题

对于n=3时的0-1背包问题，其解空间用一棵完全二叉树表示，如下图所示。

例： n=3时的0-1背包问题，W={16，15，15}，p={45，25，25}，C=30。在其解空间树上搜索最优解的过程如下图所示。

今天算法设计与分析的回溯法更新完毕。多多关注我，看下方的更多文章，连接如下：

晓强DL：图像处理必读论文之AlexNet​zhuanlan.zhihu.com 晓强DL：图像处理必读论文之二：VGG网络​zhuanlan.zhihu.com 晓强DL：第四章 贪心算法(Greedy Algorithms)​zhuanlan.zhihu.com 晓强DL：第三章 动态规划(Dynamic Programming )​zhuanlan.zhihu.com 晓强DL：第二章 递归与分治​zhuanlan.zhihu.com 晓强DL：计算机算法设计与分析第一章 算法概述​zhuanlan.zhihu.com 晓强DL：Opencv图像处理(一)​zhuanlan.zhihu.com 晓强DL：OpenCV图像处理（二）​zhuanlan.zhihu.com 晓强DL：Opencv图像处理(三)​zhuanlan.zhihu.com 晓强DL：Opencv图像处理 （四）​zhuanlan.zhihu.com