Breath-First Search/Depth-First

我是从迷宫机器人入手尝试了深度优先和广度优先,一下是题目及我的认识和实现。

题目如下:

这是一个5*9矩阵地图

* 其中 1 是机器人的起点 0 是可以通行的地板 2是墙 3是目的地 求最近直达路线

[3, 2, 2, 2, 2, 0, 0, 0, 1],

[0, 0, 0, 0 ,0, 0, 2, 0, 0],

[2, 0, 0, 2, 2, 2, 0, 0, 2],

[2, 2, 0, 0, 2, 0, 0, 2, 2],

[2, 2, 2, 0, 0, 0, 2, 2, 2]

广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。 

深度优先算法(DFS)：

（1）访问初始顶点v并标记顶点v已访问。

（2）查找顶点v的第一个邻接顶点w。

（3）若顶点v的邻接顶点w存在，则继续执行；否则回溯到v，再找v的另外一个未访问过的邻接点。

（4）若顶点w尚未被访问，则访问顶点w并标记顶点w为已访问。

（5）继续查找顶点w的下一个邻接顶点wi，如果v取值wi转到步骤（3）。直到连通图中所有顶点全部访问过为止。

深度优先其实是一种递归，他可能一条路走到墙之后发现不通又走回来重走另外一条再走到墙或走到终点。

以下是我的Py实现的核心代码

# 广度

def bfs_treasure(env_data,start_loc,end_loc):

    # 这个队列用于存储节点

    queue = []

    # 起始节点加入队列

    queue.append(start_loc)

    # 颜色set存储访问过的节点

    seen = set()

    # 起始节点变成灰色

    seen.add(start_loc)

    while (len(queue)>0):

        vertex = queue.pop(0)

        # 这里用了之前定义的验证函数把周围的节点嫩出来

        nodes = [ get_neighbors(vertex,i) for i in valid_actions(env_data,vertex) ]

        # 遍历一下

        for w in nodes:

            # 是还没走过的节点

            if w not in seen:

                # 加入队列

                queue.append(w)

                # 上色~

                seen.add(w)

        print(vertex)

# 深度       

def dfs_treasure(env_data,start_loc,end_loc):

    # 存储已访问过的节点

    visited = set()

    # 路线

    order = []

    # 递归方式

    def dfs(node):

            # 周围的节点

            node_neighbors = [ get_neighbors(node,i) for i in valid_actions(env_data,node)]

            visited.add(node)

            order.append(node)

            if node == end_loc:

                return

            else:   

                for n in node_neighbors:

                    if not n in visited:

                        dfs(n)

    if start_loc:

            dfs(start_loc)

    return order

说明一下区别和实际移动路线：

所以bfs 是辐射状扩散的，而dfs是一条路走到黑的，这个地图中dfs撞南墙后又回来走另外一条路子了，浪子回头金不换。

（

这个地图 dfs 效率更高

所以，当路径节点很深时，选择dfs。