精华内容
下载资源
问答
  • [hadoop@iZ25s7cmfyrZ test]$ cat uda_city.py# ----------# ----------# Grid format:# 0 = Navigable space# 1 = Occupied spaceimport numpy as npgrid = [[0, 0, 1, 0, 0, 0],[0, 0, 1, 0, 0, 0],[0, 0, 0, ...

    [hadoop@iZ25s7cmfyrZ test]$ cat uda_city.py

    # ----------

    # ----------

    # Grid format:

    # 0 = Navigable space

    # 1 = Occupied space

    import numpy as np

    grid = [[0, 0, 1, 0, 0, 0],

    [0, 0, 1, 0, 0, 0],

    [0, 0, 0, 0, 1, 0],

    [0, 0, 1, 1, 1, 0],

    [0, 0, 0, 0, 1, 0]]

    init = [0, 0]

    goal = [len(grid)-1, len(grid[0])-1]

    cost = 1

    delta = [[-1, 0], # go up

    [ 0,-1], # go left

    [ 0, 1], # go right

    [ 1, 0]] # go down

    #delta_name = ['^', '<', 'v', '>']

    delta_name = ['^', '<', '>', 'v']

    def search(grid,init,goal,cost):

    # ----------------------------------------

    # insert code here

    # ----------------------------------------

    closed=[[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]

    action=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]

    x=init[0]

    y=init[1]

    g=0

    closed[x][y]=1

    open=[[g,x,y]]

    found=False

    resign=False

    grid[x][y]=2

    n=0

    while found is False and resign is False:

    #print open

    n=n+1

    #print "*"*20

    #print n

    #print np.array(grid)

    if len(open)==0:

    resign=True

    print "fail"

    else:

    ##remove node from list

    open.sort()

    open.reverse()

    next=open.pop()

    ## take

    x=next[1]

    y=next[2]

    g=next[0]

    #print g

    if x==goal[0] and y==goal[1]:

    found=True

    print next

    else:

    for i in range(len(delta)):

    x2=x+delta[i][0]

    y2=y+delta[i][1]

    #print i, delta[i], x2, y2

    #print x2, y2

    if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]):

    if grid[x2][y2]==0 and closed[x2][y2]==0:

    g2=g+cost

    open.append([g2, x2, y2])

    grid[x2][y2]=2

    action[x2][y2]=i

    closed[x2][y2]=1

    return action

    print np.array(grid)

    action=search(grid,init,goal,cost) ##注意action中存储的在上一时刻位置 t-1 经过何种动作到达本位置

    print np.array(action)

    policy=[[" " for row in range(len(grid[0]))] for col in range(len(grid))] ## policy 中存储的是在当前位置经过何种动作到达下一位置;即由t到t+1

    x=goal[0]

    y=goal[1]

    policy[x][y]="*"

    while x!=init[0] or y!=init[1]:

    x2=x-delta[action[x][y]][0]

    y2=y-delta[aciton[x][y]][1]

    policy[x2][y2]=delta_name[action[x][y]]

    x=x2

    y=y2

    print np.array(policy)

    展开全文
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
    [hadoop@iZ25s7cmfyrZ test]$ cat uda_city.py 
    # ----------
    
    # ----------
    
    # Grid format:
    #   0 = Navigable space
    #   1 = Occupied space
    import numpy as np
    
    grid = [[0, 0, 1, 0, 0, 0],
            [0, 0, 1, 0, 0, 0],
            [0, 0, 0, 0, 1, 0],
            [0, 0, 1, 1, 1, 0],
            [0, 0, 0, 0, 1, 0]]
    init = [0, 0]
    goal = [len(grid)-1, len(grid[0])-1]
    cost = 1
    
    delta = [[-1, 0], # go up
            [ 0,-1], # go left
            [ 0, 1], # go right
            [ 1, 0]] # go down
    
    #delta_name = ['^', '<', 'v', '>']
    delta_name = ['^', '<', '>', 'v']
    
    def search(grid,init,goal,cost):
        # ----------------------------------------
        # insert code here
        # ----------------------------------------
        closed=[[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        action=[[-1 for row in range(len(grid[0]))] for col in range(len(grid))]
    
        x=init[0]
        y=init[1]
        g=0
        closed[x][y]=1
        open=[[g,x,y]]
        found=False  
        resign=False
        grid[x][y]=2
        n=0
        
        while found is False and resign is False:
            #print open
            n=n+1
            #print "*"*20
            #print n
            #print np.array(grid)
            if len(open)==0:
                resign=True
                print "fail"
            else:
                ##remove node from list
                open.sort()
                open.reverse()
                next=open.pop()
                ## take 
                x=next[1]
                y=next[2]
                g=next[0]
                #print g
                if x==goal[0] and y==goal[1]:
                    found=True
                    print next
                else:
                    for i in range(len(delta)):
                        x2=x+delta[i][0]
                        y2=y+delta[i][1]
                        #print i, delta[i], x2, y2
                        #print x2, y2
                        if x2 >= 0 and x2 < len(grid) and y2 >= 0 and y2 < len(grid[0]):
                            if grid[x2][y2]==0 and closed[x2][y2]==0:
                                g2=g+cost
                                open.append([g2, x2, y2])
                                grid[x2][y2]=2
                                action[x2][y2]=i
                                closed[x2][y2]=1
        return action
    print np.array(grid)
    action=search(grid,init,goal,cost)   ##注意action中存储的在上一时刻位置 t-1 经过何种动作到达本位置
    print np.array(action)
    policy=[[" " for row in range(len(grid[0]))] for col in range(len(grid))]  ## policy 中存储的是在当前位置经过何种动作到达下一位置;即由t到t+1
    x=goal[0]
    y=goal[1]
    policy[x][y]="*"
    while x!=init[0] or y!=init[1]:
        x2=x-delta[action[x][y]][0]
        y2=y-delta[aciton[x][y]][1]
        policy[x2][y2]=delta_name[action[x][y]]
        x=x2
        y=y2
    print np.array(policy)

     

    转载于:https://my.oschina.net/lCQ3FC3/blog/859127

    展开全文
  • 1. 深度优先搜索介绍图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点...

    201802071052001.jpg

    1. 深度优先搜索介绍

    图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。

    它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到,则另选一个未被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    显然,深度优先搜索是一个递归的过程。

    2. 广度优先搜索介绍

    广度优先搜索算法(Breadth First Search),又称为"宽度优先搜索"或"横向优先搜索",简称BFS。

    它的思想是:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。

    换句话说,广度优先搜索遍历图的过程是以v为起点,由近至远,依次访问和v有路径相通且路径长度为1,2...的顶点。

    # -*- coding: utf-8 -*-

    """

    Created on Wed Sep 27 00:41:25 2017

    @author: my

    """

    from collections import OrderedDict

    class graph:

    nodes=OrderedDict({})#有序字典

    def toString(self):

    for key in self.nodes:

    print key+'邻接点为'+str(self.nodes[key].adj)

    def add(self,data,adj,tag):

    n=Node(data,adj)

    self.nodes[tag]=n

    for vTag in n.adj:

    if self.nodes.has_key(vTag) and tag not in self.nodes[vTag].adj:

    self.nodes[vTag].adj.append(tag)

    visited=[]

    def dfs(self,v):

    if v not in self.visited:

    self.visited.append(v)

    print v

    for adjTag in self.nodes[v].adj:

    self.dfs(adjTag)

    visited2=[]

    def bfs(self,v):

    queue=[]

    queue.insert(0,v)

    self.visited2.append(v)

    while(len(queue)!=0):

    top=queue[len(queue)-1]

    for temp in self.nodes[top].adj:

    if temp not in self.visited2:

    self.visited2.append(temp)

    queue.insert(0,temp)

    print top

    queue.pop()

    class Node:

    data=0

    adj=[]

    def __init__(self,data,adj):

    self.data=data

    self.adj=adj

    g=graph()

    g.add(0,['e','c'],'a')

    g.add(0,['a','g'],'b')

    g.add(0,['a','e'],'c')

    g.add(0,['a','f'],'d')

    g.add(0,['a','c','f'],'e')

    g.add(0,['d','g','e'],'f')

    g.add(0,['b','f'],'g')

    g.toString()

    print '深度优先遍历的结构为'

    g.dfs('c')

    print '广度优先遍历的结构为'

    g.bfs('c')

    展开全文
  • 广度优先搜索下面我们来来BFS算法策略:比如:我们要从双子峰---->金门大桥,最短路径如何?我们利用广度优先搜索来一步步求解,注意广度优先搜索在于的关键在于“广”,也就是说以双子峰为起点,我们要尽可能的多...

    广度优先搜索

    下面我们来来BFS算法策略:

    20180110232720463166.png

    比如:我们要从双子峰---->金门大桥,最短路径如何?

    我们利用广度优先搜索来一步步求解,注意广度优先搜索在于的关键在于“广”,也就是说以双子峰为起点,我们要尽可能的多比较与之相邻的周边路径,从其中选取一条最优路径。

    第一步:

    20180110232720465119.png

    我们沿着两个箭头方向路径探索到a点和b点后,发现并没有到达想要去的地方,于是我继续往下探索。

    20180110232720466096.png

    同样,我们发现还没有到达目的地,继续往下探索。

    20180110232720467072.png

    到达这一步后,我们发现其中有一条路径已经到达金门大桥,而其他两条路径仅仅到达c点。因此,我们寻找到的最短路径为:双子峰->a->c->金门大桥。

    所以,由上我们可以知道,广度优先搜索其实就是用来探索最短路径的一种方式。

    根据上面实例,我们想要寻找一条到某地的最短路径,需要一下两个步骤:

    (1)使用图来建立问题模型。

    (2)使用广度优先搜索解决问题。

    利用广度优先搜索,我们可以回答两个问题:

    1.从节点A出发,有前往B节点的路径吗?

    2.从节点A出发,前往B节点哪条路径最短?

    首先,我们来看看如何构建一张图。

    这里我们要使用一种能够表示映射关系的数据结构---散列表。至于什么是散列表,这里就不再赘述。

    例如:

    20180110232720469026.png

    graph = {}

    grapu[‘you‘] = [‘alice‘,‘bob‘,‘mar‘,‘rain‘,‘cat‘]

    这里的“you”被映射到一个数组。在‘you‘的这个数组里面,包含所有与你相邻的元素。

    有了以上方式,我们就可以构建一张更大图。

    算法实现策略:

    20180110232720470002.png

    首先,创建一个双端队列,将需要查找的压入队列中。

    from collections import deque

    def person_is_seller(name):

    return name[-1] == ‘m‘ #如果这个名字是以M结尾,则是

    graph = {}

    grapu[‘you‘] = [‘alice‘,‘bob‘,‘mar‘,‘rain‘,‘cat‘]

    search_queue = deque() #创建一个队列

    search_queue += graph[‘you‘] #将you压入队列

    while search_queue: #只要队列不为空

    person = search_queue.popleft() #取出左边第一个人

    if person_is_seller(person): #检查这个人是否为芒果商

    print person += ‘ is a mango seller! ‘

    return True

    else:

    search_queue += graph[person] #将这个人的朋友加入队列

    return False #没有芒果商

    但是,上面算法有一个明显的问题,如果你的朋友alice和bob都有这一个好友,那么在查找的过程中就会陷入循环状态。要解决这个问题,我们可以设置一个列表,来标记那些已经被查找过的人。因此,最终代码如下:

    def search(name):

    search_queue = deque() #创建一个队列

    search_queue += graph[name] #将需要查找的压入队列

    searcher = [] # 用于记录已经查找过的

    while search_queue: #只要队列不为空

    person = search_queue.popleft() #取出左边第一个人

    if not person in searched: #当这个人不在searched中才继续往下查找

    if person_is_seller(person): #检查这个人是否为芒果商

    print person += ‘ is a mango seller! ‘

    return True

    else:

    search_queue += graph[person] #将这个人的朋友加入队列

    searched.append(person)

    return False #没有芒果商

    性能分析:

    首先沿着每条边进行查找,如果边数为n,查找效率为O(V)

    再次,我们在每次查找过程中需要对已经搜索的列表进行二次判断,判断所需时间为P(n)

    因此,广度优先搜索总的查找效率为O(V+n)

    原文:http://www.cnblogs.com/vipchenwei/p/6882593.html

    展开全文
  • 图的概念图表示的是多点之间的连接关系,由节点和边组成。...在python中,我们使用字典来表示图,我们将图相邻节点之间的连接转换为字典键值之间的映射关系。比如上图中的1的相邻节点为2和3,即可表示如下:graph={...
  • 总结 以上所述是小编给大家介绍的python 递归深度优先搜索与广度优先搜索算法模拟实现 ,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持! 本文...
  • 图论,特别是图的ADT(抽象数据类型)在数学和计算机科学中使用是非常广泛的。图由顶点(节点)和边(可能是有方向的/加权重的)...在这篇文章中,我将会探索两个简单的算法,深度优先查找和广度优先查找,要达到如下突出...
  • 二叉树的两种遍历是数据结构的经典考察题目, 广度遍历考察队列结构, 深度遍历考察递归二叉树深度优先先序遍历(父, 左子, 右子) 0, 1, 3, 7, 8, 4, 9, 2, 5, 6中序遍历(左子, 父, 右子) 7, 3, 8, 1, 9, 4, 0, 5, 2, 6...
  • 在介绍 python 实现图的深度优先和广度优先搜索前,我们先来了解下什么是“图”。1 一些定义顶点顶点(也称为“节点”)是图的基本部分。它可以有一个名称,我们将称为“键”。边边(也称为“弧”)是图的另一个基本...
  • 一、算法原理 ...宽度优先搜索算法(Breadth First Search,BSF),思想是: 从图中某顶点v出发,首先访问定点v 在访问了v之后依次访问v的各个未曾访问过的邻接点; 然后分别从这些邻接点出发依次访...
  • 宽度优先搜索算法:python实现本文博客链接:http://blog.csdn.net/jdh99,作者:jdh,转载请注明. 环境:主机:WIN10python版本:3.5开发环境:pyCharm说明:本程序是udp客户端模块。绑定固定端口进行收发。udp接收是一个...
  • 宽度优先搜索宽度优先搜索算法(Breadth First Search,BSF),思想是:·1.从图中某顶点v出发,首先访问定点v·2.在访问了v之后依次访问v的各个未曾访问过的邻接点;·3.然后分别从这些邻接点出发依次访问它们的...
  • python宽度优先解决八数码问题

    千次阅读 2020-10-15 07:33:19
    tb: open.append(i) end = datetime.now() print('--' * 20) print('--' * 20) print('--' * 20) print('搜索路径如下:') for i in close[:-1]: print(np.array(i.state)) print('↓') print(np.array(close[-1]....
  • ​leetcode.com第一, Python 代码, 用非递归遍历,题目已经假定了root 非空, 用队列(Python 用list 模拟队列),先添加root到队列中,出队列,再判右子树不为空,就添加右子树,再判断左子树是不是为空,非空...
  • 这位大神应该是擅长java的,所以python的代码写得不是很简洁,但是思路真的很好。 BFS的特点就是一层层地遍历,方便计算层数。DFS是先一条分支走到头,再下一条分支。 首先,循环一遍表格,找出所有的陆地,这就作为...
  • 目录 岛屿数量 (LeetCode 200) 词语阶梯(LeetCode 127) 词语阶梯2 (LeetCode 126) 01矩阵 (LeetCode 542) 太平洋与大西洋的水流 (LeetCode 417) 收集雨水2 (LeetCode 407) ...1. 岛屿数量 (LeetCode 200 Number of ...
  • python解决九宫格问题展示部分数据的设计:宽度优先搜索代码:深度优先搜索代码 最近课内在学习《人工智能引论》、《数据结构》。 前者讲了Open/closed表、宽度、深度优先搜索策略,后者讲到了队列,两门课都期望...
  • # -*- coding: UTF-8 -*- from __future__ import print_function deep = 3 #二叉树*******************************start L = [] ...class TreeNode(object): def __init__(self,data,left,right):
  • 宽度优先搜索BFS 工作方式: 从根节点开始,由里向外,逐层遍历所有节点——它每次总是扩展深度最浅的节点。 BFS方法,从根节点1开始,下图遍历顺序是:1,2,3,4,5,6 优先访问深度最浅的节点,故,老节点总是...
  • graph = {} def connect(self,word1,word2): count = 0 for i in range(len(word1)): if word1[i] != word2[i]: count +=1 return count ==1 def construct_graph(self,beginword,wordlist,graph): ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,084
精华内容 1,233
关键字:

python宽度优先搜索

python 订阅