Python基于递归算法实现的走迷宫问题

本文实例讲述了Python基于递归算法实现的走迷宫问题。分享给大家供大家参考,具体如下:

什么是递归?

简单地理解就是函数调用自身的过程就称之为递归。

什么时候用到递归?

如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法。
迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题。

在python中可以使用list嵌套表示二维数组。假设一个6*6的迷宫,问题时从该数组坐标[3][3]出发,判断能不能成功的走出迷宫。

maze=[[1,0,0,1,0,1],
   [1,1,1,0,1,0],
   [0,0,1,0,1,0],
   [0,1,1,1,0,0],
   [0,0,0,1,0,0],
   [1,0,0,0,0,0]]

针对这个迷宫问题,我们可以使用递归的思想很好的解决。对于数组中的一个点,该点的四个方向可以通过横纵坐标的加减轻松的表示,每当移动的一个可移动的点时候,整个问题又变为和初始状态一样的问题,继续搜索四个方向找可以移动的点,知道移动到数组的边缘。

所以我们可以这样编码:

# 判断坐标的有效性,如果超出数组边界或是不满足值为1的条件,说明该点无效返回False,否则返回True。
def valid(maze,x,y):
  if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
    return True
  else:
    return False
# 移步函数实现
def walk(maze,x,y):
  # 如果位置是迷宫的出口,说明成功走出迷宫
  if(x==0 and y==0):
    print("successful!")
    return True
  # 递归主体实现
  if valid(maze,x,y):
    # print(x,y)
    maze[x][y]=2 # 做标记,防止折回
    # 针对四个方向依次试探,如果失败,撤销一步
    if not walk(maze,x-1,y):
      maze[x][y]=1
    elif not walk(maze,x,y-1):
      maze[x][y]=1
    elif not walk(maze,x+1,y):
      maze[x][y]=1
    elif not walk(maze,x,y+1):
      maze[x][y]=1
    else:
      return False # 无路可走说明,没有解
  return True
walk(maze,3,3)

递归是个好东西呀!

PS:本站还有一个无限迷宫游戏,基于JS实现,提供给大家参考一下:

在线迷宫小游戏:
http://tools.jb51.net/games/migong

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

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

时间: 2017-08-03

Python基于回溯法子集树模板解决0-1背包问题实例

本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

Python基于回溯法子集树模板解决马踏棋盘问题示例

本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题.分享给大家供大家参考,具体如下: 问题 将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案. 分析 说明:这个图是5*5的棋盘. 类似于迷宫问题,只不过此问题的解长度固定为64 每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择. 走到一

Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法

本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情

Python基于回溯法子集树模板解决旅行商问题(TSP)实例

本文实例讲述了Python基于回溯法子集树模板解决旅行商问题(TSP).分享给大家供大家参考,具体如下: 问题 旅行商问题(Traveling Salesman Problem,TSP)是旅行商要到若干个城市旅行,各城市之间的费用是已知的,为了节省费用,旅行商决定从所在城市出发,到每个城市旅行一次后返回初始城市,问他应选择什么样的路线才能使所走的总费用最短? 分析 此问题可描述如下:G=(V,E)是带权的有向图,找到包含V中每个结点一个有向环,亦即一条周游路线,使得这个有向环上所有边成本之和最小

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

本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

Python基于回溯法子集树模板解决取物搭配问题实例

本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题.分享给大家供大家参考,具体如下: 问题 有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子.一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析 换个角度看,现有头.身.腿三个元素,每个元素都有各自的几种状态. 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状

Python使用回溯法子集树模板解决爬楼梯问题示例

本文实例讲述了Python使用回溯法子集树模板解决爬楼梯问题.分享给大家供大家参考,具体如下: 问题 某楼梯有n层台阶,每步只能走1级台阶,或2级台阶.从下向上爬楼梯,有多少种爬法? 分析 这个问题之前用分治法解决过.但是,这里我要用回溯法子集树模板解决它. 祭出元素-状态空间分析大法:每一步是一个元素,可走的步数[1,2]就是其状态空间.不难看出,元素不固定,状态空间固定. 直接上代码. 代码 '''爬楼梯''' n = 7 # 楼梯阶数 x = [] # 一个解(长度不固定,1-2数组,表示

Python基于回溯法子集树模板实现8皇后问题

本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

Python基于回溯法子集树模板解决数字组合问题实例

本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.

Python基于回溯法子集树模板实现图的遍历功能示例

本文实例讲述了Python基于回溯法子集树模板实现图的遍历功能.分享给大家供大家参考,具体如下: 问题 一个图: A --> B A --> C B --> C B --> D B --> E C --> A C --> D D --> C E --> F F --> C F --> D 从图中的一个节点E出发,不重复地经过所有其它节点后,回到出发节点E,称为一条路径.请找出所有可能的路径. 分析 将这个图可视化如下: 本问题涉及到图,那首

Python基于回溯法子集树模板解决最佳作业调度问题示例

本文实例讲述了Python基于回溯法子集树模板解决最佳作业调度问题.分享给大家供大家参考,具体如下: 问题 给定 n 个作业,每一个作业都有两项子任务需要分别在两台机器上完成.每一个作业必须先由机器1 处理,然后由机器2处理. 试设计一个算法找出完成这n个任务的最佳调度,使其机器2完成各作业时间之和达到最小. 分析: 看一个具体的例子: tji 机器1 机器2 作业1 2 1 作业2 3 1 作业3 2 3 最优调度顺序:1 3 2 处理时间:18 这3个作业的6种可能的调度方案是1,2,3:1

Python基于回溯法子集树模板解决找零问题示例

本文实例讲述了Python基于回溯法子集树模板解决找零问题.分享给大家供大家参考,具体如下: 问题 有面额10元.5元.2元.1元的硬币,数量分别为3个.5个.7个.12个.现在需要给顾客找零16元,要求硬币的个数最少,应该如何找零?或者指出该问题无解. 分析 元素--状态空间分析大法:四种面额的硬币看作4个元素,对应的数目看作各自的状态空间,遍历状态空间,其它的事情交给剪枝函数. 解的长度固定:4 解的编码:(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4

Python基于回溯法子集树模板解决野人与传教士问题示例

本文实例讲述了Python基于回溯法子集树模板解决野人与传教士问题.分享给大家供大家参考,具体如下: 问题 在河的左岸有N个传教士.N个野人和一条船,传教士们想用这条船把所有人都运过河去,但有以下条件限制: (1)修道士和野人都会划船,但船每次最多只能运M个人: (2)在任何岸边以及船上,野人数目都不能超过修道士,否则修道士会被野人吃掉. 假定野人会服从任何一种过河安排,请规划出一个确保修道士安全过河的计划. 分析 百度一下,网上全是用左岸的传教士和野人人数以及船的位置这样一个三元组作为状态,进

Python基于回溯法子集树模板解决选排问题示例

本文实例讲述了Python基于回溯法子集树模板解决选排问题.分享给大家供大家参考,具体如下: 问题 从n个元素中挑选m个元素进行排列,每个元素最多可重复r次.其中m∈[2,n],r∈[1,m]. 如:从4个元素中挑选3个元素进行排列,每个元素最多可重复r次. 分析 解x的长度是固定的,为m. 对于解x,先排第0个位置的元素x[0],再排第1个位置的元素x[1].我们把后者看作是前者的一种状态,即x[1]是x[0]的一种状态!! 一般地,把x[k]看作x[k-1]的状态空间a中的一种状态,我们要做

Python基于回溯法子集树模板解决m着色问题示例

本文实例讲述了Python基于回溯法子集树模板解决m着色问题.分享给大家供大家参考,具体如下: 问题 图的m-着色判定问题 给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色? 图的m-着色优化问题 若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数.求一个图的最小色数m的问题称为m-着色优化问题. 分析 解的长度是固定的,n.若x为本问题的一个解,则x[i]表示第i个节点的

Python基于回溯法子集树模板解决全排列问题示例

本文实例讲述了Python基于回溯法子集树模板解决全排列问题.分享给大家供大家参考,具体如下: 问题 实现 'a', 'b', 'c', 'd' 四个元素的全排列. 分析 这个问题可以直接套用排列树模板. 不过本文使用子集树模板.分析如下: 一个解x就是n个元素的一种排列,显然,解x的长度是固定的,n. 我们这样考虑:对于解x,先排第0个元素x[0],再排第1个元素x[1],...,当来到第k-1个元素x[k-1]时,就将剩下的未排的所有元素看作元素x[k-1]的状态空间,遍历之. 至此,套用子