关键词：
前言：
心是一个人的翅膀，心有多大，世界就有多大。很多时候限制我们的，不是周遭的环境，也不是他人的言行，而是我们自己！看不开，放不下，忘不了，把自己囚禁在灰暗的记忆里；不敢想，不自信，不行动，把自己局限在自己的控件里面......如果不能 打破心的桎梏，即使给你整个天空，你也找不到自由地感觉！so fighting！
---------摘自《美文欣赏》
PS：为了方便大家阅读，个人认为比较重要的内容-------红色字体显示
---------------------------------------------------- 分 割 线 ----------------------------------------------------------
算法之四：回溯算法
一、什么是回溯算法
按照惯例我们先来说一说回溯算法的基本概念，什么是回溯算法呢？回溯算法实际上就是类似枚举的搜索尝试过程，同时在这个搜索过程之中寻找问题的解，当发现不满足求解条件的时候，就“回溯返回”，尝试别的路径。
回溯法求解问题在实际过程之中也挺常见的，比如在迷宫问题之中我们就可以使用回溯法求解！回溯法可以说是一种优选搜索法，按照选优条件向前搜索，以求最后达到最终的目标，假如是在迷宫问题之中如果达到出口的时候，那么回溯的过程也就结束了。但是在这个逐步前进的过程之中，发现原先的选择并不是最优或者说是根本达不到目的地，也就是所说的碰到了“障碍物”。那么这时候它就会退回一步重新选择，这种走不通就回退一步的再走的技术为回溯法，而满足回溯状态的某个点就称之为“回溯点”。
由于回溯法挺容易理解的，所以回溯法也适合很多的实际问题，甚至一些比较复杂的大型的问题，因此也获得一个“通用解题方法”的美称！
二、核心思想
接下去再来说一说回溯法的核心思想，在包含所有问题的解空间树之中，按照深度优先搜索的策略，从根节点出发深度搜索解空间树。当搜索到某一个节点的时候，需要先判断该节点是否包含问题的解，换句话说检测当前点是否满足条件。如果包含或者说是满足条件，那么就从该节点出发继续搜索下去，如果该节点不包含所求问题的解，那么就逐层向其祖先节点进行回溯！说到这里可能大家也会感觉到其实也就是我们常说的深度优先策略，我们学习图的过程之中经常会使用到深度优先和广度优先的策略！因此对于这种策略也不会陌生，按照这种策略，首先从根节点出发深度搜索解空间树。当搜索到某一个节点的时候，这时候需要判断该节点是否包含问题的解，如果包含，就从该节点继续出发搜索下去，如果该节点不包含问题的解，那么这时候就逐层向根节点进行回溯。
总结一下，其实所谓的回溯法就是对隐式图的深度优先搜索算法。
顺便提一句，若用回溯方法求解问题的所有解的时候，如果没有找到最终的目标，那么只有当回溯到根节点的时候才可以，并且根节点的所有可行子树都要已被遍历才可以。但是通常我们只需要某一个解就行了，比如在走迷宫的时候我们只需要找到一个出口就行了（假设迷宫有多个出口）。
三、回溯算法的适用场景
那么什么时候需要用到回溯算法呢？首先使用回算法的时候需要注意一下，需要明确定义问题的解空间，问题的解空间至少包含问题的一个最优解。
在使用的时候我们还需要确定节点的扩展搜索规则，以深度优先方式搜索解空间，并且你还可以在搜索过程之中利用剪枝函数避免无效的搜索。
四、实际运用
那么体怎么使用呢？接下来我们来看一看具体地运用，首先来看一下算法的框架。假设一个问题的解是一个n维向量（a1，a2，a3，....，an），约束的条件是ai（i = 1，2，3，.....，n）之间满足某种条件，并用一个函数式f（ai）来表示。
说了怎么表示之后，我们就需要用把整个框架搭出来。一般来说有两种常见的方法，一种是递归解法，一种是非递归解法，下面我们就把这两种框架写出来。
非递归算法框架：
int a[n], i; //n是一个常量，初始化数组
i = 1;
while(i > 0 && （还没有达到出口，即还有路可以走）) //表示还没有回溯到头
{
if( i > n) //已经搜索到最终叶子节点
{
//已经搜索到了解，可以进行输出了
//如果不需要搜索出所有的解，这时候就可以结束退出了
}
else
{
//a[i]第一个可能的值
while(a[i]在不满足约束条件且在搜索空间之内)
{
a[i]下一个可能的值
}
if(a[i]在搜索空间之内)
{
//此时作为技术功能的i需要进行++操作，表示资源的占用
i = i +1;
}
else
{
清理所占的状态空间； // 回溯
i = i –1;
}
}
}
递归框架：
一般来说回溯法还是使用递归方式解决比较好，因为回溯法是对解空间的深度优先搜索，用下面的伪代码来简单模拟实现一下：（k表示搜索的深度，此框架是网上看到的，感觉比较精辟，就拿来用了）
int a[n];
try(int i)
{
if(i>n)
输出结果;
else
{
for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
{
if(fun(j)) // 满足限界函数和约束条件
{
a[i] = j;
... // 其他操作
try(i+1);
回溯前的清理工作（如a[i]置空值等）;
}
}
}
}接下来给出一个使用回溯方法解决的具体问题---迷宫问题，下面是一个迷宫类的实现：
//迷宫
template<typename T>
class Maze
{
typedef Node Pos;
public:
Maze()
: m_row(0)
, m_col(0)
, m_start(0, 2)
, m_map(NULL)
{}
~Maze()
{
for (int i = 0; i < m_row; i++)
{
delete[] m_map[i];
}
delete[] m_map;
}
bool SearchPath() //查找迷宫路径 -------(深度优先，相当于回溯吧)
{
Pos Cur = m_start;
m_s.Push(Cur);
m_map[Cur.x][Cur.y] = 2;
while (!m_s.Empty())
{
Pos next = m_s.Top();
Cur = next;
m_map[Cur.x][Cur.y] = 2;
if (next.x == m_row - 1 || next.y == m_col - 1)
return true;
//判断上
next.x--;
if (CheckNextAccess(next))
{
m_s.Push(next);
continue;
}
next.x++;
//下
next.x++;
if (CheckNextAccess(next))
{
m_s.Push(next);
continue;
}
next.x--;
//左
next.y--;
if (CheckNextAccess(next))
{
m_s.Push(next);
continue;
}
next.y++;
//右
next.y++;
if (CheckNextAccess(next))
{
m_s.Push(next);
continue;
}
//进行回溯
m_s.Pop();
//并且把这个位置标记起来
m_map[next.x][next.y] = 3;
}
return false;
}
void PrintMap() //输出迷宫地图
{
for (int i = 0; i < m_row; ++i)
{
for (int j = 0; j < m_col; ++j)
cout << m_map[i][j] << " ";
cout << endl;
}
}
void PrintPath() //打印路径的坐标
{
Stack<Pos> sk;
while (!m_s.Empty())
{
sk.Push(m_s.Top());
m_s.Pop();
}
while (!sk.Empty())
{
cout << "(" << sk.Top().x <<"，"<< sk.Top().y << ")" << "->";
sk.Pop();
}
cout << endl;
}
void SetMap(int arr[][10], int row, int col) //设置地图
{
m_row = row;
m_col = col;
m_map = new T *[m_row];
for (int i = 0; i < m_row; ++i)
{
m_map[i] = new T[m_col];
for (int j = 0; j < m_col; ++j)
m_map[i][j] = arr[i][j];
}
}
private:
bool CheckNextAccess(Pos coor) //判断该坐标能否通过
{
if (coor.x >= 0 && coor.x < m_row
&& coor.y >= 0 && coor.y < m_col
&& m_map[coor.x][coor.y] == 1)
return true;
else
return false;
}
private:
int m_row;
int m_col;
T ** m_map;
Stack<Pos> m_s;
Pos m_start;
};算法之五：分支界限法
说完了回溯算法，那么我们接下去说一说最后一个算法，其实这个算法与回溯法比较相似，所以放在一起讲了，还是像之前一样按照步骤一步一步来！
一、什么是回溯算法
首先需要说明的是，分支界限法与回溯法挺类似的，也是一种在问题的解空间树Tree上来搜索问题解的算法。但是在一般情况下，分支界限法与回溯法的求解目标不同而已，回溯法的求解目标是找出Tree中满足约束条件的所有解，不过很多时候我们为了方便只是用了其中一个解而已。而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
二、核心思想
之前我们在说回溯法的时候说过，回溯法其实就是我们通常所说的深度优先策略，而现在所说的分支界限法就是另一种策略---广度优先策略。
所谓“分支”就是采用广度优先的策略，依次搜索E-结点的所有分支，也就是所有相邻结点，抛弃不满足约束条件的结点，其余结点加入活结点表。然后从表中选择一个结点作为下一个E-结点，继续搜索。
选择下一个E-结点的方式不同，则会有几种不同的分支搜索方式。
1）FIFO搜索 2）LIFO搜索 3）优先队列式搜索
三、回溯算法的适用场景由于分支界限法是广度优先的策略，所以一般用来求最优解的比较多，我们在背包问题之中也可以使用分支界限法来解决，当然在使用的过程之中我们可以使用剪枝来优化，这样可以提高搜索的效率。
四、实际运用
在说实际运用之前还是先说一说使用的过程：
由于求解目标不同，导致分支限界法与回溯法在解空间树T上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
分支限界法的搜索策略是：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
由于分支界限法用的是广度优先策略，所以下面用一个具体的例子来表示广度优先策略：
template<typename T> //广度优先策略
class Maze
{
typedef Node Pos;
public:
Maze()
:m_row(0)
, m_col(0)
, m_start(0, 2)
, m_map(NULL)
, m_book(NULL)
{}
~Maze()
{
for (int i = 0; i < m_row; ++i)
{
delete[] m_map[i];
delete[] m_book[i];
}
delete[] m_map;
delete[] m_book;
}
bool SearchPath() //查找迷宫路径
{
queue<Node> my_queue;
assert(m_map);
my_queue.push(m_start);
Pos cur = m_start;
m_book[cur.x][cur.y] = 0;
int steps = 0;
while (!my_queue.empty())
{
Pos next = my_queue.front();
cur = next;
m_map[cur.x][cur.y] = 2;
steps = m_book[cur.x][cur.y] + 1;
if (cur.x == m_row - 1 && m_start.x != m_row - 1
||cur.y == m_col - 1 && m_start.y != m_col - 1
||cur.x == 0 && m_start.x != 0
||cur.y == 0 && m_start.y !=0)
break;
//上
next.x--;
if (CheckNextAccess(next))
{
my_queue.push(next);
m_book[next.x][next.y] = steps;
}
next.x++;
//下
next.x++;
if (CheckNextAccess(next))
{
my_queue.push(next);
m_book[next.x][next.y] = steps;
}
next.x--;
//左
next.y--;
if (CheckNextAccess(next))
{
my_queue.push(next);
m_book[next.x][next.y] = steps;
}
next.y++;
//右
next.y++;
if (CheckNextAccess(next))
{
my_queue.push(next);
m_book[next.x][next.y] = steps;
}
next.y--;
my_queue.pop();
}
if (!my_queue.empty())
m_s.Push(cur);
while (!m_s.Empty())
{
Pos next = m_s.Top();
if (m_book[next.x][next.y] == 0)
return true;
//上
next.x--;
if (CheckPrevAccess(next))
{
m_s.Push(next);
continue;
}
next.x++;
//下
next.x++;
if (CheckPrevAccess(next))
{
m_s.Push(next);
continue;
}
next.x--;
//左
next.y--;
if (CheckPrevAccess(next))
{
m_s.Push(next);
continue;
}
next.y++;
//右
next.y++;
if (CheckPrevAccess(next))
{
m_s.Push(next);
continue;
}
next.y--;
}
return true;
}
void SetMap(T arr[][10], int row, int col) //设置地图
{
assert(arr);
if (row <= 0 || col <= 0)
return;
m_row = row;
m_col = col;
m_map = new T *[m_row];
m_book = new T *[m_row];
for (int i = 0; i < m_row; ++i)
{
m_map[i] = new T[m_col];
m_book[i] = new T[m_col];
for (int j = 0; j < m_col; ++j)
{
m_map[i][j] = arr[i][j];
m_book[i][j] = -1;
}
}
}
void PrintMap() //打印地图
{
cout << "迷宫地图中所走过的路径" << endl;
for (int i = 0; i < m_row; i++)
{
for (int j = 0; j < m_col; j++)
{
cout << m_map[i][j] << " ";
}
cout << endl;
}
cout << endl << endl; //打印辅助数组
cout << "辅助数组中所有入队的坐标" << endl;
for (int i = 0; i < m_row; i++)
{
for (int j = 0; j < m_col; j++)
{
printf("%2d ", m_book[i][j]);
}
cout << endl;
}
}
void PrintPath() //打印路径
{
while (!m_s.Empty())
{
cout << "(" << m_s.Top().x << "," << m_s.Top().y << ")" << endl;
m_s.Pop();
}
}
private:
bool CheckNextAccess(Pos coor) //判断下一个坐标能否通过
{
if (coor.x >= 0 && coor.x < m_row
&& coor.y >= 0 && coor.y < m_col
&& m_map[coor.x][coor.y] == 1)
return true;
else
return false;
}
bool CheckPrevAccess(Pos coor) //判断前一个坐标能否通过
{
if (coor.x >= 0 && coor.x < m_row
&& coor.y >= 0 && coor.y < m_col
&& m_book[coor.x][coor.y] == (m_book[m_s.Top().x][m_s.Top().y] - 1))
return true;
else
return false;
}
private:
int m_row;
int m_col;
T ** m_map;
T ** m_book;
MyStack<Pos> m_s;
Pos m_start;
};
两者的区别
有一些问题其实无论用回溯法还是分支限界法都可以得到很好的解决，但是另外一些则不然。也许我们需要具体一些的分析——到底何时使用分支限界而何时使用回溯呢？
虽然两者有一些相似点，不过还是有区别的，回溯法和分支限界法的一些区别：
1）方法对解空间树的搜索方式 2）
存储结点的常用数据结构 3）结点存储特性常用应用
说的通俗一点就是两者最终得到的结果不同，回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解。分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解。
五大常用算法
http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html分治算法一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再... 查看详情
「五大常用算法」一文搞懂分治算法(代码片段)
...收录在bigsai-algorithm前言分治算法（divideandconquer）是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一，很多人在平时学习中可能只是知道分治算法，但是可能并没有系统的学习分治算法，本篇就带... 查看详情
五大常用算法之三贪心算法
贪心算法贪心算法简介： 贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。 贪心算法每一步必须满足一下条件： 1、... 查看详情
五大常用算法一文搞懂分治算法(代码片段)
前言分治算法（divideandconquer）是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一，很多人在平时学习中可能只是知道分治算法，但是可能并没有系统的学习分治算法，本篇就带你较为全面的去认识... 查看详情
五大常用经典算法
一、基本概念在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解... 查看详情
五大常用算法
五大常用算法之一：分治算法https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html五种常用算法之二：动态规划算法https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html五大常用算法之三贪心算法https://www.cnblogs.com/steven_oyj/archive/2010/... 查看详情
五大常用算法之四：回溯法
(转自：http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741376.html)1、概念 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返... 查看详情
五大常用算法：分治动态规划贪心回溯和分支界定
五大常用算法：分治、动态规划、贪心、回溯和分支界定 这五种算法引出了很多问题。慢慢的更新链接！ 动态规划的五个典型算法：动态规划 1.最大连续子序列之和2.数塔问题（二叉树从上往下遍历最大和... 查看详情
好记性不如烂笔头常用五大算法合集--日后慢慢更新
分冶法：分冶法之归并排序回溯法：贪心算法：分支界限法：动态规划法： 先把目录写在这，日后慢慢更新~参考文献：佳佳hi的博客算法论 查看详情
五大常用算法--dp(代码片段)
概念【geekforgeeks】DynamicProgrammingismainlyanoptimizationoverplainrecursion.Whereverweseearecursivesolutionthathasrepeatedcallsforsameinputs,wecanoptimizeitusingDynamicProgramming.Theideaistosimplystoretheresultsofsubproblems,sothatwedonothavetore-computethemwhenneededlater.Thissimpleoptimiza... 查看详情
五大常用算法
1.分治法 http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html2.动态规划 http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741374.html3.贪心算法 http://www.cnblogs.com/steven_oyj/a 查看详情
［转］五大常用算法：分治动态规划贪心回溯和分支界定
Referredfrom http://blog.csdn.net/yapian8/article/details/28240973分治算法一、基本概念 在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的... 查看详情
数据结构和算法-五大常用算法:分治算法(代码片段)
原文链接：（转载请注明出处）https://dmego.me/2016/10/16/hanoi一．起源： 汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64... 查看详情
五大常用算法动态规划算法
一、算法定义 假设当你正在使用适当的输入数据进行一些计算。你在每个实例中都进行了一些计算，以便得到一些结果。当你提供相同的输入时，你不知道会有相同的输出，这就导致了你之前计算某些结果的宝贵时间被浪费... 查看详情
五大常用算法动态规划算法
一、算法定义 假设当你正在使用适当的输入数据进行一些计算。你在每个实例中都进行了一些计算，以便得到一些结果。当你提供相同的输入时，你不知道会有相同的输出，这就导致了你之前计算某些结果的宝贵时间被浪费... 查看详情
游戏制作中的大宝剑---常用的数据结构与算法
前言 时间流逝，物是人非，就好像涌动的河流，永无终焉，幼稚的心智将变得高尚，青年的爱慕将变得深刻，清澈之水折射着成长。 ... 查看详情
五大常用算法--分治(代码片段)
概念DivideandConquerisanalgorithmicparadigm.AtypicalDivideandConqueralgorithmsolvesaproblemusingfollowingthreesteps.Divide:Breakthegivenproblemintosubproblemsofsametype.Conquer:RecursivelysolvethesesubproblemsCombine:Appropriatelycombinetheanswer.常见应用快排/*low-->Startingindex,high--&g... 查看详情
五大常用算法之一：贪心算法
参考技术A所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题最佳的选择而不考虑子问题的结果。这是贪心算法可行的第一个基本要素。... 查看详情