文档章节

BFS

jit-hakase
 jit-hakase
发布于 2017/08/30 22:25
字数 1089
阅读 10
收藏 0

#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
        
        S.add(calc_value(stat))
        
        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)

可以在生成状态前先计算value, 不过提升的速度不多. 再增加一个类属性last_node来链接上一个状态, 显示倒着的变化过程. 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, 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
        
        S.add(calc_value(stat))
        
        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

© 著作权归作者所有

上一篇: Java OOP
下一篇: DFS算法
jit-hakase
粉丝 3
博文 26
码字总数 30408
作品 0
南京
程序员
私信 提问
百度开源高性能高可用分布式文件系统BFS

简介 百度的核心业务和数据库系统依赖分布式文件系统作为底层存储,文件系统的可用性和性能对上层搜索业务的稳定性与效果有着至关重要的影响。现有的分布式文件系统(如HDFS等)是为离线批处...

yvxiang
2016/11/16
2.3K
16
五分钟快速实现leveldb中数据的高可靠

众所周知,leveldb是Google的Sanjay Ghemawat和Jeff Dean两位大神编写的一个高性能KV引擎,使用起来非常方便。然而,开源版本的leveldb将所有数据存放在了本地磁盘,如果本地磁盘发生故障,可...

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 两年

本月是Linux BFS发布两周年的纪念日。BFS(the Brain Fuck Scheduler)——Linux内核的中心调度器。尽管BFS还没有进入Linux内核的主线当中,该调度器仍被Con Kolivas积极地维护,为新的内核发...

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

没有更多内容

加载失败,请刷新页面

加载更多

重新开始学Java——反射

概念 reflection:自省 反射:镜子可以反射阳光一个java类 或 对象 通过照"镜子"来认知自己 Java语言中是怎么实现照镜子? java.lang.reflect 包 提供了"照镜子"API(应用程序接口) 如果要...

大家都是低调来的
4分钟前
1
0
爬取720万条城市历史天气数据

内容爬虫完毕,校验完毕,缺失信息暂未统计。总数据720万,地区3200个,年份从2011-2019,大小950Mb,原始数据已丢失,需要的朋友可以自己运行脚本挂一晚上。中间遇到了很多坑,有机会我再写...

八音弦
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工作流

本商品为 :springcloud + Springboot 微服务\分布式 工作流 前后分离 + 跨域 版本 (权限控制到菜单和按钮) 后台框架 :springcloud Greenwich.SR1 + springboot 2.1.4 + activiti6.0.0 + ...

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

本文转载于:专业的前端网站➦【jQuery基础学习】07 jQuery表单插件-Form 作用:jQuery Form插件的作用是为了让我们可以很方便地用ajax的方式提交表单,从而使我们提交表单的时候页面不用进行...

前端老手
25分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部