时间戳

首页 > 解决方案 > 深度优先搜索 8 益智游戏“从空列表中弹出”

python - 深度优先搜索 8 益智游戏“从空列表中弹出”

问题描述

我必须执行深度优先搜索来解决 8 益智游戏：（-1 代表空值）

initialState1 = [[-1,1,2], [7,8,3], [6,5,4]]
finalState1 = [[1,2,3], [8,-1,4], [7,6,5]]

我的代码：

def play(puzzle, direction):
  print(puzzle)
  if direction == "up":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j]==-1):
          if i!=0:
            puzzle[i][j] = puzzle[i-1][j]
            puzzle[i-1][j] = -1
          return puzzle

  if direction=="down":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j]==-1):
          if i!=2:
            puzzle[i][j] = puzzle[i+1][j]
            puzzle[i+1][j] = -1
          return puzzle

  if direction == "left":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j] == -1):
          if j!=0:
            puzzle[i][j] = puzzle[i][j-1]
            puzzle[i][j-1] = -1
          return puzzle

  if direction == "right":
    for i in range(3):
      for j in range(3):
        if(puzzle[i][j] == -1):
          if j!=2:
            puzzle[i][j] = puzzle[i][j+1]
            puzzle[i][j+1] = -1
          return puzzle

def checkBoundaries(puzzle):
    possibilities = []
    for i in range(3):
        for j in range(3):
            if(puzzle[i][j]==-1):
                if(i == 0):
                    if(j == 0):
                        possibilities.append("down")
                        possibilities.append("right")
                    elif(j == 1):
                        possibilities.append("down")
                        possibilities.append("right")
                        possibilities.append("left")
                    elif(j == 2):
                        possibilities.append("down")
                        possibilities.append("left")
                if(i == 1):
                    if(j == 0):
                        possibilities.append("down")
                        possibilities.append("right")
                        possibilities.append("up")
                    elif(j == 1):
                        possibilities.append("down")
                        possibilities.append("right")
                        possibilities.append("left")
                        possibilities.append("up")
                    elif(j == 2):
                        possibilities.append("down")
                        possibilities.append("left")
                        possibilities.append("up")
                if(i == 2):
                    if(j == 0):
                        possibilities.append("up")
                        possibilities.append("right")
                    elif(j == 1):
                        possibilities.append("up")
                        possibilities.append("right")
                        possibilities.append("left")
                    elif(j == 2):
                        possibilities.append("up")
                        possibilities.append("left")
                        
    return random.choice(possibilities)

def depthFirstSearch():
  pathcost=0
  queue=[]
  initialFormatted=[initialState1,"none"]
  queue.append(initialFormatted)

  while(True):
    puzzle=queue.pop(0)
    pathcost=pathcost+1
    print(str(puzzle[1])+" --> "+str(puzzle[0]))
    if(puzzle[0] == finalState1):
      print("Found")
      print("Path cost -> "+str(pathcost-1))
      break
    else:
      nextMove=play(puzzle[0], checkBoundaries(puzzle[0]))
      if(nextMove!=puzzle[0]):
          nextMove=[nextMove,checkBoundaries(puzzle[0])]
          queue.insert(0, nextMove)

depthFirstSearch()

但运行此代码，我收到此错误：

puzzle=queue.pop(0) IndexError: 从空列表中弹出

如何处理？我做错了什么？

我的代码是否在做正确的事情来实现我的目标？在 checkBoudaries 方法中，我目前正在设置一个随机值（在可能性范围内）以返回.. 是正确的还是我必须更喜欢基于最后一步的移动？

标签： pythondepth-first-search

解决方案

这里存在多个概念问题，以至于尝试编写更正版本的工作量太大。但是，我想我现在已经很好地理解了您尝试的一般结构，可以修复它。

  1. 您正在使用基于队列的方法（与递归方法相反），这意味着您需要跟踪队列节点本身中的路径成本（或者，如果您想跟踪它们，则需要跟踪整个路径）。（在递归方法中，您将在递归调用中传递此信息。）

  2. 您正在使用基于队列的方法。这自然实现了广度优先搜索。您需要一个堆栈，以便在“父”位置的其他可能性之前尝试来自当前位置的新可能性。

  3. 您正在解决的特定问题使循环成为可能。您需要对此进行某种检测。一个简单的方法是保持一个set先前看到的位置。

  4. 您需要彻底搜索，而不仅仅是从当前位置选择一个动作。这就是算法的全部要点。possibilities您应该返回from的整个列表checkBoundaries，并为每种可能性添加一个单独的节点到堆栈中。

但实际上导致报告的问题的事情：

  if(nextMove!=puzzle[0]):
      nextMove=[nextMove,checkBoundaries(puzzle[0])]
      queue.insert(0, nextMove)

这个检查不应该是必要的，因为你只应该尝试有效的移动，而有效的移动应该（根据定义）改变棋盘位置。

但除此之外，你永远不会在队列中插入任何东西，因为这个条件永远不会满足 -nextMove总是等于，即使你改变了棋盘位置。为什么？因为是同一个对象。您的代码中没有任何内容会复制板对象；所以队列包含多个副本；代码修改了相同的单个对象并将其返回给您等。这是 Python 中的一个常见问题，以多种形式表现出来 - 没有什么是完全重复的，但它与例如List of lists的问题相同意外反映在子列表中的更改。puzzle[0]play

这意味着，即使您删除了不必要的检查，您仍然会遇到问题 - 因为您的play函数会影响队列中的每个节点。您需要重写play，以便它创建一个代表“下一个”棋盘位置的新列表列表，而无需修改输入。

推荐阅读