8字谜宽度优先搜索

Question

我把它从代码审查移走了，因为那里的人建议把它张贴在这里

我尝试使用pycharm做8字谜，我将首先生成一个3x3的列表，然后将其洗牌以获得初始板状态示例：

[1 , 2 , 3 ] [4 , 5 , 6 ] [7 , 8 , 9 ]

然后我会在上面做一些随机移动来获得目标板状态：

[ 3 , 2 , 1 ] [ 6 , 5 , 4 ] [ 9 , 8 , 7 ]

当我将大小设置为3（3x3）时，它永远不会完成搜索，当我将大小设置为2时，它会解决问题，但有时它会用尽边界列表并返回任何内容，这应该是不可能的。在

编辑

我换了

return Solution (start_node, numExplored, memoryRequired)

到

^{pr2}$

它总是返回2x2，3x3的解决方案，但是仍然很慢

我用Python编写了以下代码：

def breadthFirstSearch(problem):

    """Search the shallowest nodes in the search tree first."""

    frontier = util.Queue()
    explored = []
    numExplored = 0
    memoryRequired = 0

    # generate start node
    start_node = Node(problem.getStartState(), None, 0, None)

    # return immediately if start node is the goal state
    if problem.isGoalState(start_node.state):
        return Solution(start_node, 0, 0)

    # push start node into frontier
    frontier.push (start_node)

    # while frontier list is not empty
    while not frontier.isEmpty():

         # get the first-in frontier node from frontier list
        fr_node = frontier.pop()
        explored.append(fr_node)    

        # get successor nodes
        successors = problem.getSuccessors(fr_node.state)
        numExplored += 1

        # append into explored list
        # if len(successors) >0:
        #     explored.append(fr_node)
        # else:
        #     explored.append(fr_node)

        # for each successor node
        for sc_state, sc_action, sc_cost in successors:

            # generate successor node
            sc_node = Node(sc_state, sc_action, sc_cost, fr_node)

            # check for goal state immediately after generate
            if problem.isGoalState(sc_node.state):  # if found solution
                return Solution (sc_node, numExplored, memoryRequired)

            # insert successor node into frontier list (if not found in explored and frontier)
            if sc_node not in explored and sc_node not in frontier.list:
                frontier.push(sc_node)

            memoryRequired = max ([memoryRequired, len(frontier.list)+len(explored)])

        print ('Frontier size = %d, Explored size = %d, Total size = %d ,Successor Length= %d' %(len(frontier.list), len(explored), len(frontier.list)+len(explored), len(successors)))

    return Solution (start_node, numExplored, memoryRequired)

节点定义为：

class Node:
    def __init__(self, state, action, cost, parent):
        self.state  = state
        self.cost   = cost
        self.action = action
        self.parent = parent
        if parent is None:
            self.totalCost = cost
            self.depth = 0
        else:
            self.totalCost = parent.totalCost + cost
            self.depth = parent.depth + 1

    def __eq__(self, other):
        return  hasattr(other,'state') and self.state == other.state

然后是定义NPuzzle和Puzzle状态的文件。在

class ActionType:
    UP = 'up'
    DOWN = 'down'
    LEFT = 'left'
    RIGHT = 'right'

    Actions = [ActionType.UP, ActionType.DOWN, ActionType.LEFT,
                ActionType.RIGHT]

class PuzzleState (SearchState):
    def __init__ (self, n, board = None):
        self.n = n
        self.board = [[j for j in range(n*i,n*i+n)] for i in range(n)]
        self.blankCellPos = self.getBlankCellPos()

    def __eq__ (self, other):
        if self.board == other.board:
            return True
        else:
            return False

    def deepCopy(self):
        state = copy.deepcopy(self) #PuzzleState(self.n)
        return state

    def getBlankCellPos (self):     
        for i in range(self.n):
            for j in range(self.n):
                if self.board[i][j] == 0:
                    return (i,j)


    def isValidAction (self, action):       
        (r,c)= self.blankCellPos
        if action == ActionType.UP:
            if r - 1 < 0:
                return False
            else:
                return True
        elif action == ActionType.DOWN:
            if r + 1 > self.n-1:
                return False
            else:
                return True
        elif action == ActionType.LEFT:
            if c - 1 < 0:
                return False
            else:
                return True
        elif action == ActionType.RIGHT:
            if c + 1 > self.n-1:
                return False
            else:
                return True

    def getValidActions (self):
        ValidActions = []

        for action in Actions:
            if(self.isValidAction(action) == True):
                ValidActions.append(action)

        return ValidActions

    def move (self, action):
        (r,c) = self.blankCellPos
        if action == ActionType.UP:
            self.blankCellPos = (r-1,c)
            self.board[r][c], self.board[r-1][c] = self.board[r-1][c], self.board[r][c]
        elif action == ActionType.DOWN:
            self.blankCellPos = (r+1,c)
            self.board[r][c], self.board[r+1][c] = self.board[r+1][c], self.board[r][c]
        elif action == ActionType.LEFT:
            self.blankCellPos = (r, c-1)
            self.board[r][c], self.board[r][c-1] = self.board[r][c-1], self.board[r][c]
        elif action == ActionType.RIGHT:
            self.blankCellPos = (r, c+1)
            self.board[r][c], self.board[r][c+1] = self.board[r][c+1], self.board[r][c]

    def randomMove (self, numMoves):
        #(r,c) = self.board.blankCellPos
        ValidActions = []
        actions = []
        tmp = -1
        for num in range(numMoves):
            ValidActions = self.getValidActions()
            tmp = random.choice(ValidActions)

            #remove loopy choices#
            if num > 0:
                if actions[-1] == ActionType.UP and tmp == ActionType.DOWN:
                    ValidActions.remove(ActionType.DOWN)
                    tmp = random.choice(ValidActions)
                elif actions[-1] == ActionType.DOWN and tmp == ActionType.UP:
                    ValidActions.remove(ActionType.UP)
                    tmp = random.choice(ValidActions)
                elif actions[-1] == ActionType.LEFT and tmp == ActionType.RIGHT:
                    ValidActions.remove(ActionType.RIGHT)
                    tmp = random.choice(ValidActions)
                elif actions[-1] == ActionType.RIGHT and tmp == ActionType.LEFT:
                    ValidActions.remove(ActionType.LEFT)
                    tmp = random.choice(ValidActions)

            actions.append(tmp)
            self.move(tmp)

    def randomInitialize (self):
        random.shuffle(self.board)
        for ii, sublist in enumerate(self.board):
            random.shuffle(self.board[ii])
        self.blankCellPos = self.getBlankCellPos()

    def display (self):
        print( '   ',)
        #for c in range (self.n):
        print (self.board)
            #print ('  %d' %(c),)

class NPuzzle (SearchProblem):

    def __init__ (self, n, startState = None, goalState = None):
        self.n = PuzzleState(n)
        self.startState = self.n.deepCopy()
        self.goalState = self.n.deepCopy()

    def randomStartState (self):
        self.startState.randomInitialize()

    def randomGoalState(self, numMoves):
        self.goalState.randomMove(numMoves)

    def setStartState (self, startState):
        self.startState = startState

    def setGoalState (self, goalState):
        self.goalState = goalState

    def getStartState (self):
        return self.startState

    def getGoalState (self):
        return self.goalState

    def isGoalState(self, state):
        if state == self.goalState:
            return True
        else:
            return False

    def getSuccessors (self, state):
        successorlist = []
        validActions = state.getValidActions()

        for action in validActions:
            #if not deep copy what will happen?
            successor = state.deepCopy()
            successor.move(action)

            self.cost = 1

            successorlist.append([successor, action, self.cost])

        return successorlist

根据我读到的内容和我的讲师告诉我的，这台机器应该每秒在数千个搜索中打出一些东西，但当我运行它时，它只在最初的几千个节点上显得非常快，然后在那之后就慢得很厉害了。在

我不知道怎么了。如有任何提示，我们将不胜感激。在