为什么这个不能正常工作？

Question

写了一个A*实现来解决8字谜游戏。出于某种原因，该算法适用于不太复杂的难题。我尝试了最坏的情况下的情况下，它返回了一个非最佳的结果。是我的启发式错误，还是我的堆弹出错误的值，什么可能是错误的？你知道吗

最坏情况：

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

这是我的密码

def ast(board, isDraw):
    """ Computes the steps to solve the puzzle using A*
            RETURNS: Path, Depth of Node, Max Depth of graph, Number of Expanded nodes, time algorithm finished"""
    solvedBoard = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]  # SolvedBoard
    maxDepth = 0
    nodesExpanded = 0

    open = list()
    opend = dict()
    closed = list()
    closedd = dict()

    # Find where 0 is on board
    for row in range(3):
        for column in range(3):
            if 0 == board[row][column]:
                posn = [row, column]

    root = Node(list(), board, posn, 0, f=0)
    heapq.heappush(open, root)
    opend[hash(root)] = root

    while len(open) > 0:
        node = heapq.heappop(open)
        del(opend[hash(node)])
        nodesExpanded += 1

        for child in node.getChildren():
            maxDepth = max(child.depth, maxDepth)
            if child.board == solvedBoard:
                finishedTime = time.clock()
                return (child.path, child.depth, maxDepth, nodesExpanded, finishedTime)
            else:
                if hash(child) in opend.keys() and opend[hash(child)] < child.f:
                    continue
                if hash(child) in closedd.keys() and closedd[hash(child)] < child.f:
                    continue
                heapq.heappush(open,child)
                opend[hash(child)] = child
        heapq.heappush(closed, node)
        closedd[hash(node)] = node
    finishedTime = time.clock()
    return ("There is no solution for this configuration of the board","?",maxDepth,nodesExpanded,finishedTime)

节点类

class Node:
    def __init__(self, path, board, posn, depth, direction=None, f=None):
        self.path = path
        self.depth = depth
        self.board = board
        self.posn = posn
        self.__children = list()
        self.visited = False

        if direction is not None:
            self.direction = direction
            self.__postProcess(direction)

        self.g = len(path)
        self.h = self.__getHeuristic()
        if f is None:
            self.f = self.g + self.h
        else:
            self.f = f


    def __repr__(self):
       #return "*" + ''.join(str(e) for e in self.board) + "*" DEBUG
        return str(hash(self))

    def __eq__(self, other):
        return isinstance(other, self.__class__) and self.board == other.board

    def __hash__(self):
        array = tuple(self.board[0] + self.board[1] + self.board[2])
        return hash(array)

    def __lt__(self, other):
        return self.f

    def getParentHash(self):
        """Calculates the parent, of this nodes, hash"""
        dboard = deepcopy(self.board)
        # Find where 0 is on board
        for row in range(3):
            for column in range(3):
                if 0 == dboard[row][column]:
                    posn = [row, column]
        #Undo last step to deepcopy board
        if self.path[-1] == "Right":
            dboard[posn[0]][posn[1]] = dboard[posn[0]][posn[1]-1]
            dboard[posn[0]][posn[1]-1] = 0
        elif self.path[-1] == "Left":
            dboard[posn[0]][posn[1]] = dboard[posn[0]][posn[1]+1]
            dboard[posn[0]][posn[1]+1] = 0
        elif self.path[-1] == "Up":
            dboard[posn[0]][posn[1]] = dboard[posn[0]+1][posn[1]]
            dboard[posn[0]+1][posn[1]] = 0
        elif self.path[-1] == "Down":
            dboard[posn[0]][posn[1]] = dboard[posn[0]-1][posn[1]]
            dboard[posn[0]-1][posn[1]] = 0
        return hash(tuple(dboard[0] + dboard[1] + dboard[2]))


    def getChildren(self):
        """getChildren generates children of node, if they have not be prev generated or the node has not been visited yet, returns all children for the given node"""
        if len(self.__children) == 0 and not self.visited:   #allows me to print a graph given the root node
            cdn = list()
            if 0 not in self.board[0]:
                cdn.append(Node(self.path[:], deepcopy(self.board), self.posn[:], self.depth + 1, 'Up'))
            if 0 not in self.board[2]:
                cdn.append(Node(self.path[:], deepcopy(self.board), self.posn[:], self.depth + 1, 'Down'))
            if 0 not in (self.board[0][0], self.board[1][0], self.board[2][0]):
                cdn.append(Node(self.path[:], deepcopy(self.board), self.posn[:], self.depth + 1, 'Left'))
            if 0 not in (self.board[0][2], self.board[1][2], self.board[2][2]):
                cdn.append(Node(self.path[:], deepcopy(self.board), self.posn[:], self.depth + 1, 'Right'))
            self.__children = cdn
            self.visited = True
            return cdn
        else:
            return self.__children

    def __getPos(self, num):
        for row in range(3):
            for column in range(3):
                if num == self.board[row][column]:
                    return [row, column]


    def __getHeuristic(self):
        pos0 =  self.__getPos(0)
        pos1 =  self.__getPos(1)
        pos2 =  self.__getPos(2)
        pos3 =  self.__getPos(3)
        pos4 =  self.__getPos(4)
        pos5 =  self.__getPos(5)
        pos6 =  self.__getPos(6)
        pos7 =  self.__getPos(7)
        pos8 =  self.__getPos(8)

        zero = abs(0 - pos0[0]) + abs(0 - pos0[1])
        one = abs(0 - pos1[0]) + abs(1 - pos1[1])
        two = abs(0 - pos2[0]) + abs(2 - pos2[1])
        three = abs(1 - pos3[0]) + abs(0 - pos3[1])
        four = abs(1 - pos4[0]) + abs(1 - pos4[1])
        five = abs(1 - pos5[0]) + abs(2 - pos5[1])
        six = abs(2 - pos6[0]) + abs(0 - pos6[1])
        seven = abs(2 - pos7[0]) + abs(1 - pos7[1])
        eight =  abs(2 - pos8[0]) + abs(2 - pos8[1])

        return zero + one + two + three + four + five + six + seven + eight


    def __postProcess(self, dirn):
        """postProcess: Correctly updates the current node to accurately reflect it state of the board based on
            the direction passed through the functions parameter """

        y = self.posn[0]
        x = self.posn[1]

        if 'Left' == dirn:
            self.board[y][x] = self.board[y][x - 1]
            self.board[y][x - 1] = 0
            self.posn[1] = x - 1
        elif 'Right' == dirn:
            self.board[y][x] = self.board[y][x + 1]
            self.board[y][x + 1] = 0
            self.posn[1] = x + 1
        elif 'Up' == dirn:
            self.board[y][x] = self.board[y - 1][x]
            self.board[y - 1][x] = 0
            self.posn[0] = y - 1
        elif 'Down' == dirn:
            self.board[y][x] = self.board[y + 1][x]
            self.board[y + 1][x] = 0
            self.posn[0] = y + 1

        self.path.append(dirn)