算法第十二期——BFS-判重
目录
BFS判重
Python判重方法: set、字典
set()判重
字典判重
例题：跳蚱蜢
思路
【建模】
去重
代码一：字典去重（用list实现队列）
代码二：set()去重（用list实现队列）
代码二：set()去重（用deque实现队列） 推荐！
BFS判重
- BFS=队列
- BFS:逐步扩展下一层，把扩展出的下一层状态放进队列中处理。
- 判重：若这些状态有相同的，只搜索一次，即进入队列一次，提高运行效率。
Python判重方法: set、字典
set()判重
- set()函数创建一个无序、不重复元素集
- 关系测试，删除重复数据，计算交集、差集、并集、补集
# 对字符串去重
a = set ()
a.add("678"); print(a) # {'678'}
a.add("123"); print(a) # {'678', '123'}
a.add("678"); print(a) # {'678', '123'} 去重
b=sorted(a); print(b) # ['123', '678'] sorted()返回的是列表
# 不能用sort()，因为sort()是list的方法
# 对单个字符串去重是对每个字母去重
s=set("aabc"); print(s)# {'a', 'c', 'b'}
print(len(s)) # 3 有多少种不同的字母
print(sorted(s)) # ['a', 'b', 'c'] 排序
# 对多个字符串去重是对每个字符串去重
s=set(["aabc","bca","aabc"]); print(s) # {'aabc', 'bca'}
# 对数字去重
b = set()
b.add(678) ; print(b)# {678}
b.add(123) ; print(b)# {123, 678}
b. add(678); print(b)# {123, 678}
a=set([1,1,2,3,5]); print(a) # {1, 2, 3, 5}
b=set([1,2,3,4]);print(b) # {1, 2, 3, 4}
print(a-b) # 差集，在集合a 中但不在集合b 中的元素 # {5}
print(b-a) # 差集 # {4}
print(a&b) # 交集，同时在集合a和b中的共同元素。 # {1, 2, 3}
print (a|b) # 并集，包括集合a和b中所有元素。 # {1, 2, 3, 4, 5}
print(a^b) # 补集，包括集合a和b的非共同元素。 # {4, 5}字典判重
- 字典:无序、可变、有索引的集合。
- 字典:用花括号定义，有键和值。
print(a^b) # 补集，包括集合a和b的非共同元素。 # {4, 5}
#%%
a={5:"xy"}
# 没有这个键就添加，有这个键就修改（相当于去重）
a[1]="cb" # 添加键值对
a[2]="kd"
a[2]="af" # 修改键值对
print(a) # {5: 'xy', 1: 'cb', 2: 'af'}
b=sorted(a.items()) ; print(b) # 按键排序[(1, 'cb'), (2, 'af'), (5, 'xy')]
b=sorted(a.values()) ; print(b) # 值排序 ['af', 'cb', 'xy']
b=sorted(a.items(),key=lambda x: x[0]); print(b) # 按键排序 [(1, 'cb'), (2, 'af'), (5, 'xy')]
b=sorted(a.items(),key=lambda x: x[1]); print(b) # 按值排序 [(2, 'af'), (1, 'cb'), (5, 'xy')]
a={"food" :" xy" , " price" :555}
a[3]=899 # 键值对可以是不同类型
print(a) # {'food': ' xy', ' price': 555, 3: 899}例题：跳蚱蜢
跳蚱蜢2017年第八届省赛，lanqiao0J题号642
【题目描述】
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下图所示： 有 9 只盘子，排成 1 个圆圈。 其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 1 ~ 8。
每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1−8 换位，2−7换位,...），至少要经过多少次跳跃？
思路
- 从起始状态到终止状态，求最少跳跃次数
- 最短路径问题
- 用BFS
【建模】
- 直接让蚱蜢跳到空盘有点麻烦，因为有很多在跳蚱蜢。
- 反过来看，让空盘跳，跳到蚱蜢的位置，简单多了，只有一个空盘在跳。
化圆为线
- 题目是一个圆圈，不好处理，用一个建模技巧“化圆为线”，把圆形转换为线形。
- 把空盘看成0，有9个数字{0,1,2,3,4,5,6,7,8}，一个圆圈上的9个数字，拉直成了一条线上的9个数字，这条线的首尾两个数字0和8处理成相连的。
- 八数码问题:有9个数字{0,1,2,3,4,5,6,7,8}，共有9!=362880种排列，不算多。
最短路径
- 初始状态:“012345678”，目标状态:“087654321”。
- 从初始状态“012345678”跳一次，有4种情况:0跳到1，2,7,8这几个点，即“1023456783"、“210345678”、“812345670”、“712345608"。
- 然后从这4种状态继续跳到下一种状态，一直跳到目标状态为止，第一个出现的‘’087654321就是最短路径。
- 用BFS扩展每一层。
- 每一层就是蚱蜢跳了一次，扩展到某一层时发现终点“087654321”，这一层的深度就是蚱蜢跳跃的次数。
第1步到第2步，有4种跳法;第2步到第3步，有4^2种;...;第20步，有4^20= 1万亿种，超时。
去重
判重：判断有没有重复跳，如果跳到一个曾经出现过的情况，就不用往下跳了。一共只有9!= 362880种情况。
代码复杂度：在每一层，能扩展出最少4种、最多362880种情况；若最后算出的答案是20层，那么最多算20*362880= 7,257,600次。在代码中统计实际的计算次数，是1451452次。
队列：最多有9!=362880种情况进入队列。
代码一：字典去重（用list实现队列）
- 用list实现队列
- 速度慢：3s，超时
def insertQueue(q: list, dir: int, news: tuple, vis): #
pos = news[1] # 0的位置
status = news[0] # 当前状态
insertPos = (pos + dir + 9) % 9 # 难点：化圆为线
# 将字符串转为列表比较好处理
t = list(status)
t[pos], t[insertPos] = t[insertPos], t[pos] # 空盘子与跳到的数交换
# 处理完再转回字符串
addStatus = "".join(t)
# 去重
if addStatus not in vis: # 当前状态不在vis（没访问过）
vis[addStatus] = 1 # 向字典vis添加，用去重作用
q.append((addStatus, insertPos, news[2] + 1)) # 添加到队尾
q = [("012345678",0,0)] # 到当前状态，空盘子0的位置，步数
vis = {"012345678": 1} # 访问情况，用于去重
while q: # 队列不为空
news = q.pop(0) # 弹出队头
if news[0] == "087654321": # 结束条件：到达了目标状态，输出最少步数
print(news[2]) # news[2]三元组第三个：步数。
break
#扩展下一层的4种情况
insertQueue(q, -2, news,vis) # 左边跳一个
insertQueue(q, -1, news,vis) # 左边跳两个
insertQueue(q, 1, news, vis) # 右边跳一个
insertQueue(q, 2, news, vis) # 右边跳两个代码二：set()去重（用list实现队列）
用list实现队列
这个方法比上面简单一点。
# 与其他代码不同的地方已用注释标出
def insertQueue(q: list, dir: int, news: tuple, vis):
pos = news[1]
status = news[0]
insertPos = (pos + dir + 9) % 9
t = list(status)
t[pos], t[insertPos] = t[insertPos], t[pos]
addStatus = "".join(t)
if addStatus not in vis:
vis.add(addStatus) # 访问了就保存到vis
q.append((addStatus, insertPos, news[2] + 1))
q = [("012345678",0,0)]
vis = set() # vis访问情况。用set()去重
vis.add("012345678") # 初始化第一个状态，存到vis
while q:
news = q.pop(0)
if news[0] == "087654321":
print(news[2])
break
insertQueue(q, -2, news,vis)
insertQueue(q, -1, news,vis)
insertQueue(q, 1, news, vis)
insertQueue(q, 2, news, vis)代码二：set()去重（用deque实现队列） 推荐！
用deque实现队列
速度快：1.4s
# 与其他代码不同的地方已用注释标出
from collections import * # 需导入collections
def insertQueue(q: list, dir: int, news: tuple, vis):
pos = news[1]
status = news[0]
insertPos = (pos + dir + 9) % 9
t = list(status)
t[pos], t[insertPos] = t[insertPos], t[pos]
addStatus = "".join(t)
if addStatus not in vis:
vis.add(addStatus) # 访问了就保存到vis
q.append((addStatus, insertPos, news[2] + 1))
q = deque() # 用deque去重
q.append(("012345678",0,0)) # 初始化队列
vis = set() # vis访问情况
vis.add("012345678") # 初始化第一个状态，存到vis
while q:
news = q.popleft() # 弹出队头
if news[0] == "087654321":
print(news[2])
break
insertQueue(q, -2, news,vis)
insertQueue(q, -1, news,vis)
insertQueue(q, 1, news, vis)
insertQueue(q, 2, news, vis)