CS 188 (3) Breadth First Search BFS(广度优先搜索算法)

    本文要实现 Breadth First Search BFS(广度优先搜索算法) ,首先搜索搜索树中最浅的节点,广度搜索算法搜索到达目标。

    Queue是一个先进先出（FIFO）队列策略的容器，Queue是一个类，使用列表List初始化,入站在列表List中头部插入一个元素，出栈使用pop实现，将仍在队列中的最早进入队列的项目出列，这个操作从队列中删除该项。从列表的长度为0判断栈是否为空。   

class Queue:"A container with a first-in-first-out (FIFO) queuing policy."def __init__(self):self.list = []def push(self,item):"Enqueue the 'item' into the queue"self.list.insert(0,item)def pop(self):"""Dequeue the earliest enqueued item still in the queue. Thisoperation removes the item from the queue."""return self.list.pop()def isEmpty(self):"Returns true if the queue is empty"return len(self.list) == 0

广度优先算法BFS代码：

# search.py
# ---------
# Licensing Information:  You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# 
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).def breadthFirstSearch(problem):"""Search the shallowest nodes in the search tree first.""""*** YOUR CODE HERE ***"#util.raiseNotDefined()path =Path([problem.getStartState()],[],0)if problem.isGoalState(problem.getStartState()):return path.directions#新建一个队列,起始状态入队列queue =util.Queue()    queue.push(path)#取得初始状态列表visited =[problem.getStartState()]while not queue.isEmpty():#如队列不为空，取最先进入队列的元素（List的最后一个元素），获取当前路径currentPath = queue.pop()currentLocation = currentPath.locations[-1]#如果当前位置已经是终点的位置，则返回当前路径的方向列表，用于移动pac man。if problem.isGoalState(currentLocation):return currentPath.directionselse:#在搜索问题中取得当前位置后继的下一个状态.getSuccessors中for循环遍历北、南、东、西四个方向，#directionToVector取得方向到坐标偏移向量的转换值，在当前坐标上加上位移的坐标偏移量值，#如果下一步坐标移动的点不是围墙，则在后续状态列表中加入三元组( nextState, action, cost)nextSteps = problem.getSuccessors(currentLocation)for nextStep in nextSteps:#遍历下一步的状态，依次获得位置、方向、成本信息nextLocation =nextStep[0]nextDirection = nextStep[1]nextCost = nextStep[2]# 不在当前路径里面而且下一个位置还没被访问（多条路径交叉点）if (nextLocation not in currentPath.locations) and (nextLocation not in visited):if not problem.isGoalState(nextLocation):visited.append(nextLocation)print("访问的位置：", visited)#获取当前路径列表集nextLocations =currentPath.locations[:]#将新的位置加入到当前路径的列表里面nextLocations.append(nextLocation)print("当前位置：",currentLocation)print("当前位置下一步可能的移动位置：",nextLocation)print("加到当前位置列表集：",nextLocations)print()print()#print(currentLocation,nextLocation,nextLocations)#获取当前的方向集nextDirections = currentPath.directions[:]#将新的方向加入到当前方向集的列表里面nextDirections.append(nextDirection)nextCosts = currentPath.cost +nextCostnextPath =Path(nextLocations,nextDirections,nextCosts)#下一步的状态，入队列queue.push(nextPath)                    #队列为空，仍未到达终点，返回空集return []

    案例使用tinyMaze布局，从搜索问题problem的walls属性信息中可以获取迷宫墙的数字信息，如下图所示，要从（5，5）点到达（1，1）点，和深度优先算法不同，深度优先算法采样堆栈沿着一条路径深入遍历，然后遍历另一条路径；广度优先算法采用队列先进先出，层层遍历两条路径：

     pac man移动北、南、东、西移动与x，y的坐标变换关系：

广度优先搜索算法的遍历如下：

[SearchAgent] using function breadthFirstSearch
[SearchAgent] using problem type PositionSearchProblem
访问的位置： [(5, 5), (5, 4)]
当前位置： (5, 5)
当前位置下一步可能的移动位置： (5, 4)
加到当前位置列表集： [(5, 5), (5, 4)]访问的位置： [(5, 5), (5, 4), (4, 5)]
当前位置： (5, 5)
当前位置下一步可能的移动位置： (4, 5)
加到当前位置列表集： [(5, 5), (4, 5)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3)]
当前位置： (5, 4)
当前位置下一步可能的移动位置： (5, 3)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5)]
当前位置： (4, 5)
当前位置下一步可能的移动位置： (3, 5)
加到当前位置列表集： [(5, 5), (4, 5), (3, 5)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3)]
当前位置： (5, 3)
当前位置下一步可能的移动位置： (4, 3)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3), (4, 3)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5)]
当前位置： (3, 5)
当前位置下一步可能的移动位置： (2, 5)
加到当前位置列表集： [(5, 5), (4, 5), (3, 5), (2, 5)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2)]
当前位置： (4, 3)
当前位置下一步可能的移动位置： (4, 2)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3), (4, 3), (4, 2)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5)]
当前位置： (2, 5)
当前位置下一步可能的移动位置： (1, 5)
加到当前位置列表集： [(5, 5), (4, 5), (3, 5), (2, 5), (1, 5)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5), (3, 2)]
当前位置： (4, 2)
当前位置下一步可能的移动位置： (3, 2)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3), (4, 3), (4, 2), (3, 2)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5), (3, 2), (1, 4)]
当前位置： (1, 5)
当前位置下一步可能的移动位置： (1, 4)
加到当前位置列表集： [(5, 5), (4, 5), (3, 5), (2, 5), (1, 5), (1, 4)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5), (3, 2), (1, 4), (2, 2)]
当前位置： (3, 2)
当前位置下一步可能的移动位置： (2, 2)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3), (4, 3), (4, 2), (3, 2), (2, 2)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5), (3, 2), (1, 4), (2, 2), (1, 3)]
当前位置： (1, 4)
当前位置下一步可能的移动位置： (1, 3)
加到当前位置列表集： [(5, 5), (4, 5), (3, 5), (2, 5), (1, 5), (1, 4), (1, 3)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5), (3, 2), (1, 4), (2, 2), (1, 3), (2, 3)]
当前位置： (2, 2)
当前位置下一步可能的移动位置： (2, 3)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3), (4, 3), (4, 2), (3, 2), (2, 2), (2, 3)]访问的位置： [(5, 5), (5, 4), (4, 5), (5, 3), (3, 5), (4, 3), (2, 5), (4, 2), (1, 5), (3, 2), (1, 4), (2, 2), (1, 3), (2, 3), (2, 1)]
当前位置： (2, 2)
当前位置下一步可能的移动位置： (2, 1)
加到当前位置列表集： [(5, 5), (5, 4), (5, 3), (4, 3), (4, 2), (3, 2), (2, 2), (2, 1)]......

欢迎关注微信公众号：“从零起步学习人工智能”。