搜索的策略(3)——觐天宝匣上的拼图

搜索的策略(3)——觐天宝匣上的拼图小说《溥仪藏宝录》讲述了一个曲折离奇的故事。在故事中,溥仪试图利用藏有大清皇家宝藏秘密的宝盒——“觐天宝匣”复辟清朝。这个宝匣是他从宫中带走的唯一宝物,里面藏着富可敌国的巨额宝藏,足以发动第三次世界大战。由于种种原因,溥仪将宝匣藏于太极皇陵。抗战期间,爱国人士崔二侉子带领众人深入太极皇陵,盗走了觐天

大家好,欢迎来到IT知识分享网。

  小说《溥仪藏宝录》讲述了一个曲折离奇的故事。在故事中,溥仪试图利用藏有大清皇家宝藏秘密的宝盒——“觐天宝匣”复辟清朝。这个宝匣是他从宫中带走的唯一宝物,里面藏着富可敌国的巨额宝藏,足以发动第三次世界大战。由于种种原因,溥仪将宝匣藏于太极皇陵。抗战期间,爱国人士崔二侉子带领众人深入太极皇陵,盗走了觐天宝匣。此后的几年里,参与盗宝的人陆续神秘死亡,崔二侉子将宝匣交给侦探出身的萧剑南。其后六十多年的时间里,萧剑南用了一生时间试图寻找到事情的真相,直到临终,才将这件事告知自己的孙子萧伟。萧伟与好友高阳、赵颖试图打开觐天宝匣……

  宝匣共有三层,每层都有一锁,第一层是“子午鸳鸯芯”,第二层是“对顶梅花芯”,而第三层是“天地乾坤芯”,由高丽制锁名匠设计,没有钥匙,如果不是受过专门训练,根本无法开启。任何外力企图强行打开,都会触发机关,启动刀具装置,将其中所藏之物绞得粉碎。

搜索的策略(3)——觐天宝匣上的拼图

  觐天宝匣的正上方刻有高丽名匠李舜臣在大韩海峡击败进犯日军的场景,被切分成九九八十一个小块,组成了拼图游戏中最复杂的“九九拼图”。 九九拼图是觐天宝匣的护盾,只有将拼图复原才能看到“子午鸳鸯芯”。在这里,我们感兴趣的不是觐天宝匣的三重锁,而是拼图护盾,看看如何借助计算机的帮助来激活成功教程护盾。

构建数据模型

  第一步仍然是构建数据模型,建立从实际问题到软件问题的映射。在书中,高阳想到了一个聪明的做法——把整体图案用相机拍照,再把照片用PS切分成小块并一一编号,只要把编号移动至顺序排列,问题就解决了 。

  我们使用高阳的做法,一个用一个n×n的二维列表存储n×n的拼图,列表中的每个元素都是拼图的一个小块。对于一个被复原的三三拼图来说,二维列表的数据:

搜索的策略(3)——觐天宝匣上的拼图

  拼图游戏需要有一个“图眼”,否则碎片无法移动,我们选择右下角的碎片作为图眼:

搜索的策略(3)——觐天宝匣上的拼图

  可移动的碎片共有8个,编写移动这8个碎片的代码并不容易,需要加入大量的判断。不妨换一种思路,在游戏中只有图眼可以移动,这样只需要将图眼和目标位置的数据互相交换就可以完成移动操作:

搜索的策略(3)——觐天宝匣上的拼图

  依然使用差向量表示上、右、下、左四个方向:(0, 1), (-1, 0), (0, -1), (1, 0),当图眼向某个方向移动时,目标位置只需要用图眼的当前位置加上该方向的差向量即可。我们使用一个名为JigsawPuzzle的类完成拼图游戏,它的基本数据模型如下:

 

 1 class JigsawPuzzle:
 2     def __init__(self, n=3):
 3         self.n = n
 4         # 成功状态,列表元素按照从左到右,从上到下的顺序依次排列
 5         self.succ_img = []
 6         for i in range(n):
 7             self.succ_img.append(list(range(n * i, n * i + n)))
 8         # #用空白符号作为图眼的值
 9         self.eye_val = ' '
10         # 将右下角的碎片作为图眼
11         self.succ_img[n - 1][n - 1] = self.eye_val
12         # “图眼”移动的方向, 上、右、下、左
13         self.v_move = [(0, 1), (-1, 0), (0, -1), (1, 0)]
14         # 被打乱顺序的拼图
15         self.confuse_img = self._confuse()
16         # 已经被访问过的拼图状态
17         self.visited_list = []
18         # 拼图步骤
19         self.answer = None
20 
21     def _confuse(self):
22         ''' 将拼图打乱顺序 '''
23         # 将图眼随机移动 n * n * 10 次
24         tar_img = copy.deepcopy(self.succ_img)
25         from_x, from_y = self.n - 1, self.n - 1
26         for i in range(self.n ** 2 * 10):
27             # 选择一个随机方向
28             v_x, v_y = random.choice(self.v_move)
29             to_x, to_y = from_x + v_x, from_y + v_y
30             if self.enable(to_x, to_y):
31                 # 向选择的随机方向移动
32                 self.move(tar_img, from_x, from_y, to_x, to_y)
33                 from_x, from_y = to_x, to_y
34 
35         return tar_img
36 
37     def is_succ(self, curr_img):
38         '''
39         是否完成拼图
40         :param curr_img: 当前拼图
41         :return:
42         '''
43         for i, row in enumerate(curr_img):
44             for j, n in enumerate(row):
45                 print(i, j, n, self.succ_img[i][j])
46                 if n != self.succ_img[i][j]:
47                     return False
48         return True
49 
50     def enable(self, to_x, to_y):
51         '''
52          图眼是否能够移动到to位置
53         :param to_x: 图眼的行索引
54         :param to_y: 图眼的列索引
55         :return:
56         '''
57         return 0 <= to_x < self.n and 0 <= to_y < self.n
58 
59     def move(self, curr_img, from_x, from_y, to_x, to_y):
60         '''
61         将图眼从from移动到to
62         '''
63         curr_img[from_x][from_y], curr_img[to_x][to_y] = curr_img[to_x][to_y], curr_img[from_x][from_y]

  enable()方法用于边界校验;move()用于移动图眼,它做的仅仅是将列表中的两个元素互换位置。_confuse()作为私有方法,用于打乱拼图的顺序。像洗牌方法一样随机放置列表中的元素并不能保证拼图一定能够还原,因此稳妥的方法是使用随机移动若干次图眼。

广度优先搜索

  第一个想到的策略仍然是盲目策略,穷举所有的移动,直到拼图还原为止。这里我们选择广度优先搜索作为搜索策略。

  广度优先搜索是另一种盲目搜索算法,如果我们把所有要搜索的状态组成一棵树,那么广度优先搜索就是按照层序搜索所有节点,直到搜完整棵树为止:

搜索的策略(3)——觐天宝匣上的拼图

  在拼图中,图眼每次至多可以向四个方向移动,这四个方向构成了搜索的“一层”,每一层的状态又可以继续展开:

搜索的策略(3)——觐天宝匣上的拼图

  注意到第三层的第四个状态又回到了原点,继续遍历这个状态是没有意义的,在编写代码时可以使用visited_list存储所有被访问过的拼图状态,如果碰到某一个状态被访问过,则直接略过:

 1     def has(self, curr_img):
 2         '''
 3         curr_img是否已经被访问过
 4         :param curr_img:
 5         :return:
 6         '''
 7         for s in self.visited_list:
 8             if s == curr_img:
 9                 return True
10         return False

  广度优先搜索通常使用队列的结构,样本代码如下:

 1 from queue import Queue
 2 def bfs(node):
 3     ''' 图的广度优先搜索'''
 4     if node is None:
 5         return
 6    queue = Queue()
 7    nodeSet = set()
 8    queue.put(node)
 9    nodeSet.add(node)
10    while not queue.empty():
11        cur = queue.get()             # 弹出元素
12        for next in cur.nexts:          # 遍历元素的相邻节点
13            if next not in nodeSet:    # 若相邻节点没有入过队列,加入队列
14                 nodeSet.add(next)
15                 queue.put(next)          

  样本代码仅仅是遍历了所有节点,而拼图游戏要做到的除了回答“经过多少遍历才能能复原拼图”之外,还要寻找复原的步骤,所以我们需要构造一个结构将复原步骤存储起来:

1 class Node:
2     ''' 拼图状态链表, 每一个链表元素指向上一个拼图状态 '''
3     def __init__(self, img, parent_node):
4         self.img = img
5         self.parent = parent_node

  Node中存储某一步拼图的状态,并用parent指向它的上一个状态。现在可以使用深度优先搜索的模板编写代码

 1     def bfs(self):
 2         ''' 广度优先搜索 '''
 3         queue = Queue()
 4         queue.put(Node(self.confuse_img, None))
 5
 6         while not queue.empty():
 7             curr_node = queue.get()
 8             curr_img = curr_node.img
 9             self.visited_list.append(curr_img)
10
11             # 检测拼图是否正确
12             if self.is_succ(curr_img):
13                 self.answer = curr_node
14                 break
15
16             # curr_img中图眼的位置
17             x, y = self.search_eye(curr_img)
18             # 向四个方向进行广度优先搜索
19             for v_x, v_y in self.v_move:
20                 to_x, to_y = x + v_x, y + v_y
21                 if not self.enable(to_x, to_y):
22                     continue
23
24                 curr_copy = copy.deepcopy(curr_img)
25                 self.move(curr_copy, x, y, to_x, to_y)
26                 # 判断curr_copy的状态是否曾经搜索过
27                 if not self.has(curr_copy):
28                     next_node = Node(curr_copy, curr_node)
29                     queue.put(next_node)

  搜索过程将产生很多由不同的Node链表,只有最终指“复原”状态的链表才是有用的。

  完整代码:

 

  1 from queue import Queue
  2 import random
  3 import copy
  4 from os import system
  5 import time
  6 
  7 class Node:
  8     ''' 拼图状态链表, 每一个链表元素指向上一个拼图状态 '''
  9     def __init__(self, img, parent_node):
 10         self.img = img
 11         self.parent = parent_node
 12 
 13 class JigsawPuzzle:
 14     def __init__(self, n=3):
 15         self.n = n
 16         # 成功状态,列表元素按照从左到右,从上到下的顺序依次排列
 17         self.succ_img = []
 18         for i in range(n):
 19             self.succ_img.append(list(range(n * i, n * i + n)))
 20         # #用空白符号作为图眼的值
 21         self.eye_val = ' '
 22         # 将右下角的碎片作为图眼
 23         self.succ_img[n - 1][n - 1] = self.eye_val
 24         # “图眼”移动的方向, 上、右、下、左
 25         self.v_move = [(0, 1), (-1, 0), (0, -1), (1, 0)]
 26         # 被打乱顺序的拼图
 27         self.confuse_img = self._confuse()
 28         # 已经被访问过的拼图状态
 29         self.visited_list = []
 30         # 拼图步骤
 31         self.answer = None
 32 
 33     def _confuse(self):
 34         ''' 将拼图打乱顺序 '''
 35         # 将图眼随机移动 n * n * 10 次
 36         tar_img = copy.deepcopy(self.succ_img)
 37         from_x, from_y = self.n - 1, self.n - 1
 38         for i in range(self.n ** 2 * 10):
 39             # 选择一个随机方向
 40             v_x, v_y = random.choice(self.v_move)
 41             to_x, to_y = from_x + v_x, from_y + v_y
 42             if self.enable(to_x, to_y):
 43                 # 向选择的随机方向移动
 44                 self.move(tar_img, from_x, from_y, to_x, to_y)
 45                 from_x, from_y = to_x, to_y
 46 
 47         return tar_img
 48 
 49     def is_succ(self, curr_img):
 50         '''
 51         是否完成拼图
 52         :param curr_img: 当前拼图
 53         :return:
 54         '''
 55         for i, row in enumerate(curr_img):
 56             for j, n in enumerate(row):
 57                 print(i, j, n, self.succ_img[i][j])
 58                 if n != self.succ_img[i][j]:
 59                     return False
 60         return True
 61 
 62     def enable(self, to_x, to_y):
 63         '''
 64          图眼是否能够移动到to位置
 65         :param to_x: 图眼的行索引
 66         :param to_y: 图眼的列索引
 67         :return:
 68         '''
 69         return 0 <= to_x < self.n and 0 <= to_y < self.n
 70 
 71     def move(self, curr_img, from_x, from_y, to_x, to_y):
 72         '''
 73         将图眼从from移动到to
 74         '''
 75         curr_img[from_x][from_y], curr_img[to_x][to_y] = curr_img[to_x][to_y], curr_img[from_x][from_y]
 76 
 77     def has(self, curr_img):
 78         '''
 79         curr_img是否已经被访问过
 80         :param curr_img:
 81         :return:
 82         '''
 83         for s in self.visited_list:
 84             if s == curr_img:
 85                 return True
 86         return False
 87     def search_eye(self, img):
 88         '''
 89         找到img中图眼的位置
 90         :param img:
 91         :return: (x,y)
 92         '''
 93         # “图眼”的值是eye_val,打乱顺序后需要寻找到图眼的位置
 94         for x in range(self.n):
 95             for y in range(self.n):
 96                 if self.eye_val == img[x][y]:
 97                     return  x, y
 98 
 99     def bfs(self):
100         ''' 广度优先搜索 '''
101         queue = Queue()
102         queue.put(Node(self.confuse_img, None))
103 
104         while not queue.empty():
105             curr_node = queue.get()
106             curr_img = curr_node.img
107             self.visited_list.append(curr_img)
108 
109             # 检测拼图是否正确
110             if self.is_succ(curr_img):
111                 self.answer = curr_node
112                 break
113 
114             # curr_img中图眼的位置
115             x, y = self.search_eye(curr_img)
116             # 向四个方向进行广度优先搜索
117             for v_x, v_y in self.v_move:
118                 to_x, to_y = x + v_x, y + v_y
119                 if not self.enable(to_x, to_y):
120                     continue
121 
122                 curr_copy = copy.deepcopy(curr_img)
123                 self.move(curr_copy, x, y, to_x, to_y)
124                 # 判断curr_copy的状态是否曾经搜索过
125                 if not self.has(curr_copy):
126                     next_node = Node(curr_copy, curr_node)
127                     queue.put(next_node)
128 
129     def start(self):
130         self.bfs()
131 
132 def display(answer):
133     ''' 在控制台打印动态效果(仅对三三拼图有效) '''
134     stack = []
135     node = answer
136     while node is not None:
137         stack.append(node.img)
138         node = node.parent
139     while stack != []:
140         system('cls')
141         status_list = [i for item in stack.pop() for i in item]
142         print(''''
143             * * * * *
144             * %s %s %s *
145             * %s %s %s *
146             * %s %s %s *
147             * * * * *'''  % tuple(status_list))
148         time.sleep(1)
149 
150 if __name__ == '__main__':
151     puzzle = JigsawPuzzle(n=3)
152     puzzle.start()
153     answer = puzzle.answer
154     while answer is not None:
155         print(answer.img)
156         answer = answer.parent
157 
158     display(puzzle.answer)

 

 

 

  如果拼图的初始状态是[[3, 0, 2], [1, 7, ‘ ‘], [6, 5, 4]],则程序打印的复原顺序是:

[[0, 1, 2], [3, 4, 5], [6, 7, ‘ ‘]]

[[0, 1, 2], [3, 4, ‘ ‘], [6, 7, 5]]

[[0, 1, 2], [3, ‘ ‘, 4], [6, 7, 5]]

[[0, ‘ ‘, 2], [3, 1, 4], [6, 7, 5]]

[[‘ ‘, 0, 2], [3, 1, 4], [6, 7, 5]]

[[3, 0, 2], [‘ ‘, 1, 4], [6, 7, 5]]

[[3, 0, 2], [1, ‘ ‘, 4], [6, 7, 5]]

[[3, 0, 2], [1, 7, 4], [6, ‘ ‘, 5]]

[[3, 0, 2], [1, 7, 4], [6, 5, ‘ ‘]]

[[3, 0, 2], [1, 7, ‘ ‘], [6, 5, 4]]

  打印结果自下而上构成了复原的每一个步骤:

搜索的策略(3)——觐天宝匣上的拼图

  这种盲目搜索法对付3×3的小型拼图尚可,当规模是9×9时就有些力不从心了。在dfs()中,每一移动一个碎片,都将产生4种新的移动,又是个指数爆炸的问题。能否在短时间算出九九拼图,全看运气和人品,高阳的程序就运行了将近两天时间。在下一章里,我们将继续搜索的探讨,使用更智能、更高效的搜索算法复原觐天宝匣的拼图。


   作者:我是8位的

  出处:搜索的策略(3)——觐天宝匣上的拼图

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

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

搜索的策略(3)——觐天宝匣上的拼图

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/33275.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信