关于python:BFS算法示例-解开密码锁的最少次数

6次阅读

共计 1938 个字符，预计需要花费 5 分钟才能阅读完成。

BFS(广度优先搜寻)是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

BFS 算法的核心思想就是把一些问题形象成图.

BFS 绝对 DFS 最次要的区别是: BFS 找到的门路肯定是最短的, 但代价是空间复杂度比 DFS 大很多.

BFS 常呈现的场景: 问题的实质就是让你在 一幅图 中找到从终点 start 到起点 target的最近间隔,BFS 算法其实就是在干这事.

一般来说在找最短门路的时候用 BFS, 其余时候还是用 DFS 多一些.

传统的 BFS 框架是从终点开始向周围扩散, 遇到起点时进行; 而双向 BFS 则是从终点和起点同时开始扩散, 当两边有交加的时候进行.

应用双向 BFS 的前提是, 必须提前晓得起点在哪里.

无论传统 BFS 还是双向 BFS, 无论做不做优化, 从 Big O 的衡量标准看, 空间复杂度都是一样的.

有一个带四个圆形拨轮的转盘锁, 每个拨轮都有 0 - 9 共 10 个数字,
每个拨轮能够高低旋转: 例如把 9 变成 0, 0 变成 9, 每次旋转只能将一个拨轮旋转 一下

import copy
from rich.console import Console
from rich import print

console = Console()  
res  = []

#~ 解开密码锁的起码次数


# 将明码向上拨动一次
def plusOne(s,j):
    ch = []
    for i in s:
        ch.append(i)

    if ch[j] == '9':
        ch[j] = str(0)
    else:
        ch[j] = str(int(ch[j]) + 1  )
        
    # print(ch)    
    res = ''        
    for i in ch:
        res += i 
    return res 

# 将明码向下拨动一次
def minusOne(s,j):
    ch = []
    for i in s:
        ch.append(i)

    if ch[j] == '0':
        ch[j] = str(9)
    else:
        ch[j] = str(int(ch[j]) - 1  )
        
    res = ''        
    for i in ch:
        res += i 
    return res 
                
# 传统 BFS, 从终点登程扩散
def openLock(deadends,target):
    
    #记录须要跳过的明码
    deads = [] 
    for i in deadends:
        deads.append(i)
        
    #记录曾经穷举过的明码, 避免走回头路
    visited = []
    q = []
    
    #从终点开始启动广度优先搜寻
    step = 0
    q.append("0000")
    visited.append("0000")
    
    while(q != None):
        sz = len(q)
        #将以后队列中的所有节点向四周扩散
        for i in range(sz):
            cur = q.pop(0)
            print(cur)
            
            #判断明码是否非法, 是否达到起点
            if cur in deads:
                continue
            
            if cur  == target:
                return step
            
            # 将一个节点的未遍历相邻节点退出队列
            for j in range(4):
                up = plusOne(cur,j)
                if up not in visited:
                    q.append(up)
                    visited.append(up)
                      
                down =  minusOne(cur,j)
                if down not in visited:
                    q.append(down)
                    visited.append(down)

        step += 1           
                    
    return -1                

# 双向 BFS                    
def both_openLock(deadends,target):
    
    #记录须要跳过的明码
    deads = [] 
    for i in deadends:
        deads.append(i)
        
    #记录曾经穷举过的明码, 避免走回头路
    visited = []
    q1 = []
    q2 = []
    
    #初始化终点和起点
    q1.append("0000")
    q2.append(target)
    
    step = 0
    
    while(q1 != None and q2 != None):
        print('q1 is' + str(q1))
        print('q2 is' + str(q2))
        temp = []
        for cur in q1:
            if cur in deads:
                continue
            if cur in q2:
                return step
            visited.append(cur)
            
            for j in range(4):
                up = plusOne(cur,j)
                if up not in visited:
                    temp.append(up)
                      
                down =  minusOne(cur,j)
                if down not in visited:
                   temp.append(down)
    
        step += 1
        print('temp is'+ str(temp))
        q1 = q2
        q2 = temp
    
              
                    
    return -1                


deadends = ["0007","5678"]
target = "2222"    
    
res =   both_openLock(deadends,target)  
print(res)