[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. 算法原理

			
首先，我们给定一个二叉树图如下：

			
 

			
 

			
1). 宽度优先搜索：

			
宽度优先搜索算法(Breadth First Search，BSF)，思想是：

			
· 1.从图中某顶点v出发，首先访问定点v

			
· 2.在访问了v之后依次访问v的各个未曾访问过的邻接点；

			
· 3.然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问;

			
· 4.直至图中所有已被访问的顶点的邻接点都被访问到;

			
· 5.如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

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

			如上图的BFS访问顺序为：

			
A->B->C->D->E->F

			
 

			
 

			
2). 深度优先搜索：

			
图的深度优先搜索(Depth First Search, DFS)，和树的前序遍历非常类似。

			
它的思想：

			
1.从顶点v出发，首先访问该顶点;

			
2.然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图;

			
3.直至图中所有和v有路径相通的顶点都被访问到。

			
4.若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止

			
如上图的BFS访问顺序为：

			
A->B->D->E->C->F

			
 

			
2. 关键代码的编写

			
1）首先定义一个类，创建一个二叉树图

			
 

			
# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
    def __init__(self, *args, **kwargs):
        self.order = []  # visited order
        self.neighbor = {}

    def add_node(self, node):
        key, val = node
        if not isinstance(val, list):
            print('节点输入时应该为一个线性表')    # 避免不正确的输入
        self.neighbor[key] = val

 

			
2）宽度优先算法的实现

			
 

			
# 宽度优先算法的实现
def BFS(self, root):
    #首先判断根节点是否为空节点
    if root != None:
        search_queue = deque()
        search_queue.append(root)
        visited = []
    else:
        print('root is None')
        return -1

    while search_queue:
        person = search_queue.popleft()
        self.order.append(person)

        if (not person in visited) and (person in self.neighbor.keys()):
            search_queue += self.neighbor[person]
            visited.append(person)

 

			
 

			
 

			
3）深度优先算法的实现

			
 

			
# 深度优先算法的实现
def DFS(self, root):
    # 首先判断根节点是否为空节点
    if root != None:
        search_queue = deque()
        search_queue.append(root)

        visited = []
    else:
        print('root is None')
        return -1

    while search_queue:
        person = search_queue.popleft()
        self.order.append(person)

        if (not person in visited) and (person in self.neighbor.keys()):
            tmp = self.neighbor[person]
            tmp.reverse()

            for index in tmp:
                search_queue.appendleft(index)

            visited.append(person)

 

			
 

			
3.运行结果的展示

			
 

			
 

			
 

			
 

			
 
			
		

			
实验过程中遇到的问题如何解决的？
			
			

			
 
			
		

			
1. 遇到的问题

			
   在本次实验中最大的问题就是对于两个算法的理解和实现吧，比如是迭代还是递归，还是回溯，都是我们值得去思考和理解的。

			
 

			
 

			
2. 如何解决

			
   其实，把严蔚敏的数据结构里面的原理理解清楚了，这两个算法其实不难的，如果这都理解不清楚，就说明数据结构学得很有问题，立即推放弃学计算机。

			
 

			
 
			
		

			
本次实验的体会（结论）
			
			

			
 
			
		

			
本次实验在很大层度上让我进一步了解了这两种算法的区别和原理，不仅专业课学习上有一定帮助，同时也为考研复习提供了一个很好的复习。
			
		

			
 
			
		

			
 

			
 

			
日期：2018-06-12

			
            
			
		
附录：

完整的代码：

# -*- coding: utf-8 -*-
# /usr/bin/python
# 作者：郭畅
# 实验日期：20180612
# Python版本：3.6.4
# 主题：基于深度优先和宽度优先的搜索算法的简单实现
# 参考书籍：数据结构C语言版（清华大学出版社严蔚敏版）

from collections import deque    # 线性表的模块

# 首先定义一个创建图的类，使用邻接矩阵
class Graph(object):
    def __init__(self, *args, **kwargs):
        self.order = []  # visited order
        self.neighbor = {}

    def add_node(self, node):
        key, val = node
        if not isinstance(val, list):
            print('节点输入时应该为一个线性表')    # 避免不正确的输入
        self.neighbor[key] = val

    # 宽度优先算法的实现
    def BFS(self, root):
        #首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)
            visited = []
        else:
            print('root is None')
            return -1

        while search_queue:
            person = search_queue.popleft()
            self.order.append(person)

            if (not person in visited) and (person in self.neighbor.keys()):
                search_queue += self.neighbor[person]
                visited.append(person)

    # 深度优先算法的实现
    def DFS(self, root):
        # 首先判断根节点是否为空节点
        if root != None:
            search_queue = deque()
            search_queue.append(root)

            visited = []
        else:
            print('root is None')
            return -1

        while search_queue:
            person = search_queue.popleft()
            self.order.append(person)

            if (not person in visited) and (person in self.neighbor.keys()):
                tmp = self.neighbor[person]
                tmp.reverse()

                for index in tmp:
                    search_queue.appendleft(index)

                visited.append(person)

    def clear(self):
        self.order = []

    def node_print(self):
        for index in self.order:
            print(index, end='  ')


if __name__ == '__main__':
    # 创建一个二叉树图
    g = Graph()
    g.add_node(('A', ['B', 'C']))
    g.add_node(('B', ['D', 'E']))
    g.add_node(('C', ['F']))

    # 进行宽度优先搜索
    g.BFS('A')
    print('宽度优先搜索:')
    print('  ', end='  ')
    g.node_print()
    g.clear()

    # 进行深度优先搜索
    print('\n\n深度优先搜索:')
    print('  ', end='  ')
    g.DFS('A')
    g.node_print()
    print()

 

人工智能学习：python实现宽度优先搜索算法

本文博客链接:http://blog.csdn.net/jdh99,作者:jdh,转载请注明.
 
环境：
主机:WIN10
python版本:3.5
开发环境:pyCharm

说明：
学习《人工智能 一种现代方法》编写宽度优先算法。
书中算法源码：



算法流程分析：
数据结构：
frontier：边缘。存储未扩展的节点
 
explored：探索集。存储的是状态（注意，这个之前的算法有区别）
流程：
如果边缘为空，则返回失败。操作：EMPTY?(frontier)
 
否则从边缘中选择一个叶子节点。操作：POP(frontier)
 
将叶子节点的状态放在探索集
 
遍历叶子节点的所有动作
每个动作产生子节点
  
如果子节点的状态不在探索集或者边缘，则目标测试：通过返回
  
失败则放入边缘。操作：INSERT(child, frontier)
 
 
 
注意：算法中只有在遍历叶子节点所有动作，即宽度搜索之前，才将叶子节点的状态放入到探索集。在遍历过程中，如果子节点没有通过目标测试，并没有将子节点的状态放入探索集，而是将子节点放在边缘中，准备下一轮基于本子节点的宽度遍历。
 
 
算法性能分析：
完备的
 
不是最优的
 
时间复杂度：
假设每个状态都有b个后继，解的深度为d，则节点总数：
b + b^2 + b^3 + … + b^d = O(b^d)
以上算法是在扩展节点时而不是生成时进行目标检测，所以时间复杂度应该是O(b^(d+1))
空间复杂度：
每个已扩展的节点都保存到探索集，探索集的节点数：O(b(d - 1))，边缘节点中：O(b^d)。所以控件复杂度为O(b^d)，由边缘集所决定。
 



城市地图：



源码：

import pandas as pd
from pandas import Series, DataFrame

# 城市信息：city1 city2 path_cost
_city_info = None

# 按照路径消耗进行排序的FIFO,低路径消耗在前面
_frontier_priority = []


# 节点数据结构
class Node:
    def __init__(self, state, parent, action, path_cost):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost


def main():
    global _city_info
    import_city_info()

    while True:
        src_city = input('input src city\n')
        dst_city = input('input dst city\n')
        result = breadth_first_search(src_city, dst_city)
        if not result:
            print('from city: %s to city %s search failure' % (src_city, dst_city))
        else:
            print('from city: %s to city %s search success' % (src_city, dst_city))
            path = []
            while True:
                path.append(result.state)
                if result.parent is None:
                    break
                result = result.parent
            size = len(path)
            for i in range(size):
                if i < size - 1:
                    print('%s->' % path.pop(), end='')
                else:
                    print(path.pop())


def import_city_info():
    global _city_info
    data = [{'city1': 'Oradea', 'city2': 'Zerind', 'path_cost': 71},
            {'city1': 'Oradea', 'city2': 'Sibiu', 'path_cost': 151},
            {'city1': 'Zerind', 'city2': 'Arad', 'path_cost': 75},
            {'city1': 'Arad', 'city2': 'Sibiu', 'path_cost': 140},
            {'city1': 'Arad', 'city2': 'Timisoara', 'path_cost': 118},
            {'city1': 'Timisoara', 'city2': 'Lugoj', 'path_cost': 111},
            {'city1': 'Lugoj', 'city2': 'Mehadia', 'path_cost': 70},
            {'city1': 'Mehadia', 'city2': 'Drobeta', 'path_cost': 75},
            {'city1': 'Drobeta', 'city2': 'Craiova', 'path_cost': 120},
            {'city1': 'Sibiu', 'city2': 'Fagaras', 'path_cost': 99},
            {'city1': 'Sibiu', 'city2': 'Rimnicu Vilcea', 'path_cost': 80},
            {'city1': 'Rimnicu Vilcea', 'city2': 'Craiova', 'path_cost': 146},
            {'city1': 'Rimnicu Vilcea', 'city2': 'Pitesti', 'path_cost': 97},
            {'city1': 'Craiova', 'city2': 'Pitesti', 'path_cost': 138},
            {'city1': 'Fagaras', 'city2': 'Bucharest', 'path_cost': 211},
            {'city1': 'Pitesti', 'city2': 'Bucharest', 'path_cost': 101},
            {'city1': 'Bucharest', 'city2': 'Giurgiu', 'path_cost': 90},
            {'city1': 'Bucharest', 'city2': 'Urziceni', 'path_cost': 85},
            {'city1': 'Urziceni', 'city2': 'Vaslui', 'path_cost': 142},
            {'city1': 'Urziceni', 'city2': 'Hirsova', 'path_cost': 98},
            {'city1': 'Neamt', 'city2': 'Iasi', 'path_cost': 87},
            {'city1': 'Iasi', 'city2': 'Vaslui', 'path_cost': 92},
            {'city1': 'Hirsova', 'city2': 'Eforie', 'path_cost': 86}]

    _city_info = DataFrame(data, columns=['city1', 'city2', 'path_cost'])
    # print(_city_info)


def breadth_first_search(src_state, dst_state):
    global _city_info

    node = Node(src_state, None, None, 0)
    # 目标测试
    if node.state == dst_state:
        return node
    frontier = [node]
    explored = []

    while True:
        if len(frontier) == 0:
            return False
        node = frontier.pop(0)
        explored.append(node.state)
        if node.parent is not None:
            print('deal node:state:%s\tparent state:%s\tpath cost:%d' % (node.state, node.parent.state, node.path_cost))
        else:
            print('deal node:state:%s\tparent state:%s\tpath cost:%d' % (node.state, None, node.path_cost))

        # 遍历子节点
        for i in range(len(_city_info)):
            dst_city = ''
            if _city_info['city1'][i] == node.state:
                dst_city = _city_info['city2'][i]
            elif _city_info['city2'][i] == node.state:
                dst_city = _city_info['city1'][i]
            if dst_city == '':
                continue
            child = Node(dst_city, node, 'go', node.path_cost + _city_info['path_cost'][i])
            print('\tchild node:state:%s path cost:%d' % (child.state, child.path_cost))
            if child.state not in explored and not is_node_in_frontier(frontier, child):
                # 目标测试
                if child.state == dst_state:
                    print('\t\t this child is goal!')
                    return child
                frontier.append(child)
                print('\t\t add child to child')


def is_node_in_frontier(frontier, node):
    for x in frontier:
        if node.state == x.state:
            return True
    return False


if __name__ == '__main__':
    main()





利用算法求解：
input src city
Zerind
input dst city
Urziceni
deal node:state:Zerind parent state:None path cost:0
 child node:state:Oradea path cost:71
   add child to child
 child node:state:Arad path cost:75
   add child to child
deal node:state:Oradea parent state:Zerind path cost:71
 child node:state:Zerind path cost:142
 child node:state:Sibiu path cost:222
   add child to child
deal node:state:Arad parent state:Zerind path cost:75
 child node:state:Zerind path cost:150
 child node:state:Sibiu path cost:215
 child node:state:Timisoara path cost:193
   add child to child
deal node:state:Sibiu parent state:Oradea path cost:222
 child node:state:Oradea path cost:373
 child node:state:Arad path cost:362
 child node:state:Fagaras path cost:321
   add child to child
 child node:state:Rimnicu Vilcea path cost:302
   add child to child
deal node:state:Timisoara parent state:Arad path cost:193
 child node:state:Arad path cost:311
 child node:state:Lugoj path cost:304
   add child to child
deal node:state:Fagaras parent state:Sibiu path cost:321
 child node:state:Sibiu path cost:420
 child node:state:Bucharest path cost:532
   add child to child
deal node:state:Rimnicu Vilcea parent state:Sibiu path cost:302
 child node:state:Sibiu path cost:382
 child node:state:Craiova path cost:448
   add child to child
 child node:state:Pitesti path cost:399
   add child to child
deal node:state:Lugoj parent state:Timisoara path cost:304
 child node:state:Timisoara path cost:415
 child node:state:Mehadia path cost:374
   add child to child
deal node:state:Bucharest parent state:Fagaras path cost:532
 child node:state:Fagaras path cost:743
 child node:state:Pitesti path cost:633
 child node:state:Giurgiu path cost:622
   add child to child
 child node:state:Urziceni path cost:617
   this child is goal!
from city: Zerind to city Urziceni search success
Zerind->Oradea->Sibiu->Fagaras->Bucharest->Urziceni

从Zerind到Urziceni的最优路径应该是Zerind->Arad->Sibiu->Rimnicu Vilcea->Pitesti->Bucharest->Urziceni，所以本算法不是最优算法，只是一个解。


参考书目：
1.《人工智能 一种现代方法》