早在1952年,克劳德·香农就已经是电子信息界的传奇人物,但是对当时的普通大众来说,他仍然是个陌生人。不过在即将开始的会展后,他就人尽皆知了。

  在会议展上,香农展示了一只木制的、带有铜须的玩具老鼠,这只老鼠能够在迷宫中穿梭,最终找到出口处的金属硬币。老鼠是通过试错的方式探索迷宫的,通过胡须,它可以感知是否碰到了走不通的墙壁,如果正对的墙壁走不通,就会退到后一个格子,旋转90°,继续探测下一个方向。如果走通了迷宫,老鼠还能记住这条路线,在下一次直接完成任务。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

搜索的策略(1)——盲目搜索 算法 第1张

  其实香农的老鼠并没有那么智能,它仅仅是“记住”路线,而不是“认识”路线——在老鼠走通迷宫后,如果撤掉迷宫的墙壁,老鼠依然是按照上次的线路前进。香农可没有把这一点告诉观众,对于观众来说,这只机器老鼠简直是来自异次元的天物,是一个会思考的机器!

  这个其貌不扬的小老鼠在当年登上了《时代》和《生活》杂志的封面,有一期文章甚至用《这只老鼠比你聪明》为标题。贝尔实验室的老板们对这只老鼠印象深刻,他们在冲动中甚至要把香农拉进贝尔电话公司的董事会。

盲目搜索

  从老鼠探索迷宫的行为可以看出,它使用的深度优先搜索,这是一种简单而暴力的穷举搜索,几乎没有任何神秘性可言——找到一条路就一直走下去,直到撞墙为止,然后回溯,继续探索,我们将这种搜索策略称为“盲目搜索”。

  盲目搜索就是我们常说的“蛮力法”,又叫非启发式搜索。作为最先想到的一种所搜策略,盲目搜索是一种无信息搜索。之所以被称为“盲目”,是因为这种搜索策略只是按照预定的策略搜索解空间的所有状态,而不会考虑到问题本身的特性。我们熟悉的深度优先搜索和广度优先搜索就是两种典型的盲目搜索。

  盲目搜索的名字不太好听,容易被扣上“性能低下”的帽子,通常在找不到解决问题的规律时使用,但凡能找到某些规律,就不会选择蛮力法,可以说盲目搜索策略是最后的大招。遗憾的是,很多问题都没有明显的规律可循,很多时候我们不得不求助于蛮力法。同时,由于思路简单,盲目搜索策略通常是被人们第一个想到的,对于一些比较简单的问题,盲目搜索确实能发挥奇效。对于盲目策略来说,我们既鄙视它近似蛮力的“性能低下”,又膜拜它把一切托付给计算机的“节省脑细胞”。

  在这一章里,我们先对盲目所搜展开讨论,看看计算机带给我们的神奇的大招。同时我们也将看到,“盲目”也并非一味的蛮干,在加以改进后,算法也并非像我们想象的那样“性能低下”。

八皇后问题

  在国际象棋中,皇后(Queen)是攻击力最强的棋子,皇后可横、直、斜走,且格数不限,吃子与走法相同,往往是棋局中制胜的决定性力量,少掉一个皇后往往意味着棋局告负。皇后模拟的是欧洲中世纪时,王室自皇后娘家借来的援军,作为棋盘上最具威力的一子,皇后代表强大的援军。

  国际象棋棋手马克斯·贝瑟尔于1848年提出了一个问题:在8×8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,一共有多少种摆法?

解空间

  八皇后看起来不那么好对付,除了挨个尝试之外没什么太好的办法了。如果不考虑皇后的互相攻击,将八个皇后每行摆放一个,一共会有多少种摆法呢?

  这个问题实际是在回答要搜索的解空间,这也是问题的关键——盲目搜索并不是漫无目的的搜索,而是在一个固定的范围内寻找答案。有时候解空间的范围不太容易直接回答,此时的一种思路是将问题简化,由简单的问题入手,逐步归纳总结出最后的答案。我们不妨把问题规模缩小,把2个皇后摆放在2×2的棋盘上,看看一共有多少种摆法。

  为了叙述方便,我们把每一行的皇后都编上号,摆放在第1行的皇后是1号,第2行是2号,两个皇后一共有22=4种摆法:

搜索的策略(1)——盲目搜索 算法 第2张

  类似地,把3个皇后摆放在3×3的棋盘上时,先固定前两行的皇后,再摆放3号,此时有3种摆法:

搜索的策略(1)——盲目搜索 算法 第3张

  保持1号不动,移动2号时,会产生另外6种摆法:

搜索的策略(1)——盲目搜索 算法 第4张

  这就形成了9种摆法。最后再移动1号,会产生另外9×2=18种摆法,因此把3个皇后摆放在3×3的棋盘上一共有33=27种摆法。以此类推,八皇后问题的解空间是88=16777216。仅仅是8个棋子就产生了如此多的解空间,没有计算机可真是累人。

搜索策略

  160多万的解空间真的要全部搜索吗?当然不会,每个皇后都有自己的攻击范围,在摆放第1个皇后时,其它皇后的摆放位置也被某种程度的限定了:

搜索的策略(1)——盲目搜索 算法 第5张

  为了避开皇后1的攻击范围,第2个皇后只能在剩下的6浅色格子中选择;而2号皇后落子后,又将对其它皇后做出进一步限制;到了第3行,摆放位置可能只剩下4个:

搜索的策略(1)——盲目搜索 算法 第6张

  我们并不会傻乎乎的对所有解空间进行搜索,而是随着步骤的进行,避开了绝对不可能的解,从而有效地缩小了解空间的范围。

  之后的皇后也采用这样的办法来摆放,这是一种试探法——先把皇后摆放在“安全”位置,然后设置她的攻击范围,再在下一个安全位置摆放下一个皇后;如果下一个皇后没有“安全”位置了,那么“悔棋”,重新摆放上一皇后;再不行就“大悔棋”,上上一个皇后也重新摆放:

搜索的策略(1)——盲目搜索 算法 第7张

  这种带回溯的方法就是我们熟知的深度优先搜索——只管埋头前进,撞到墙才后退。

  虽然我们知道怎么摆放棋子,但计算机并不知道,在编写代码之前必须先完成从现实世界到软件设计的映射。

  对于棋盘问题,一个有效的数据结构是8×8的二维列表,列表中的每个元素代表棋盘上的一个方格;方格有三种状态,闲置、落子、是否处于被攻击状态,分别用0、1、2表示,这些构成了八皇后问题的数据模型。

  接下来是摆放棋子的行为。我们按行来摆放,每行摆放一个皇后,每次落子后都将把棋盘的部分方格设置为“被攻击”。代码:

 1 import copy
 2 
 3 class EightQueen:
 4     def __init__(self):
 5         # 棋盘单元格的初始状态, 被皇后占据状态, 被皇后攻击状态
 6         self.s_init, self.s_queen, self.s_attack = 0, 1, 2
 7         # 棋盘的行数和列数
 8         self.row_num, self.col_num  = 8, 8
 9         # 棋盘
10         self.chess_board = [[self.s_init] * self.row_num for i in range(self.row_num)]
11         # 解决方案列表
12         self.answer_list = []
13 
14     def start(self):
15         self.put_down(self.chess_board, 0)
16 
17     def put_down(self, curr_board, row):
18         ''' 在棋盘的第row行落子 '''
19         if row == self.row_num:
20             self.answer_list.append(curr_board)
21             return
22 
23         for col in range(self.col_num):
24             if self.enable(curr_board, row, col):
25                 # 复制棋盘上的状态, 以便回溯
26                 bord = copy.deepcopy(curr_board)
27                 # 将皇后放在第row行第col列中
28                 bord[row][col] = self.s_queen
29                 # 设置第row行第col列的皇后的攻击范围
30                 self.set_attack(bord, row, col)
31                 # 继续在下一行落子
32                 self.put_down(bord, row + 1)
33 
34     def enable(self, curr_board, row, col):
35         '''是否可以在棋盘的第row行第col列落子'''
36         return curr_board[row][col] == self.s_init
37 
38     def set_attack(self, curr_board, row, col):
39         '''设置第row行第cell列的皇后的攻击范围'''
40         # 最后一行没有必要设置攻击范围
41         if row == self.row_num - 1:
42             return
43 
44         # 正下方的攻击范围
45         for next_row in range(row + 1, self.row_num):
46             curr_board[next_row][col] = self.s_attack
47         # 左斜下的攻击范围
48         left_col = col - 1
49         for next_row in range(row + 1, self.row_num):
50             if left_col >= 0:
51                 curr_board[next_row][left_col] = self.s_attack
52                 left_col -= 1
53             else:
54                 break
55         # 右斜下的攻击范围
56         right_col = col + 1
57         for next_row in range(row + 1, self.row_num):
58             if right_col < self.col_num:
59                 curr_board[next_row][right_col] = self.s_attack
60                 right_col += 1
61             else:
62                 break
63 
64     def display(self):
65         '''打印所有方案'''
66         length = len(self.answer_list)
67         if length == 0:
68             print('No answers!')
69             return
70 
71         print('There are %d answers!' % length)
72         for i in range(0, length):
73             print('-' * 20, 'answer', i + 1, '-' * 20)
74             bord = self.answer_list[i]
75             for row in bord:
76                 for c in row:
77                     if c == self.s_queen:
78                         print('%4d' % 1, end='')
79                     else:
80                         print('%4d' % 0, end='')
81                 print()
82 
83 if __name__ == '__main__':
84     eq = EightQueen()
85     eq.start()
86     eq.display()

  在set_attack()中,由于是逐行落子,所以只需要处理位于皇后下方的单元格。每次set_attack后,棋盘上的安全位置就又少了一些,下次落子只能落在下一行的“安全”位置上。

  enable()用来判断是否安全,方法很简单,只需检查方格的状态是否是初始状态。

  在put_down()中,我们以一种“顺序”的方式逐行落子,如果正好摆满了八个皇后,则该种摆法是八皇后问题的一个解;如果没有任何“安全”位置能够摆放下一个皇后,则进行“悔棋”操作。每落一子都要记住棋盘的状态,只有这样才能回溯,以便进行“悔棋”。每落一子都相当于在解空间内进行了一次搜索,如果加入计数器的话,会发现最终只进行了15720次搜索,这可比之前少了两个数量级。

  一共有92种解,其中一种:

搜索的策略(1)——盲目搜索 算法 第8张

  高斯认为八皇后问题有76种方案,1854年在柏林的象棋杂志上不同的作者发表了40种不同的解。看来没有计算机的帮助,带有穷举性质的盲目搜索还真是一种不可尝试的方法。

同根同源的另一种方法

  在EightQueen中,我们的方案是每次落子都重置棋盘的“安全”状态,与之对应的另一种思路是“先检查,再落子”,从而省去了方格的“被攻击”状态。

  仍然是按行来摆放,每行摆放一个皇后,摆放前需要检查待摆放的棋子是否处于其它皇后的攻击范围内,只有不在攻击范围内时才允许摆放,否则“缓棋”,重新摆放上一个皇后,代码如下:

 

 1 import copy
 2 
 3 class EightQueen_2:
 4     def __init__(self):
 5         # 棋盘单元格的初始状态, 被皇后占据状态
 6         self.s_init, self.s_queen = 0, 1
 7         # 棋盘的行数和列数
 8         self.row_num, self.col_num = 8, 8
 9         # 棋盘
10         self.chess_board = [[self.s_init] * self.row_num for i in range(self.row_num)]
11         # 解决方案列表
12         self.answer_list = []
13 
14     def start(self):
15         self.put_down(self.chess_board, 0)
16 
17     def put_down(self, curr_board, row):
18         ''' 在棋盘的第row行落子 '''
19         if row == self.row_num:
20             self.answer_list.append(curr_board)
21             return
22 
23         for col in range(self.col_num):
24             # 是否会和已经在棋盘上的皇后互相攻击
25             if self.enable_attacked(curr_board, row, col) == False:
26                 # 复制棋盘上的状态, 以便回溯
27                 bord = copy.deepcopy(curr_board)
28                 # 将皇后放在第row行第col列中
29                 bord[row][col] = self.s_queen
30                 # 继续在下一行落子
31                 self.put_down(bord, row + 1)
32 
33     def enable_attacked(self, curr_board, row, col):
34         ''' 第row行第col列的皇后是否会和已经在棋盘上的皇后互相攻击 '''
35         # 是否会和第col列的皇后互相攻击
36         for last_row in range(row - 1, -1, -1):
37             if curr_board[last_row][col] == self.s_queen:
38                 return True
39         # 是否会和左斜上的皇后互相攻击
40         left_col = col - 1
41         for last_row in range(row - 1, -1, -1):
42             if left_col >= 0 and curr_board[last_row][left_col] == self.s_queen:
43                 return True
44             left_col -= 1
45         # 是否会和右斜上的皇后互相攻击
46         right_col = col + 1
47         for last_row in range(row - 1, -1, -1):
48             if right_col < self.col_num and curr_board[last_row][right_col] == self.s_queen:
49                 return True
50             right_col += 1
51 
52         return False
53 
54     def display(self):
55         '''打印所有方案'''
56         length = len(self.answer_list)
57         if length == 0:
58             print('No answers!')
59             return
60         print('There are %d answers!' % length)
61         for i in range(0, length):
62             print('-' * 20, 'answer', i + 1, '-' * 20)
63             bord = self.answer_list[i]
64             for row in bord:
65                 for c in row:
66                     print('%4d' % c, end='')
67                 print()
68 
69 if __name__ == '__main__':
70     eq = EightQueen_2()
71     eq.start()
72     eq.display()

  enable_attacked()用于判断待摆放的棋子是否处于其它皇后的攻击范围内,由于是逐行落子,下方没有皇后,所以只需要考虑上方的皇后即可

  EightQueen_2仅仅是用比较代替了修改,和EightQueen并没有本质的区别,只是因为EightQueen更符合人类的行为,所以看起来也更高级一点。

  

   作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,非商业用途! 

  扫描二维码关注公众号“我是8位的”

搜索的策略(1)——盲目搜索 算法 第9张

,

  出处:http://www.cnblogs.com/bigmonkey

  本文以学习、研究和分享为主,如需转载,请联系本人,标明作者和出处,非商业用途! 

  扫描二维码关注公众号“我是8位的”

搜索的策略(1)——盲目搜索 算法 第10张

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄