首页 > 代码库 > 游戏与常用的五大算法---下篇
游戏与常用的五大算法---下篇
前言：
心是一个人的翅膀，心有多大，世界就有多大。很多时候限制我们的，不是周遭的环境，也不是他人的言行，而是我们自己！看不开，放不下，忘不了，把自己囚禁在灰暗的记忆里；不敢想，不自信，不行动，把自己局限在自己的控件里面......如果不能 打破心的桎梏，即使给你整个天空，你也找不到自由地感觉！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）结点存储特性常用应用
说的通俗一点就是两者最终得到的结果不同，回溯法深度优先搜索堆栈活结点的所有可行子结点被遍历后才被从栈中弹出找出满足约束条件的所有解。分支限界法广度优先或最小消耗优先搜索队列、优先队列每个结点只有一次成为活结点的机会找出满足约束条件的一个解或特定意义下的最优解。
游戏与常用的五大算法---下篇