广度优先搜索(Breadth-First-Search)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 2.2k | 阅读时长 ≈ 9
Breadth-First-Search

Breadth-First-Search

原理介绍

   Breadth-First-Search(BFS):深度优先搜索，属于图算法的一种，是一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。在树搜索算法中，从上到下为纵，从左向右为横，纵向搜索为深度优先，而横向搜索是广度优先。简言之就是先访问图的顶点，然后优先访问其邻接点，然后再依次进行被访问点的邻接点，一层一层访问，直至访问完所有点，遍历结束，通常根据队列的先进先出性质将各结点遍历。

bfs

算法条件

解空间

  解的组织形式可以规范为一个n元组${x_1,x_2,\ldots,x_n}$，并且对解有取值范围的限定，一般为有穷个，解的个数代表一个结点的分支个数。解空间越小，搜索效率越高，解空间大犹如大海捞针，搜索效率很低。

剪枝函数

  剪枝函数又称为隐约束，对能否得到问题的可行解的约束称为约束函数，对能否得到问题的最优解的约束称为限界函数。有了剪枝函数，我们就可以剪掉得不到可行解或最优解的分支，避免了无效搜索，提高搜索的效率。因此剪枝函数的设计是十分重要的。

算法步骤

  (1)分析题意，了解题目要求
  (2)根据问题分析解空间的形式
  (3)根据解空间设计合适的剪枝函数

经典例题(0-1背包)

问题描述

  假设山洞里有n个宝物，每种宝物有一定重量w和相应的价值v，背包的装载能力有限，只能运走重量为m的宝物，宝物不可以分割，如何使背包运走物品的价值最大？
  第一行先输入宝物的数量n，和背包的承载重量m，然后每一行输出一个宝物对应的重量w和价值v(用空格分开)

1
2
3
4
5
6
5 10 # 宝物数n和背包能装载的重量m
2 6 #每个宝物的重量w和价值v
5 3
4 5
2 4
3 6

算法分析

  0-1背包问题和普通背包问题不同的是其解空间为{0，1}，即每一个物品都有两种状态，装入或者不装入，因此满足解空间的条件。
  分析剪枝函数，如果剩余的价值加上当前的价值都没有已经搜索到的最大价值高，则没有必要继续搜索。

python代码实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys

def bfs(treasure_queue):
    global max_value, max_plan
    while treasure_queue:
        n, out_node = treasure_queue[0][0], treasure_queue.pop(0)
        if n >= count:
            max_value, max_plan = [out_node[2], out_node[3][:]] if out_node[2] > max_value else [max_value, max_plan[:]]
            continue
        if out_node[1] - treasure[n][1] >= 0:
            treasure_queue.append([n + 1, out_node[1] - treasure[n][1], out_node[2] + treasure[n][2], out_node[3][:n] + [True] + out_node[3][n + 1:]])
        if out_node[2] + leave_value[n] > max_value:
            treasure_queue.append([n + 1, out_node[1], out_node[2], out_node[3][:]])

print('请输入宝物数量和驴子承载重量:')
for line in sys.stdin:
    count, weight = line.strip().split()
    count, weight, treasure, max_plan, max_value, leave_value, res = int(count), float(weight), [], [False] * int(count), 0, [0], []
    print('请输入每个宝物的重量和价值')
    for i in range(count):
        tmp = [float(x) for x in sys.stdin.readline().strip().split()]
        treasure.append([i + 1] + tmp + [tmp[1] / tmp[0]])
    treasure.sort(key=lambda x: (-x[3]))
    for i in reversed(range(1, count)):
        leave_value = [leave_value[0] + treasure[i][2]] + leave_value
    bfs([[0, weight, 0, [False] * count]])
    print('最优的方案为:\n' + ''.join(['' + ('装入第' + str(j) + '个宝物\n') * (j != 0) for j in sorted([treasure[i][0] * max_plan[i] for i in range(count)])]) + '装入宝物的最大价值为:', max_value)

代码运行结果

2

经典例题(旅行商问题)

问题描述

  现有n个景点，从第一个景点出发，两个景点之间有数字代表可以直接到达，问如何找到一个路径能够不重复的走遍所有景点回到出发点，而且所经过的路径长度是最短的。
  第一行输入景点的个数，第二行输入两地之间可以直接到达的数量，然后每行输入两地和之间的距离

1
2
3
4
5
6
7
8
9
10
11
5 # 景点个数
9 # 景点之间的连接数
1 2 3 # 景点1和景点2之间的距离为3
1 4 8
1 5 9
2 3 3
2 4 10
2 5 5
3 4 4
3 5 3
4 5 20

算法分析

  旅行商问题(TSP)是一个典型的问题，此问题的解空间为n，每一个景点都可以到与之相连的所有点，因此当景点数很多时，最优解的搜索是十分缓慢的。
  分析剪枝函数，剪枝函数容易看出，由于不是任何两个景点都是相连的，而且走过的景点不能再走一次，所以这也大大减少了解空间的个数。

python代码实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys

def bfs(tour_queue):
    global  min_dist, min_route
    while tour_queue:
        n, out_node = tour_queue[0][0], tour_queue.pop(0)
        if n >= scenic_spot_num:
            min_dist, min_route = [out_node[1] + connection[out_node[2][-1]][0], out_node[2][:] + [0]] if out_node[1] + connection[out_node[2][-1]][0] < min_dist else [min_dist, min_route[:]]
        for i in range(scenic_spot_num):
            if i not in out_node[2] and connection[out_node[2][-1]][i] != 0 and out_node[1] + connection[out_node[2][-1]][i] + connection[i][0] < min_dist:
                tour_queue.append([n + 1, out_node[1] + connection[out_node[2][-1]][i], out_node[2] + [i]])

print('请输入景点数:')
for line in sys.stdin:
    scenic_spot_num, min_dist, min_route = int(line.strip()), 65535, []
    print('请输入连通的景点数:')
    connection_num, connection = int(sys.stdin.readline().strip()), [[0 for i in range(scenic_spot_num)] for j in range(scenic_spot_num)]
    print('请依次输入两个景点之间的距离:')
    for i in range(connection_num):
        begin, end, weight = [int(i) for i in sys.stdin.readline().strip().split()]
        connection[begin - 1][end - 1], connection[end - 1][begin - 1] = weight, weight
    bfs([[1, 0, [0]]])
    print('最短的路径为:' + '->'.join([str(x + 1) for x in min_route]) + '\n最短的路径长度为:', min_dist)

代码运行结果

3

经典例题(迷宫问题)

问题描述

  在一个m×n的地图上，有许多障碍物，给定起始点坐标和目的地坐标，问从起始点开始通过上下左右四个方向移动如何找到一条最短路径能够到达目的地？
  第一行输入地图的大小m和n，然后每一行输入障碍物的坐标，输入0，0时结束，接着输入起始点坐标和目的地坐标。

1
2
3
4
5
6
7
8
9
5 6 # 地图的大小m,n
1 6 # 障碍物的坐标
2 3 
3 4
3 5
5 1
0 0 #输入0,0结束
2 1 #起始点坐标
4 6 #目的地坐标

5

算法分析

  迷宫问题是一个典型的搜索问题，每个点都有四个移动方向，因此每一个结点都有四个子节点，可以通过广度优先算法来求解此问题。
  分析剪枝函数，此题比较特殊，特别适合于用广度优先，广度优先是一层一层遍历，后面访问的结点的层数一定不小于前面结点的层数。判断新加入的坐标是否为目的地坐标，如果是则为最优解，不需要再搜索其他路径。

python代码实战

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import sys

def bfs(circuit_board_queue):
    global min_spend
    while circuit_board_queue:
        out_node_value, out_node_site = circuit_board_queue[0][0], circuit_board_queue.pop(0)[1]
        if [end_x - 1, end_y - 1] == out_node_site[-1]:
            return out_node_value, [x[:] for x in out_node_site]
        for x, y in direction:
            if 0 <= out_node_site[-1][0] + x < m_size and 0 <= out_node_site[-1][1] + y < n_size and out_node_value + 1 < min_spend[out_node_site[-1][0] + x][out_node_site[-1][1] + y]:
                min_spend[out_node_site[-1][0] + x][out_node_site[-1][1] + y] = out_node_value + 1
                circuit_board_queue.append([out_node_value + 1, out_node_site + [[out_node_site[-1][0] + x, out_node_site[-1][1] + y]]])

print('请输入地图大小:')
for line in sys.stdin:
    m_size, n_size = [int(x) for x in line.strip().split()]
    circuit_board, min_spend, direction = [[1 for i in range(n_size)] for j in range(m_size)], [[65535 for i in range(n_size)] for j in range(m_size)], [[1, 0], [0, 1], [-1, 0], [0, -1]]
    while True:
        print('请输入障碍物坐标:')
        x, y = [int(x) for x in sys.stdin.readline().strip().split()]
        if x == 0 and y == 0:
            break
        circuit_board[x - 1][y - 1] = 0
    print('请输入起点坐标')
    begin_x, begin_y = [int(x) for x in sys.stdin.readline().strip().split()]
    min_spend[begin_x - 1][begin_y - 1] = 0
    print('请输入终点坐标')
    end_x, end_y = [int(x) for x in sys.stdin.readline().strip().split()]
    min_dist, min_route = bfs([[0, [[begin_x - 1, begin_y - 1]]]])
    print('这条最短路径的长度为:', min_dist, '\n最佳的路径为:' + '->'.join([str(tuple([y + 1 for y in x])) for x in min_route]))

代码运行结果

4

算法总结

  广度优先搜索是一个基本搜索方法，和深度优先有异曲同工之妙，对于许多问题都可以同时用这两种方法解决。和深度优先相同，都是指数级的时间复杂度，但是对于有些问题不得不使用广度优先进行遍历，因此寻找合适的约束条件可以大大减少时间的开销。

-------------本文结束感谢您的阅读-------------
0%