Python使用回溯法子集树模板解决迷宫问题示例

本文实例讲述了Python使用回溯法解决迷宫问题。分享给大家供大家参考，具体如下：

问题

给定一个迷宫，入口已知。问是否有路径从入口到出口，若有则输出一条这样的路径。注意移动可以从上、下、左、右、上左、上右、下左、下右八个方向进行。迷宫输入0表示可走，输入1表示墙。为方便起见，用1将迷宫围起来避免边界问题。

分析

考虑到左、右是相对的，因此修改为：北、东北、东、东南、南、西南、西、西北八个方向。在任意一格内，有8个方向可以选择，亦即8种状态可选。因此从入口格子开始，每进入一格都要遍历这8种状态。

显然，可以套用回溯法的子集树模板。

注意，解的长度是不固定的。

代码

# 迷宫（1是墙，0是通路）
maze = [[1,1,1,1,1,1,1,1,1,1],
    [0,0,1,0,1,1,1,1,0,1],
    [1,1,0,1,0,1,1,0,1,1],
    [1,0,1,1,1,0,0,1,1,1],
    [1,1,1,0,0,1,1,0,1,1],
    [1,1,0,1,1,1,1,1,0,1],
    [1,0,1,0,0,1,1,1,1,0],
    [1,1,1,1,1,0,1,1,1,1]]
m, n = 8, 10  # 8行，10列
entry = (1,0) # 迷宫入口
path = [entry] # 一个解（路径）
paths = []   # 一组解
# 移动的方向（顺时针8个：N, EN, E, ES, S, WS, W, WN）
directions = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
# 冲突检测
def conflict(nx, ny):
  global m,n,maze
  # 是否在迷宫中，以及是否可通行
  if 0 <= nx < m and 0 <= ny < n and maze[nx][ny]==0:
    return False
  return True
# 套用子集树模板
def walk(x, y): # 到达(x,y)格子
  global entry,m,n,maze,path,paths,directions
  if (x,y) != entry and (x % (m-1) ==0 or y % (n-1) == 0): # 出口
    #print(path)
    paths.append(path[:]) # 直接保存，未做最优化
  else:
    for d in directions: # 遍历8个方向(亦即8个状态)
      nx, ny = x+d[0], y+d[1]
      path.append((nx,ny))   # 保存，新坐标入栈
      if not conflict(nx, ny): # 剪枝
        maze[nx][ny] = 2     # 标记，已访问（奇怪，此两句只能放在if区块内！）
        walk(nx, ny)
        maze[nx][ny] = 0     # 回溯，恢复
      path.pop()        # 回溯，出栈
# 解的可视化（根据一个解x，复原迷宫路径，'2'表示通路）
def show(path):
  global maze
  import pprint, copy
  maze2 = copy.deepcopy(maze)
  for p in path:
    maze2[p[0]][p[1]] = 2 # 通路
  pprint.pprint(maze) # 原迷宫
  print()
  pprint.pprint(maze2) # 带通路的迷宫
# 测试
walk(1,0)
print(paths[-1], '\n') # 看看最后一条路径
show(paths[-1])

效果图

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

# Python  # 回溯法  # 子集树模板  # 解决  # 迷宫问题  # Python解决走迷宫问题算法示例  # Python基于递归算法实现的走迷宫问题  # Python 实现递归法解决迷宫问题的示例代码  # python迷宫问题深度优先遍历实例  # 使用python求解迷宫问题的三种实现方法  # 遍历  # 亦即  # 进阶  # 放在  # 相关内容  # 都要  # 感兴趣  # 数据结构  # 给大家  # 考虑到  # 可选  # 两句  # 若有  # 可以选择  # 更多关于  # 所述  # 程序设计  # 使用技巧  # 可走  # 未做 

相关文章： 家具网站制作软件,家具厂怎么跑业务？  长春网站建设制作公司,长春的网络公司怎么样主要是能做网站的？  广德云建站网站建设方案与建站流程优化指南  如何快速完成中国万网建站详细流程？  如何通过西部建站助手安装IIS服务器？  如何通过商城自助建站源码实现零基础高效建站？  如何制作网站标识牌,动态网站如何制作（教程）？  建站之星伪静态规则如何正确配置？  如何选择适合PHP云建站的开源框架？  建站之星后台密码如何安全设置与找回？  免费网站制作appp,免费制作app哪个平台好？  自助网站制作软件,个人如何自助建网站？  建站之星云端配置指南：模板选择与SEO优化一键生成  公司网站的制作公司,企业网站制作基本流程有哪些？  如何在Mac上搭建Golang开发环境_使用Homebrew安装和管理Go版本  如何正确下载安装西数主机建站助手？  如何选择可靠的免备案建站服务器？  定制建站策划方案_专业建站与网站建设方案一站式指南  企业网站制作费用多少,企业网站空间一般需要多大，费用是多少？  如何快速配置高效服务器建站软件？  网站制作大概多少钱一个,做一个平台网站大概多少钱？  javascript中的try catch异常捕获机制用法分析  制作网站的公司有哪些,做一个公司网站要多少钱？  深入理解Android中的xmlns:tools属性  网站按钮制作软件,如何实现网页中按钮的自动点击？  如何在IIS服务器上快速部署高效网站？  在线ppt制作网站有哪些软件,如何把网页的内容做成ppt？  微信小程序制作网站有哪些,微信小程序需要做网站吗？  外汇网站制作流程,如何在工商银行网站上做外汇买卖？  如何在阿里云ECS服务器部署织梦CMS网站？  如何在Golang中引入测试模块_Golang测试包导入与使用实践  建站之星伪静态规则如何设置？  清单制作人网站有哪些,近日“兴风作浪的姑奶奶”引起很多人的关注这是什么事情？  商务网站制作工程师,从哪几个方面把握电子商务网站主页和页面的特色设计？  平台云上自助建站如何快速打造专业网站？  教学网站制作软件,学习*后期制作的网站有哪些？  品牌网站制作公司有哪些,买正品品牌一般去哪个网站买？  网站制作难吗安全吗,做一个网站需要多久时间？  做企业网站制作流程,企业网站制作基本流程有哪些？  建站之星后台密码遗忘或太弱？如何重置与强化？  魔毅自助建站系统：模板定制与SEO优化一键生成指南  h5网站制作工具有哪些,h5页面制作工具有哪些？  实例解析angularjs的filter过滤器  如何在阿里云高效完成企业建站全流程？  如何在IIS中新建站点并配置端口与IP地址？  如何配置支付宝与微信支付功能？  英语简历制作免费网站推荐,如何将简历翻译成英文？  平台云上自主建站：模板化设计与智能工具打造高效网站  济南企业网站制作公司,济南社保单位网上缴费步骤？  如何高效完成独享虚拟主机建站？