미로 문제를 해결하기 위해 Python의 역추적 하위 집합 트리 템플릿 사용에 대한 자세한 설명

이 글에서는 미로 문제를 해결하기 위한 Python의 역추적 방법을 주로 소개하고, 역추적 방법 하위 집합 트리 템플릿을 기반으로 Python에서 미로 문제를 해결하기 위한 관련 운영 기술과 주의 사항을 분석합니다. 참고로

이 문서의 예에서는 Python이 역추적 방법을 사용하여 미로 문제를 해결하는 방법을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

Problem

미로를 놓으면 입구가 보입니다. 입구에서 출구까지의 경로가 있는지 물어보고, 있다면 해당 경로를 출력합니다. 이동은 위, 아래, 왼쪽, 오른쪽, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 등 8개 방향으로 수행할 수 있습니다. 미로에 0을 입력하면 걸을 수 있다는 뜻이고, 1을 입력하면 벽이라는 의미입니다. 편의상 경계 문제를 피하기 위해 미로를 1로 둘러쌉니다.

분석

왼쪽과 오른쪽이 상대적이라는 점을 고려하여 북쪽, 북동쪽, 동쪽, 남동쪽, 남쪽, 남서쪽, 서쪽, 북서쪽의 8개 방향으로 수정됩니다. 어떤 그리드에는 선택할 수 있는 방향이 8개 있습니다. 즉, 선택할 수 있는 상태가 8개입니다. 따라서 입구 그리드부터 시작하여 그리드에 들어갈 때마다 이 8가지 상태를 통과해야 합니다.

분명히 역추적 방법의 하위 집합 트리 템플릿을 적용할 수 있습니다.

솔루션의 길이는 고정되어 있지 않습니다.

Code

# 迷宫（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，复原迷宫路径，&#39;2&#39;表示通路）
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], &#39;\n&#39;) # 看看最后一条路径
show(paths[-1])

Rendering

위 내용은 미로 문제를 해결하기 위해 Python의 역추적 하위 집합 트리 템플릿 사용에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!