• python宽度优先搜索算法
2020-11-27 15:59:22

# ----------

# ----------

# 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)

更多相关内容
• Python实现 宽度/广度优先搜索算法, 深度优先搜索算法1. 二叉树图2. 宽度/广度优先搜索算法(Breadth First Search，BSF)3. 深度优先搜索算法4. 宽度/广度优先搜索算法实现5. 深度优先搜索算法实现6. 完整代码实现 1....

# 1. 二叉树图

工作原理:

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

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

如上图的BFS访问顺序为：A->B->C->D->E->F

# 3. 深度优先搜索算法

工作原理:

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

如上图的BFS访问顺序为：A->B->D->E->C->F

# 4. 宽度/广度优先搜索算法实现

# 宽度优先算法的实现
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)



# 5. 深度优先搜索算法实现

# 深度优先算法的实现
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)



# 6. 完整代码实现

# -*- coding: utf-8 -*-
from collections import deque    # 线性表的模块

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

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.BFS('A')
print('宽度优先搜索:')
print('  ', end='  ')
g.node_print()  # A B C D E F
g.clear()

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


展开全文
• 基于python的广度优先搜索算法BFS设计与实现
• 本资源包括宽度优先搜索算法解决八数码问题的实验报告以及用python实现的源代码，有较详细的原理和设计思路，代码有详细的注释，适合初学者学习。
• 主要介绍了python 递归深度优先搜索与广度优先搜索算法模拟实现 ,非常不错，具有一定的参考借鉴价值，需要的朋友可以参考下
 实验目的： 了解和掌握深度优先和宽度优先算法的原理以及应用并实现两种算法。 实验内容： 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 = {}

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.BFS('A')
print('宽度优先搜索:')
print('  ', end='  ')
g.node_print()
g.clear()

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

展开全文
• 人工智能作业,利用python实现宽度优先BFS搜索解决八数码问题
• 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]....
'''
by Jun
'''
import copy
import numpy as np
from datetime import datetime

# 字符串列表化
def string_to_ls(str):
return [i.split(' ') for i in str.split(',')]

# 获取位置
def get_loacl(arr, target):
# r, c = np.where(arr == target)
# return r, c
for i in arr:
for j in i:
if j == target:
return arr.index(i), i.index(j)

# 获取可以和0交换位置的元素
def get_elements(arr):
r, c = get_loacl(arr, '0')
elements = []
if r > 0:
elements.append(arr[r - 1][c])  # 上面的元素
if r < 2:
elements.append(arr[r + 1][c])  # 下边的元素
if c > 0:
elements.append(arr[r][c - 1])  # 左面的元素
if c < 2:
elements.append(arr[r][c + 1])  # 右面的元素
return elements

def get_child(arr, e):
# 深拷贝与浅拷贝！!
arr_new = copy.deepcopy(arr)
r, c = get_loacl(arr_new, '0')
r1, c1 = get_loacl(arr_new, e)
arr_new[r][c], arr_new[r1][c1] = arr_new[r1][c1], arr_new[r][c]
return arr_new

def is_goal(arr, goal):
return arr == goal

class state:
def __init__(self, state, parent):
# state是一个3x3的ls矩阵
self.state = state
self.parent = parent

def chidren(self):
chidren = []
for i in get_elements(self.state):
child = state(state=get_child(self.state, i), parent=self)
chidren.append(child)
return chidren

# 打印求解路径
def print_path(n):
if n.parent == None:
return
else:
print('↑')
print(np.array(n.parent.state))
print_path(n.parent)

if __name__ == '__main__':
initial = '0 1 3,4 2 5,7 8 6'
goal = '4 1 3,7 0 5,8 2 6'
# initial = '0 7 8,2 5 4,3 6 1'
# goal = '7 5 8,2 4 1,3 6 0'
# initial = '4 0 1,6 8 5,7 3 2'
# goal = '5 8 2,1 0 4,6 3 7'
initial_arr = state(string_to_ls(initial), parent=None)
goal_arr = string_to_ls(goal)
start = datetime.now()
open = [initial_arr]
close = []
while len(open) > 0:
open_tb = [i.state for i in open]
close_tb = [i.state for i in close]
n = open.pop(0)
close.append(n)
if is_goal(n.state, goal_arr):
print(np.array(n.state))
print_path(n)
print('最优求解过程如上')
break
else:
for i in n.chidren():
if i.state not in open_tb:
if i.state not in close_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].state))
print('共耗时:', end - start)
print('搜索步骤为{}'.format(len(close) - 1))


展开全文
• 开始宽度优先搜索图graph，搜索过程中记录到达步数； 设置搜索队列Q，设置集合visit，记录搜索过的顶点，将（beginword,1）添加到队列 只要队列不空，取出队列头部元素 （1）若取出的队列头部元素为endword...
• 宽度优先搜索算法python实现本文博客链接:http://blog.csdn.net/jdh99,作者:jdh,转载请注明. 环境：主机:WIN10python版本:3.5开发环境:pyCharm说明：本程序是udp客户端模块。绑定固定端口进行收发。udp接收是一个...
• 深度优先搜索算法2.广度优先搜索算法三、实验代码和用于测试的迷宫1.实验代码2.测试迷宫2.1 maze1.txt2.2 maze2.txt2.3 maze3.txt四、实验结果1. maze1.txt2. maze2.txt3. maze3.txt五、结果分析总结 一、实验内容 ...
• 基于C++的 BFS算法解决8数码问题 没有做界面 直接是输出步骤 算法是亮点
• Python代码实现的伪代码如下： 2、广度优先算法：遍历规则：1)先访问完当前顶点的所有邻接点。(应该看得出广度的意思)2)先访问顶点的邻接点先于后访问顶点的邻接点被访问。最后得出的结果为：ABCDEFGH。Python代码...
• 1. 深度优先搜索介绍图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点...
• ​leetcode.com第一， Python 代码， 用非递归遍历，题目已经假定了root 非空， 用队列（Python 用list 模拟队列），先添加root到队列中，出队列，再判右子树不为空，就添加右子树，再判断左子树是不是为空，非空...
• 【问题描述】采用宽度优先搜索算法求解TSP问题，并在搜索过程中，使用界限条件（当前结点已经走过的路径长度要小于已求得的最短路径）进行“剪枝”操作（不再对后续结点进行遍历），从而提高搜索效率。采用queue模块...
• python算法分析与设计实验：宽度优先查找最短路径 一、实验目的 ...3、熟练掌握图上深度优先搜索算法及其算法复杂度分析，了解深度优先算法的建模过程。 二、实验工具 Win10操作系统、python3.7...
• 【问题描述】采用宽度优先搜索算法求解TSP问题，并在搜索过程中，使用界限条件（当前结点已经走过的路径长度要小于已求得的最短路径）进行“剪枝”操作（不再对后续结点进行遍历），从而提高搜索效率。采用queue模块...
• 广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
• 参考： 清华大学出版社....内容： 使用python实现了三种不同启发函数的A*搜索算法（图搜索），以及宽度优先搜索和深度优先搜索，并计算扩展结点数和生成结点数，可以输出解路径。有GUI交互界面。 License: MIT ...
• ## 宽度优先搜索算法解决八数码问题

万次阅读 多人点赞 2020-05-19 23:44:41
宽度优先搜索算法解决八数码问题 实验原理 1、宽度优先搜索是指在一个搜索树中，搜索以同层邻近节点依次扩展节点。这种搜索是逐层进行的，在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。 宽度优先...
• 使用过程式，宽度优先，A算法求解八数码问题
• 一、算法原理 ...宽度优先搜索算法(Breadth First Search，BSF)，思想是： 从图中某顶点v出发，首先访问定点v 在访问了v之后依次访问v的各个未曾访问过的邻接点； 然后分别从这些邻接点出发依次访...
• 通俗易懂广度优先搜索算法
• 该程序实现用深度优先搜索算法解决八数码问题，代码有详细的注释，适合初学者学习。在学习过程中有问题可以评论交流。
• 宽度优先搜索BFS 工作方式： 从根节点开始，由里向外，逐层遍历所有节点——它每次总是扩展深度最浅的节点。 BFS方法，从根节点1开始，下图遍历顺序是：1，2，3，4，5，6 优先访问深度最浅的节点，故，老节点总是...
• 本文实例讲述了Python数据结构与算法之图的广度优先与深度优先搜索算法。分享给大家供大家参考，具体如下： 根据维基百科的伪代码实现： 广度优先BFS： 使用队列，集合 标记初始结点已被发现，放入队列 每次循环从...
• 一、BFS的介绍 BFS（广度优先搜索，也可称宽度优先搜索）是连通图的一种遍历策略。因为它的基本思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域。 广度优先搜索（BFS）类似于二叉树的层序遍历算法，它的...
• 算法之广度优先搜索（breadth-first search，BFS）： 广度优先搜索是一种用于图的查找算法，可解决以下两类问题： 第一类问题：从节点A出发，有前往节点B的路径吗？ 第二类问题：从节点A出发，前往节点B的哪条路径...

...