【转】A*算法解决八数码问题

from utils import (  PriorityQueue)
import copy
 
infinity = float(‘inf‘)
 
def best_first_graph_search(problem, f):
    #定义初始节点
    node = Node(problem.initial)
    node.fvalue=f(node)
    #如果是最终结果，返回节点
    if problem.goal_test(node):
        return node
    #frotier是一个顺序队列，从小到大排列，排列比较通过f函数
    #如果order是min，最小的先出队
    frontier = PriorityQueue(min, f)
    #加入节点
    frontier.append(node)
    #print(node.fvalue)
    #展开的节点
    explored = set()
    #当栈不为空
    while frontier:
        #节点出队
        node = frontier.pop()
        #print("pop")
        #node.state.display()
        #print(node.fvalue)
        # 如果是最终结果，返回节点
        if problem.goal_test(node):
            return node
        #加入展开的节点
        explored.add(node)
        #对于出栈的子节点
        for child in node.expand(problem):
            #如果节点没有展开，并且子节点没在队中
            if child not in explored and child not in frontier:
                #子节点入队
                frontier.append(child)
                #print(child.fvalue)
                #如果子节点在队中
            elif child in frontier:
                incumbent = frontier[child]
                #如果子节点的f值小于队中节点的f值
                if f(child) ".format(self.state.board)
 
    def __lt__(self, node):
        #