## BFS 原

jit-hakase

#BFS算法 ###走迷宫的最短路径 问题: 给出一个起点和终点, 求起点走到终点的最短距离. 思路: 穷举所有可能, 按步数递增依次搜寻. 起点(0,0) 终点(4,4) 1为墙(不可走) python code

from queue import Queue

M = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
]

V = [[False for j in range(5)] for i in range(5)]

dx = [-1,  1,  0,  0]
dy = [ 0,  0, -1,  1]

class Node:
def __init__(self, x, y, step):
self.x, self.y, self.step = x, y, step

def bfs(start_x, start_y):
que = Queue()
que.put(Node(start_x, start_y, 0))

while not que.empty():
node = que.get()
x, y, step = node.x, node.y, node.step

for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx<0 or ny<0 or nx>4 or ny>4:
continue
if V[nx][ny] or M[nx][ny]==1:
continue
if nx==4 and ny==4:
return step+1

que.put(Node(nx, ny, step+1))
V[nx][ny] = True

ans = bfs(0, 0)
print(ans)

###八数码(九宫问题) 问题: 3×3棋盘上有1~8的数字和一个空格, 每次移动空格可以和相邻数字交换,给出一个初始状态和一个目标状态, 找出最少的移动步骤. 思路: 同走迷宫, 多了中途产生的状态处理. 必须把已经出现过的状态记录在集合中, 防止搜索重复节点导致搜索树停滞. python不支持将列表放在集合中,用技巧存储状态转换的整数. python code

from queue import Queue
import copy

M = [
[0, 8, 7],
[6, 5, 4],
[3, 2, 1]
]

T = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]

S = set()

dx = [-1,  1,  0,  0]
dy = [ 0,  0, -1,  1]

class Node:
def __init__(self, x, y, stat, step):
self.x, self.y = x, y
self.stat, self.step = stat, step

def calc_value(stat):
weight, sum = 1, 0
for i in range(3):
for j in range(3):
sum += stat[i][j]*weight
weight *= 10
return sum

def bfs():
que = Queue()
start_node = Node(0, 0, copy.deepcopy(M), 0)
que.put(start_node)

while not que.empty():
node = que.get()
x, y = node.x, node.y
stat, step = node.stat, node.step

for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx<0 or ny<0 or nx>2 or ny>2:
continue

new_stat = copy.deepcopy(stat)
new_stat[nx][ny], new_stat[x][y] = new_stat[x][y], new_stat[nx][ny]

if calc_value(new_stat) in S:
continue

if new_stat == T:
return step+1

que.put(Node(nx, ny, new_stat, step+1))

ans = bfs()
print(ans)

from queue import Queue
import copy

M = [
[0, 8, 7],
[6, 5, 4],
[3, 2, 1]
]

T = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]

S = set()

dx = [-1,  1,  0,  0]
dy = [ 0,  0, -1,  1]

class Node:
def __init__(self, x, y, stat, step, last_node):
self.x, self.y = x, y
self.stat, self.step = stat, step
self.last_node = last_node

def calc_value(stat):
weight, sum = 1, 0
for i in range(3):
for j in range(3):
sum += stat[i][j]*weight
weight *= 10
return sum

def swap_stat(stat, x, y, nx, ny):
stat[x][y], stat[nx][ny] = stat[nx][ny], stat[x][y]

def bfs():
que = Queue()
start_node = Node(0, 0, M, 0, None)
que.put(start_node)

while not que.empty():
node = que.get()
x, y = node.x, node.y
stat, step = node.stat, node.step

for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx<0 or ny<0 or nx>2 or ny>2:
continue

swap_stat(stat, x, y, nx, ny)
if calc_value(stat) in S:
swap_stat(stat, x, y, nx, ny)
continue

if stat == T:
return step+1, node

new_stat = copy.deepcopy(stat)
swap_stat(stat, x, y, nx, ny)
que.put(Node(nx, ny, new_stat, step+1, node))

ans, node = bfs()
print(ans)

while node.last_node != None:
print(node.stat)
node = node.last_node

###优先队列BFS 依然是走迷宫, 但这次判断的是最短时间, 所以应该优先判断时间. 增加三秒(遇到2), 所以最优不是之前那条路. python code

from queue import PriorityQueue

M = [
[0, 0, 1, 0, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 2],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0]
]

V = [[False for j in range(5)] for i in range(5)]

dx = [-1,  1,  0,  0]
dy = [ 0,  0, -1,  1]

class Node:
def __init__(self, x, y, step, time):
self.x, self.y = x, y
self.step, self.time = step, time

def __lt__(self, other):
if self.time > other.time:
return True
return False

def bfs(start_x, start_y):
que = PriorityQueue()
que.put(Node(start_x, start_y, 0, 0))

while not que.empty():
node = que.get()
x, y = node.x, node.y
step, time = node.step, node.time

for i in range(4):
nx, ny = x+dx[i], y+dy[i]
if nx<0 or ny<0 or nx>4 or ny>4:
continue
if V[nx][ny] or M[nx][ny]==1:
continue
if nx==4 and ny==4:
return time+1

t = V[nx][ny]+1

que.put(Node(nx, ny, step+1, time+t))
V[nx][ny] = True

ans = bfs(0, 0)
print(ans)

###三维立方体迷宫BFS 只需多增加z轴方向, 在类中多增加一个成员z, 对应修改bfs函数. python code

dx = [0, 0, 1, 0, 0, -1]
dy = [0, 1, 0, 0, -1, 0]
dz = [1, 0, 0, -1, 0, 0]

class Node:
def __init__(self, x, y, z, step):
self.x, self.y, self.z, self.step = x, y, z, step

### jit-hakase

yvxiang
2016/11/16
2.3K
16

yvxiang
2016/12/06
3.5K
10
Linux 内核调度器--Linux BFS

BFS 是一款专门为 Linux 桌面环境所设计的内核调度器，它基于 Staircase Deadline 和 EEVDF 算法，支持 Linux 2.6.31 之后的内核。它提供了前所未有的流畅桌面性能，不仅得到了用户的认可，也...

2010/12/05
1K
0
Linux BFS 两年

xyxzfj
2011/08/17
3.4K
13
BFS-百度文件系统 v0.6.0 发布

BFS-百度文件系统 V0.6 发布了。BFS 是百度团队从百度搜索的业务特点出发，以高可用、高吞吐和低延迟为目标，开发的新一代分布式文件系统。 0.6.0 更新内容： 支持文件软链接 DK添加C语言接口...

bluebore
2017/03/10
2.9K
4

4分钟前
1
0

8分钟前
2
0
python的字典类型

1、新建字典 通过键值对 dict_1 = {'a':1,'b':2,'c':3} 通过dict()函数 list_1 = ['adam', 'bob', 'cathy', 'david', 'emma'] list_2 = [1,2,3,4,5] dict_2 = dict(zip(list_1,list_2)) 2、字......

davidwbnu
10分钟前
1
0
springcloud vue.js 前后分离 activiti工作流

java框架开发者
16分钟前
6
0
【jQuery基础学习】07 jQuery表单插件-Form

25分钟前
1
0