| 赞 | 190 |
| VIP | 627 |
| 好人卡 | 188 |
| 积分 | 95 |
| 经验 | 171230 |
| 最后登录 | 2024-7-3 |
| 在线时间 | 5073 小时 |
Lv4.逐梦者 (版主)
- 梦石
- 0
- 星屑
- 9532
- 在线时间
- 5073 小时
- 注册时间
- 2013-6-21
- 帖子
- 3580
  
|
本帖最后由 RyanBern 于 2015-5-27 23:19 编辑
谈谈如何编写有效的穷举算法
在写程序的时候，我们或多或少都会碰到算法的问题。而算法中最简单的一种，莫过于穷举法。因穷举法好想，好写，比较无脑，所以被很多人所青睐。虽然从效率的角度上来说，穷举法的效率不高，而且解决问题比较笨，看起来很low的样子。但是，作为一种基本的简单算法，穷举法的适用范围可谓是非常广泛，几乎所有的问题都可以用穷举法解决。如果说，效率低是穷举法的一个缺点，那么适用面广绝对是穷举法的一个巨大的优点。况且，现在算法的发展十分迅速，高效率的穷举法也可谓是比比皆是。那么，如何有效率地进行穷举，也属于我们应该学习的范围。
言归正传，那么穷举法应该如何写出呢？可能有人觉得穷举法不是特别难写，那是因为涉及到的问题都比较简单。
在这里，我把穷举的方式分为三种，普通穷举，深度优先搜索（回溯法），广度优先搜索。后面两种属于有一定筛选条件的搜索方法，适用于一些穷举上比较困难的问题，也具有减少穷举次数的能力。严格意义上来讲，几种方式的界限有时候并不是很清楚。但是对于同一个问题，不同方法的实现还是有区别的。
（一）普通穷举
所谓普通穷举，概括来讲，需要你做下面两个事情：
1.如何按照一定顺序把可能的组合列举出来
2.对于给定的组合，如何计算它是否满足题目要求，或者是在优化问题中，对应的数值是多少。
只要能有办法完成上面两步，那么穷举法就一定能够进行。
下面举一个例子：
某人开枪射击，每次射中的环数为0~10之内的整数，他一共开了5枪，总共的环数为25环。问：他各枪打出的环数组合有多少种？在这里，打出的环数和顺序加以区分，例如[5, 5, 5, 4, 6]和[5, 5, 5, 6, 4]认为是不同的。（这道题是R考场第二期的附加题A题）
那么我们分开进行这两步。
1.所有组合都要按照一定规则列举出来，我们可以先考虑第 i 枪的环数x(i)，每个x(i)取值于0~10，然后对每一枪考虑即可。
2.对于一个组合x(1), x(2), ... x(5)，如果它们加起来等于25，那么符合要求，结果计数变量 +1 即可。
所以，可以写出如下代码：
def solve(score) result = 0 for x1 in 0..10 for x2 in 0..10 for x3 in 0..10 for x4 in 0..10 for x5 in 0..10 result += 1 if x1 + x2 + x3 + x4 + x5 == score end end end end end end
def solve(score)
result = 0
for x1 in 0..10
for x2 in 0..10
for x3 in 0..10
for x4 in 0..10
for x5 in 0..10
result += 1 if x1 + x2 + x3 + x4 + x5 == score
end
end
end
end
end
end
代码很容易看，所以我就不解释了，原理就是一个个结果去试，但是前提你要能够用一种方式把所有结果列举出来。
我们再看个例子，请设计一个算法，判断一个字符串a中是否含有某字符串b，例如a="bookkeeper"，b="ookkee"，那么a就是含有b。（即b是a的一个子串）
首先我们想想，如果b是a的子串，那么所有的情况可以按照b的第一个字符在a中的位置进行区分，总共的可能数为m - n + 1，其中 m 是a串的长度，n 是b串的长度，并且规定m >= n。然后找到了这个位置，只需判断从这个位置起是否含有b就可以了。
bool is_substring(char *a, int m, char * b, int n){ for (int i = 0; i < m - n ; i++){ for(int j = 0; j < n ; j++){ if (a[i + j] != b[j]) break; if (j == n - 1) return true; } } return false }
bool is_substring(char *a, int m, char * b, int n){
for (int i = 0; i < m - n ; i++){
for(int j = 0; j < n ; j++){
if (a[i + j] != b[j]) break;
if (j == n - 1) return true;
}
}
return false
}
代码的原理也比较简单，看一下就没什么问题。在这里我们注意到穷举法涉及到的循环比较多，如果搞不清循环之间的关系，有可能会出错。
再举一个穷举规则稍微复杂一点的例子。假设给定一个序列，长度为 n，序列里面的元素都是正整数。现在问，如果从序列中抽出一列子列，并且要求该子列是单调不增的，那么这个子列最长是多少。注：称一个序列是另外一个序列的子列，是指将原来序列的若干项抽出来，并按照原来顺序排成一列；称一个序列单调不增，指的是该序列的数字后面的一个总不大于前面的一个。（此题为R考场第二期附加题B题）
经过分析，我们需要做的第一件事情就是如何把所有子列都列举出来。进而判断他是否是单调不增。
如果该序列确实符合要求，那么则计算该序列的长度（实际可以用数组的大小表示）
那么，如何列举所有子列出来呢？通过简单的分析，我们知道，如果原序列的长度是 n，那么它所有非空子列的总数就是2^n - 1。也就是说，对于固定位置的数字，要么出现在子列中，要么不出现在子列中，总共只有2种可能，一共 n 个位置，就是 n 个 2 相乘。又要求子列非空，所以结果要去掉 1 。下面我们要做的就是列出所有的子列。
我们知道，如果用 0 表示不在子列中，1表示在子列中，那么我们可以得到一个长度为 n 的0-1序列，这个0-1序列就能表示所有的子列，而这本身又是一个数字的二进制表示。所以我们考虑用一个整数来表示一个序列，表示的方法就是把整数看成二进制数，如果某个位上的数为 1，那么该位上的数字便在子列当中。为了方便起见，我们的整数位数从右到左算起，即二进制数110(对应十进制的6)的第 0 位为0，第 1 位为 1，第 2 位为 1。如果序列a的长度为3，那么110(6)对应的序列就是a[1], a[2]组成的子列。
现在列举的方法已经叙述完毕，那么该如何操作呢？这就涉及到位运算了。一个二进制数，如果我想要知道它的第 i 位是什么，我只需要做右移 i 位的运算，然后看第 0 位的数值即可。在这里位数依然是从右向左的。例如我想知道110(6)的第 2 位是什么，那么我就把它右移 2 位，然后取出第 0 位即可。取出第 0 位的过程可以使用按位与'&'运算。
最后就是如何判断数列是否符合要求，这个比较简单，就不说了。
从上面的思路，我们可以大致写出代码出来了。
def solve_max_sub_seq(seq) n = seq.size max = 1 (1...2 ** n).each do |digit| sub_seq = [] flag = true (0...n).each do |pos| if (digit >> pos) & 0x01 == 1 if sub_seq.size == 0 || sub_seq[-1] >= seq[pos] sub_seq << seq[pos] else flag = false break end end end max = [max, sub_seq.size].max if flag end return max en d
def solve_max_sub_seq(seq)
n = seq.size
max = 1
(1...2 ** n).each do |digit|
sub_seq = []
flag = true
(0...n).each do |pos|
if (digit >> pos) & 0x01 == 1
if sub_seq.size == 0 || sub_seq[-1] >= seq[pos]
sub_seq << seq[pos]
else
flag = false
break
end
end
end
max = [max, sub_seq.size].max if flag
end
return max
en
d
结合上面的思路，看懂此代码应该不难。
（二）深度优先搜索（回溯法）
如果说第一部分是最普通的穷举，把所有可能的情况都列出来，那么这一部分则是有选择的穷举，只是把符合条件的情况列举出来，并加以比较。和普通穷举相比，它大量减少了枚举次数，以便在尽可能少的空间里面需求我们需要的解。
回溯法的原理其实非常简单，例如，我们要列举出所有符合条件的解，而写出这个解我们需要 n 步，每一步我们总共有a(n)种选择，那么我们只需要从第一步开始，依次向下进行即可。当然，每一步我们需要出一种选择，在这里我们按照一定的顺序把选择遍历一遍。一旦选定了一个选择之后，我们就进行下一步的选择（而不再考虑同一步的其他选择）。而到某一步时，我们发现解已经生成或者中途再无选择可做，我们就需要退回到上一部，更改我们上一部的选择（这就是所谓回溯）。当所有选择都遍历完毕时，符合条件的解就已经找到了。
这样说还是很难理解，我们说得形象一点好了。玩RPG的人或多或少都会碰到走迷宫的关卡，而有一种很著名的“贴墙法”，我相信很多人也听说过。简单来说，从迷宫的入口出发，如果遇到岔路就走左边那一条，如果遇到死路就原路返回。这个方法就是一个回溯法。不过这种方法也有一定的缺陷，就是无法处理环路的情况。当把原路返回的条件改成“遇到死路或者走过的路”，那么算法就可以执行下去。
和深度优先相关联的的数据结构就是“栈”，建议在维基百科上查询。
因此我们不妨把这个迷宫问题作为一道例题，来看看回溯法如何编写。
迷宫的数据结构是一个n*n的Table，左上角的(0, 0)位置是起点，右下角的(n-1, n-1)是终点。表格中，数字0表示可以通行，数字1表示不能通行。人只能竖着走或者是横着走。
例如，n = 5时，一个迷宫可以是下面的这样（为了方便起见，起点用s表示，终点用e表示，s和e都是可通行的，实际的数据还是0和1）：
s 1 0 0 0
0 0 0 1 1
1 1 0 0 1
0 0 0 1 1
1 1 0 0 e
对于每一个点，我们对四个方向做试探，试探的顺序为[下左右上]，如果发现某个方向能够走通，不管这条路将来通向哪里，我们都往这个方向走一步，并且，最重要的，我们需要把当前的位置做标记，从而记录我们到过的位置和选择的方向，这一步是回溯必不可少的环节。记录我们到过的位置是为了避免走重复的路从而绕圈，而记录选择的方向是为了给回溯做准备，如果某个方向的路没有走通，那么接下来将从何处开始。
我在下面的代码里面写了详细的注释，请认真阅读并领会回溯法的过程。
module Maze # 记录路径点的类，每个点记录坐标和行走方向 class Path_Point attr_accessor :x # 该点 x 坐标 attr_accessor :y # 该点 y 坐标 attr_accessor :d # 该点行走方向，0 : 向下，1 : 向左，2 : 向右，3 : 向上 def initialize(x = 0, y = 0, d = -1) @x = x @y = y @d = d end end # 判断坐标是否有效（不能走出迷宫外） # map是一个 Table 对象 def valid?(x, y, map) return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize end # 求迷宫的一条路径 # map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑 def self.solve(map) # 记录迷宫路径点所用栈 stack = [] # 方向数组，方便表示向各个方向行走时的坐标增量 direction = [[1, 0], [0, -1], [0, 1], [-1, 0]] # 给起点做标记 map[0, 0] = 2 # 起点入栈 stack.push(Path_Point.new(0, 0, -1)) # 当栈不空时，证明还有路径点需要处理，此时进行循环 while !stack.empty? # 取出栈顶元素 point = stack.pop # 试探下一个方向 point.d += 1 # 当该方向是有效方向时 while point.d <= 3 # 计算沿着该方向行走一步之后的新坐标 new_x = point.x + direction[point.d][0] new_y = point.y + direction[point.d][1] # 如果走到终点(Table右下角的点) if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0 # 此时栈中的路径点合起来就是一条路径 # 但是还缺少两个点：当前点和终点 # 把当前点和终点加上就是一条完整路径 stack << point stack << Path_Point.new(new_x, new_y) # 返回 stack 数组 return stack end # 如果下一步的坐标在地图内，并且是没有走过的通路 if valid?(new_x, new_y, map) && map[new_x, new_y] == 0 # 走向下一个路径点，并做标记为已走过 map[new_x, new_y] = 2 # 当前点入栈，记录 stack << point # 设置当前点为新的路径点 point = Path_Point.new(new_x, new_y) end # 无论是否找到新路径点，point的d值均 +1 # 如果point为新路径点，那么此操作会让其d值从-1变为0，可操作 # 如果point为原有路径点，那么此操作是试探下一个可能的方向 point.d += 1 end end # 如果栈为空，依然没有找到通路，返回 nil return nil end end
module Maze
# 记录路径点的类，每个点记录坐标和行走方向
class Path_Point
attr_accessor :x # 该点 x 坐标
attr_accessor :y # 该点 y 坐标
attr_accessor :d # 该点行走方向，0 : 向下，1 : 向左，2 : 向右，3 : 向上
def initialize(x = 0, y = 0, d = -1)
@x = x
@y = y
@d = d
end
end
# 判断坐标是否有效（不能走出迷宫外）
# map是一个 Table 对象
def valid?(x, y, map)
return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize
end
# 求迷宫的一条路径
# map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑
def self.solve(map)
# 记录迷宫路径点所用栈
stack = []
# 方向数组，方便表示向各个方向行走时的坐标增量
direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
# 给起点做标记
map[0, 0] = 2
# 起点入栈
stack.push(Path_Point.new(0, 0, -1))
# 当栈不空时，证明还有路径点需要处理，此时进行循环
while !stack.empty?
# 取出栈顶元素
point = stack.pop
# 试探下一个方向
point.d += 1
# 当该方向是有效方向时
while point.d <= 3
# 计算沿着该方向行走一步之后的新坐标
new_x = point.x + direction[point.d][0]
new_y = point.y + direction[point.d][1]
# 如果走到终点(Table右下角的点)
if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0
# 此时栈中的路径点合起来就是一条路径
# 但是还缺少两个点：当前点和终点
# 把当前点和终点加上就是一条完整路径
stack << point
stack << Path_Point.new(new_x, new_y)
# 返回 stack 数组
return stack
end
# 如果下一步的坐标在地图内，并且是没有走过的通路
if valid?(new_x, new_y, map) && map[new_x, new_y] == 0
# 走向下一个路径点，并做标记为已走过
map[new_x, new_y] = 2
# 当前点入栈，记录
stack << point
# 设置当前点为新的路径点
point = Path_Point.new(new_x, new_y)
end
# 无论是否找到新路径点，point的d值均 +1
# 如果point为新路径点，那么此操作会让其d值从-1变为0，可操作
# 如果point为原有路径点，那么此操作是试探下一个可能的方向
point.d += 1
end
end
# 如果栈为空，依然没有找到通路，返回 nil
return nil
end
end
仿照上面的回溯算法，我们可以解决著名的“八皇后问题”。
例：八皇后问题。国际象棋的棋盘为8*8的方阵，现在在这个棋盘上放置8枚“皇后”棋子，要求这8枚皇后的任何两枚都不能互相进攻。注：在棋盘上，皇后的行走规则是横、竖、对角线，也就是说，我们需要任何两个皇后都不能在同一行，同一列，或者是同一对角线上。请列举出所有可能的放置方法。
分析：我们利用回溯法求解此题。首先，我们并不知道可行的解究竟长成什么样子，只能一个一个进行试探。如果利用普通的穷举法，先把所有可能的放置方法穷举一遍，然后判断某个固定的放置方法是否符合要求，如果符合要求就输出。利用普通的穷举法，一共要列举8^8种情况。再对于每一种情况进行判断，任意两个皇后都不能互相攻击，还需要比较8*7/2=28次，计算代价较高。因此我们放弃普通的穷举法。
那么回溯法的思想是怎样的呢？首先，我们一步一步进行试探。我们先放置第一列（或者第一行的皇后，在这里我们统一选择第一列），因为我们不知道解长成什么样子，所以我们不妨取第一列的第一个位置，放置第一个皇后。放置完毕后，我们需要考虑这个皇后带给其他位置的影响，即“假设这个位置有皇后，那么哪些地方不能再放置皇后了呢”？显然，和它同行，同列，以及同对角线的位置都不能放置。为了简单起见，由于我们接下来放置的是第二列的皇后，本来就不会跟第一列的皇后在同一列上，因此对列的考虑可以省去。考虑影响之后，我们放置第二列的皇后，选择的位置当然是已经排除了第一个皇后产生影响之外的位置。放置第二列的皇后之后，我们还需要考虑第二个皇后对其他位置的影响。
以此列推，我们这样不断放置，直到遇到下面两种情况之一：
（1）成功放置了第8列的皇后。
（2）放置了某列时，发现所有的位置均不能放置。
出现这两种情况之后，我们需要做的事情是一样的，就是要把最近一列的皇后移除，然后考虑下一个可能的位置。如果不存在下一个可能的位置，那么就继续移除最近一列的皇后。当所有可能的位置都不存在时，证明穷举已经结束了。（1）和（2）的不同之处在于，（1）情况时，你要先输出这组解，然后再进行回退，而（2）情况不需要。同时，一定要注意，将某个皇后从棋盘上移除时，记得要清除它对其他位置造成的影响。
上面的两个过程用图表示大概是这样的。我们假设棋盘是4*4的（0表示可用位置，1表示不可用位置，*表示皇后）：
* 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1 | * 1 1 1
1 1 1 0
1 * 1 0
1 1 1 1 | * 1 1 1
1 1 0 1
1 1 1 1
1 * 1 1 |
这是个例子，从第二个格子到第三个格子就发生了回溯，因为如果将第二列的皇后放在第三个位置上，那么第三列的位置均不可用，所以应该试探第二列第四个位置。
此问题的代码和上面的那个迷宫问题基本相似，我在这里不给出注释，看看你能不能理解吧。
module Queen_Problem class Queen attr_accessor :x attr_accessor :y def initialize(x = 0, y = 0) @x = x @y = y end end # 判断坐标是否有效 # map是一个 Table 对象 def valid?(x, y, map) return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize end # 设置位置限制 def set_restriction(queen, map, res = 1) return unless valid?(queen.x, queen.y, map) d = 1 for i in queen.y + 1...map.ysize [-d, 0, d].each do |j| map[j, i] += res if valid?(j, i, map) end d += 1 end end # 消除位置限制 def remove_restriction(queen, map) set_restriction(queen, map, -1) end def self.solve(map) stack = [] stack.push(Queen.new(-1, 0)) while !stack.empty? queen = stack.pop remove_restriction(queen, map) queen.x += 1 while queen.x < map.xsize if queen.y == map.ysize p stack queen = stack.pop elsif valid?(queen.x, queen.y, map) && map[queen.x, queen.y] == 0 set_restriction(queen, map) stack << queen queen = Queen.new(-1, queen.y + 1) end queen.x += 1 end end end end
module Queen_Problem
class Queen
attr_accessor :x
attr_accessor :y
def initialize(x = 0, y = 0)
@x = x
@y = y
end
end
# 判断坐标是否有效
# map是一个 Table 对象
def valid?(x, y, map)
return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize
end
# 设置位置限制
def set_restriction(queen, map, res = 1)
return unless valid?(queen.x, queen.y, map)
d = 1
for i in queen.y + 1...map.ysize
[-d, 0, d].each do |j|
map[j, i] += res if valid?(j, i, map)
end
d += 1
end
end
# 消除位置限制
def remove_restriction(queen, map)
set_restriction(queen, map, -1)
end
def self.solve(map)
stack = []
stack.push(Queen.new(-1, 0))
while !stack.empty?
queen = stack.pop
remove_restriction(queen, map)
queen.x += 1
while queen.x < map.xsize
if queen.y == map.ysize
p stack
queen = stack.pop
elsif valid?(queen.x, queen.y, map) && map[queen.x, queen.y] == 0
set_restriction(queen, map)
stack << queen
queen = Queen.new(-1, queen.y + 1)
end
queen.x += 1
end
end
end
end
（三）广度优先搜索（BFS）
这是第二种有选择的搜索方式，我们称其为广度优先搜索。它相当于是深度优先搜索的相对方法。在深度优先搜索中，我们遇到分支的情况，会毫不犹豫地进入到一个分支中，然后遇到分支就进入，直到找到的问题的解或者是回头。而广度优先搜索，则是在遇到分支时，不急着进入一个分支当中，而是把当前分支的所有情况考虑之后，再进行下一步。
和深度优先相似，广度优先搜索也有专门的数据结构，那就是“队列”，建议在维基百科上查询相关内容。
我们还是拿走迷宫举例，上面我们说，深度优先是“一条路走到黑”地搜索，那么广度优先就是一种“地毯式”的搜索。我们回忆在深度优先中，我们遇到岔路就指定一个方向，然后继续走下去，那么在广度优先中，我们要如何做呢？
首先，我们在起点位置，假如走到某个地方发现有分支，那么，相对地，我们要考虑所有的分支方向，在这里，我们假设自己可以“分身”。那么遇到分支，我们“分身”出与分支个数相同的分身，然后让这些“分身”来测试每个路径。如果分身遇到岔路，就继续“分身”。直到某一个分身到达了出口为止。值得注意的是，如果分身在途中遇到了死路，或者是其他分身已经走过的路，那么该分身就应该消失。显然，在广度优先搜索中，每种情况处理且只处理了一次。
基于这个想法，我们写出代码如下。在代码里，我详细给出注释，请仔细比较此代码和深度优先搜索代码的不同。
module Maze # 记录路径点的类，每个点记录坐标和行走方向 class Path_Point attr_accessor :x # 该点 x 坐标 attr_accessor :y # 该点 y 坐标 def initialize(x = 0, y = 0) @x = x @y = y end end # 判断坐标是否有效（不能走出迷宫外） # map是一个 Table 对象 def valid?(x, y, map) return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize end # 求迷宫的一条路径 # map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑 def self.solve(map) # 记录待处理路径所用队列 queue = [] # 方向数组，方便表示向各个方向行走时的坐标增量 direction = [[1, 0], [0, -1], [0, 1], [-1, 0]] # 方向 Table，用于记录各个点的上一个点是哪个方向的。-1 : 起点，0 : 下，1 : 左，2 : 右，3 : 上。 dir_table = Table.new(map.xsize, map.ysize) # 给起点做标记，记录方向 map[0, 0] = 2 dir_table[0, 0] = -1 # 起点入队列 queue.push(Path_Point.new(0, 0)) # 当队列不空时，证明还有路径点需要处理，此时进行循环 while !queue.empty? # 取出队列最前面的元素 point = queue.shift # 试探每个方向，k 表示试探方向 k = 0 while k <= 3 # 计算沿着该方向行走一步之后的新坐标 new_x = point.x + direction[k][0] new_y = point.y + direction[k][1] # 如果走到终点(Table右下角的点) if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0 # 此时要回溯路径，具体方法在后面给出 # 注意方向的反转问题 return make_reverse_path(Path_Point.new(new_x, new_y)).reverse end # 如果下一步的坐标在地图内，并且是没有走过的通路 if valid?(new_x, new_y, map) && map[new_x, new_y] == 0 # 做标记为已走过 map[new_x, new_y] = 2 # 记录该新点的来路方向，注意方向的反转问题 dir_table[new_x, new_y] = 3 - k # 新路径点入队列 queue << Path_Point.new(new_x, new_y) end # 考虑下一个方向 k += 1 end end # 如果队列为空，依然没有找到通路，返回 nil return nil end # 由路径终点倒推，产生路径 # dir_table : 用于记录来路方向的表格 def make_reverse_path(final_point, dir_table) path = [] # 设定初值 point = final_point d = dir_table[point.x, point.y] # 方向数组，方便表示向各个方向行走时的坐标增量 direction = [[1, 0], [0, -1], [0, 1], [-1, 0]] while d != -1 # 把该点放入路径 path << point # 获取来路方向 d = dir_table[point.x, point.y] # 获取来路坐标 new_x = point.x + direction[d][0] new_y = point.y + direction[d][1] # 当前点转换为来路 point = Path_Point.new(new_x, new_y) end # 此时起点还未放入路径 path << point # 此时的 path 为反转路径 return path end end
module Maze
# 记录路径点的类，每个点记录坐标和行走方向
class Path_Point
attr_accessor :x # 该点 x 坐标
attr_accessor :y # 该点 y 坐标
def initialize(x = 0, y = 0)
@x = x
@y = y
end
end
# 判断坐标是否有效（不能走出迷宫外）
# map是一个 Table 对象
def valid?(x, y, map)
return x >= 0 && y >= 0 && x < map.xsize && y < map.ysize
end
# 求迷宫的一条路径
# map : 表示迷宫的 Table 对象，0 : 允许通过，1 : 禁止通过，2 : 允许通过但是已经走过，下次走将不会考虑
def self.solve(map)
# 记录待处理路径所用队列
queue = []
# 方向数组，方便表示向各个方向行走时的坐标增量
direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
# 方向 Table，用于记录各个点的上一个点是哪个方向的。-1 : 起点，0 : 下，1 : 左，2 : 右，3 : 上。
dir_table = Table.new(map.xsize, map.ysize)
# 给起点做标记，记录方向
map[0, 0] = 2
dir_table[0, 0] = -1
# 起点入队列
queue.push(Path_Point.new(0, 0))
# 当队列不空时，证明还有路径点需要处理，此时进行循环
while !queue.empty?
# 取出队列最前面的元素
point = queue.shift
# 试探每个方向，k 表示试探方向
k = 0
while k <= 3
# 计算沿着该方向行走一步之后的新坐标
new_x = point.x + direction[k][0]
new_y = point.y + direction[k][1]
# 如果走到终点(Table右下角的点)
if new_x == map.xsize - 1 && new_y == map.ysize - 1 && map[new_x, new_y] == 0
# 此时要回溯路径，具体方法在后面给出
# 注意方向的反转问题
return make_reverse_path(Path_Point.new(new_x, new_y)).reverse
end
# 如果下一步的坐标在地图内，并且是没有走过的通路
if valid?(new_x, new_y, map) && map[new_x, new_y] == 0
# 做标记为已走过
map[new_x, new_y] = 2
# 记录该新点的来路方向，注意方向的反转问题
dir_table[new_x, new_y] = 3 - k
# 新路径点入队列
queue << Path_Point.new(new_x, new_y)
end
# 考虑下一个方向
k += 1
end
end
# 如果队列为空，依然没有找到通路，返回 nil
return nil
end
# 由路径终点倒推，产生路径
# dir_table : 用于记录来路方向的表格
def make_reverse_path(final_point, dir_table)
path = []
# 设定初值
point = final_point
d = dir_table[point.x, point.y]
# 方向数组，方便表示向各个方向行走时的坐标增量
direction = [[1, 0], [0, -1], [0, 1], [-1, 0]]
while d != -1
# 把该点放入路径
path << point
# 获取来路方向
d = dir_table[point.x, point.y]
# 获取来路坐标
new_x = point.x + direction[d][0]
new_y = point.y + direction[d][1]
# 当前点转换为来路
point = Path_Point.new(new_x, new_y)
end
# 此时起点还未放入路径
path << point
# 此时的 path 为反转路径
return path
end
end
（四）剪枝技术
说完了普通穷举和两种搜索方法，下面简单说下这个剪枝技术。剪枝技术是对于两种搜索方式有比较好的效果。那么，什么是剪枝技术呢？在深度优先搜索和广度优先搜索中，如果我们遇到了选择分支，那么我们就以某种方式进入到这个分支当中。但是，如果我们能够在进入分支之前，对分支的情况估计一下，如果满足一定的条件才进入分支，否则不进入，这就是我们所谓的“剪枝技术”。这就好像把本来应有的分支统统减掉，不去进行搜索一样。
我们举个例子，假如我们在一系列过程中要寻找最优解。现在，我们已经进行了若干步搜索，搜索到了若干解，而且这些解中最大值为20（假设数值最大的解是最优解）。那么，我们在对其他情况继续搜索的时候，如果我们能想办法在搜索之前能够估计出来这个解的上界，例如，如果沿着另外一个方向搜索，解最大值不会超过19，现在我已经有了一个值为20的解了，那么沿着该方向就完全不必继续搜索了。这就是剪枝技术。
下面是一个非常特殊的例子，虽然拿它当做剪枝的例子未必合适，但是至少说明了“剪枝”的思想。
例：计算斐波那契数列，其中，a(0)=a(1)=1，a(n+1)=a(n)+a(n-1)，即某一项是它前面两项的和。
为了简单起见，我们称斐波那契数列的第 n 项为 Fib(n)，于是，如果我们要知道Fib(n)，那么就要知道Fib(n-1)和Fib(n-2)，利用简单的递归写法，我们马上就能写出这样的程序：
def fib(n) if n == 0 || n == 1 return 1 end return fib(n-1) + fib(n-2) end
def fib(n)
if n == 0 || n == 1
return 1
end
return fib(n-1) + fib(n-2)
end
上面的这个代码比较短，原理也很清楚，就是利用分支，不断地对 n 进行缩减，最后都归结为算Fib(0)和Fib(1)。
你可以试试在计算机上调用fib(40)，然后，计算机就会算上一分钟，然后告诉你答案。这未免有点太慢了。我们看看这个方法的执行过程，以求Fib(4)为例：
Fib(4)-Fib(3)--Fib(2)-Fib(1)
| | |
| | -----Fib(0)
| |
| -------Fib(1)
|
|
-----Fib(2)--Fib(1)
|
-------Fib(0)
通过上面的图，我们可以看到，计算Fib(4)时需要Fib(3)和Fib(2)，但是在计算Fib(3)的时候，已经计算了Fib(2)，不需要再计算一遍了，但是当计算Fib(3)完毕后，Fib(2)又重新被计算了一次。你可能说，多算个一两次没什么，但是你要知道，这仅仅是算Fib(4)的情况，如果计算Fib(40)，那么重复的计算将会有相当多。计算机是算不过来的。我们看到，每计算一个值时，如果不能有效地砍掉分支，那么效率将会变得非常低。
因此，我们对此作出改进。我们在计算的过程中，把中间能用到的结果都保存下来。这样，如果下次再碰到，就不必进行分支中的内容，而是直接提取数据就好了。这样做会节省很多的时间。
请阅读以下代码，并测试，体会其中的不同：
$solution_hash = {} def fib(n) if n == 0 || n == 1 return 1 end # 如果已经算出结果，直接取出，否则再计算 a = $solution_hash[n-1].nil? ? fib(n-1) : $solution_hash[n-1] # 计算完毕后，计算结果保存，以便下回使用 $solution_hash[n-1] = a b = $solution_hash[n-2].nil? ? fib(n-2) : $solution_hash[n-2] $solution_hash[n-2] = b return a + b end
$solution_hash = {}
def fib(n)
if n == 0 || n == 1
return 1
end
# 如果已经算出结果，直接取出，否则再计算
a = $solution_hash[n-1].nil? ? fib(n-1) : $solution_hash[n-1]
# 计算完毕后，计算结果保存，以便下回使用
$solution_hash[n-1] = a
b = $solution_hash[n-2].nil? ? fib(n-2) : $solution_hash[n-2]
$solution_hash[n-2] = b
return a + b
end
在这里，虽然$solution_hash被设定为全局变量，写法可能不够严谨。但是完全可以把它写成局部变量，这个请自行思考。
在我给出的水晶代码中，也有对应的剪枝部分，可以防止重复遍历。
好了，关于穷举我就写这么多，希望不要看得不耐烦了。其实我感觉论坛上多数人对算法不太感兴趣呢，何况是这么'low'的穷举和搜索。写这个回帖的时候，我还参考了我的算法教程，不过现在想想，貌似有点小题大做了。如果以后再遇到算法问题，欢迎在讨论区发帖，我尽量会参加讨论的。
（完） |
评分
-
查看全部评分
|
写轮眼
发表于 2015-5-4 23:41:17
收藏
分享
提升卡
沉默号角
喧嚣号角
变色卡
升龙剑
楼主
发表于 2015-5-12 21:08:22
