状态空间搜索核心算法代码实现(Python)

python                  def dfs_maze(maze, start, goal):                  """                  DFS求解迷宫问题                  :param maze: 二维列表，迷宫地图（0可走，1墙壁）                  :param start: 元组，初始位置 (x, y)                  :param goal: 元组，目标位置 (x, y)                  :return: 列表，从起点到终点的路径（无路径返回空列表）                  """                  rows = len(maze)                  cols = len(maze[0]) if rows > 0 else 0                  # 记录已访问状态（避免重复访问和循环，解决理论中“无限深度”问题）                  visited = [[False for _ in range(cols)] for _ in range(rows)]                  # 栈存储 (当前位置, 路径)，栈顶为当前探索节点，契合DFS后进先出特性                  stack = [(start, [start])]                  # 四向移动操作（上、下、左、右），对应理论中的“操作集合O”                  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]                  while stack:                  current_pos, path = stack.pop()# 后进先出，深度优先探索                  x, y = current_pos                  # 目标检测：到达出口则返回路径，对应理论中“目标状态G”判断                  if current_pos == goal:                  return path                  # 标记当前位置为已访问，避免重复探索                  if not visited[x][y]:                  visited[x][y] = True                  # 扩展节点：生成四向移动后的子状态，对应理论中“状态扩展”步骤                  for dx, dy in directions:                  new_x = x + dx                  new_y = y + dy                  # 验证子状态合法性：在迷宫范围内、可通行、未访问                  if 0 <= new_x < rows and 0 <= new_y < cols:                  if maze[new_x][new_y] == 0 and not visited[new_x][new_y]:                  new_pos = (new_x, new_y)                  new_path = path.copy()                  new_path.append(new_pos)                  stack.append((new_pos, new_path))                  # 栈空仍未找到目标，返回空路径（无解）                  return []                  # ------------------- 测试代码 -------------------                  if __name__ == "__main__":                  # 迷宫地图（0可走，1墙壁），对应理论中“状态空间SS”的实例化                  maze = [                  [0, 1, 0, 0, 0],                  [0, 1, 0, 1, 0],                  [0, 0, 0, 1, 0],                  [0, 1, 1, 1, 0],                  [0, 0, 0, 0, 0]                  ]                  start = (0, 0)# 初始状态S                  goal = (4, 4)# 目标状态G                  dfs_path = dfs_maze(maze, start, goal)                  if dfs_path:                  print("DFS找到迷宫路径（不一定最短）：")                  print(dfs_path)                  else:                  print("DFS未找到迷宫路径（无解）")

python                  from collections import deque                  def bfs_maze(maze, start, goal):                  """                  BFS求解迷宫最短路径问题                  :param maze: 二维列表，迷宫地图（0可走，1墙壁）                  :param start: 元组，初始位置 (x, y)                  :param goal: 元组，目标位置 (x, y)                  :return: 列表，从起点到终点的最短路径（无路径返回空列表）                  """                  rows = len(maze)                  cols = len(maze[0]) if rows > 0 else 0                  visited = [[False for _ in range(cols)] for _ in range(rows)]                  # 队列存储 (当前位置, 路径)，队首为当前探索节点，契合BFS先进先出特性                  queue = deque()                  queue.append((start, [start]))                  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 四向移动操作                  while queue:                  current_pos, path = queue.popleft()# 先进先出，按层遍历                  x, y = current_pos                  # 目标检测：到达出口即返回最短路径                  if current_pos == goal:                  return path                  # 标记当前位置为已访问，避免重复扩展                  if not visited[x][y]:                  visited[x][y] = True                  # 扩展当前状态的所有子状态，按层加入队列                  for dx, dy in directions:                  new_x = x + dx                  new_y = y + dy                  if 0 <= new_x < rows and 0 <= new_y < cols:                  if maze[new_x][new_y] == 0 and not visited[new_x][new_y]:                  new_pos = (new_x, new_y)                  new_path = path.copy()                  new_path.append(new_pos)                  queue.append((new_pos, new_path))                  return []                  # ------------------- 测试代码 -------------------                  if __name__ == "__main__":                  # 沿用上述迷宫地图，保持状态空间一致性                  maze = [                  [0, 1, 0, 0, 0],                  [0, 1, 0, 1, 0],                  [0, 0, 0, 1, 0],                  [0, 1, 1, 1, 0],                  [0, 0, 0, 0, 0]                  ]                  start = (0, 0)                  goal = (4, 4)                  bfs_path = bfs_maze(maze, start, goal)                  if bfs_path:                  print("BFS找到迷宫最短路径：")                  print(bfs_path)                  print(f"最短路径长度：{len(bfs_path)-1}（步数）")                  else:                  print("BFS未找到迷宫路径（无解）")                  

python                  import heapq                  def manhattan_distance(state, goal):                  """                  计算八数码问题的曼哈顿距离（启发函数h(n)，可采纳）                  :param state: 元组，当前棋局状态                  :param goal: 元组，目标棋局状态                  :return: 整数，曼哈顿距离总和（估计代价）                  """                  distance = 0                  # 预存目标状态中每个数字的位置，提升计算效率                  goal_pos = {num: (i//3, i%3) for i, num in enumerate(goal)}                  for i, num in enumerate(state):                  if num != 0:# 空格不计入距离，仅计算数字位置差                  x1, y1 = i//3, i%3# 当前数字的行列坐标                  x2, y2 = goal_pos[num]# 数字的目标行列坐标                  distance += abs(x1 - x2) + abs(y1 - y2)                  return distance                  def get_neighbors(state):                  """                  生成当前棋局的所有合法子状态（空格四向移动，对应操作集合O）                  :param state: 元组，当前棋局                  :return: 列表，合法子状态集合                  """                  neighbors = []                  empty_idx = state.index(0)# 定位空格位置索引                  x, y = empty_idx//3, empty_idx%3# 空格的行列坐标                  directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]# 空格四向移动                  for dx, dy in directions:                  new_x = x + dx                  new_y = y + dy                  # 验证移动合法性：空格需在3×3网格内                  if 0 <= new_x < 3 and 0 <= new_y < 3:                  new_empty_idx = new_x * 3 + new_y# 新空格位置索引                  # 交换空格与相邻数字，生成子状态                  state_list = list(state)                  state_list[empty_idx], state_list[new_empty_idx] = state_list[new_empty_idx], state_list[empty_idx]                  neighbors.append(tuple(state_list))                  return neighbors                  def a_star_8puzzle(start, goal):                  """                  A*算法求解八数码问题，结合实际代价g(n)和启发代价h(n)                  :param start: 元组，初始棋局（初始状态S）                  :param goal: 元组，目标棋局（目标状态G）                  :return: 列表，从初始到目标的最优路径（无路径返回空列表）                  """                  # 开放列表：用小根堆存储 (f(n), g(n), 当前状态, 路径)，优先扩展f(n)最小的状态                  open_list = []                  heapq.heappush(open_list, (0, 0, start, [start]))                  # 关闭列表：存储已扩展的状态，避免重复计算                  close_list = set()                  # g_dict：记录每个状态到初始状态的实际代价，优化重复状态的g值更新                  g_dict = {start: 0}                  while open_list:                  # 取出f(n)最小的状态，作为当前扩展节点                  f_n, g_n, current_state, path = heapq.heappop(open_list)                  # 目标检测：到达目标状态则返回最优路径                  if current_state == goal:                  return path                  # 若当前状态已扩展，直接跳过，避免重复处理                  if current_state in close_list:                  continue                  close_list.add(current_state)                  # 扩展当前状态的所有子状态，计算f(n)并加入开放列表                  for neighbor in get_neighbors(current_state):                  new_g = g_n + 1# 移动一步，实际代价g(n)加1                  # 若子状态未访问，或新路径的g值更小（更新更优路径）                  if neighbor not in g_dict or new_g < g_dict[neighbor]:                  g_dict[neighbor] = new_g                  h_n = manhattan_distance(neighbor, goal)# 计算启发代价                  new_f = new_g + h_n# 评估函数f(n) = g(n) + h(n)                  new_path = path.copy()                  new_path.append(neighbor)                  heapq.heappush(open_list, (new_f, new_g, neighbor, new_path))                  return []                  # ------------------- 测试代码 -------------------                  if __name__ == "__main__":                  # 初始状态（可替换为任意合法八数码棋局）                  start_state = (2, 8, 3, 1, 6, 4, 7, 0, 5)                  goal_state = (1, 2, 3, 4, 5, 6, 7, 8, 0)# 目标状态                  a_star_path = a_star_8puzzle(start_state, goal_state)                  if a_star_path:                  print("A*算法找到八数码最优路径，共{}步：".format(len(a_star_path)-1))                  for i, state in enumerate(a_star_path):                  print(f"第{i}步：")                  # 格式化输出棋局，便于观察状态变化                  for row in range(3):                  print(state[row*3 : (row+1)*3])                  print("-" * 10)                  else:                  print("该八数码棋局无解（八数码有1/2概率无解，需确保初始状态合法）")