编写代码使用A* 算法求解八数码问题，其中估价函数f(x)=g(x)+h(x)，其中g(x)为从初始状态到当前状态的层数，g(s)=0. h(x)为启发式函数。 要求：求出以下三种启发式函数对应的求解效率，其中， 求解效率 = 最佳路径节点数/遍历路径节点数 三总启发式函数分别为： 1）h(x)=0 2）h(x) = 错误位置和 3）h(x) = 错误位置曼哈顿距离和

代码如下：

import heapq

class EightPuzzle:
    goal_state = [[1,2,3],
                  [4,5,6],
                  [7,8,0]]

    def __init__(self, start_state):
        self.start_state = start_state
        self.g = 0
        self.h = self.calculate_h()
        self.f = self.g + self.h

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

    def __eq__(self, other):
        return self.start_state == other.start_state

    def generate_children(self):
        children = []
        zero_i = -1
        zero_j = -1
        for i in range(3):
            for j in range(3):
                if self.start_state[i][j] == 0:
                    zero_i = i
                    zero_j = j
                    break
        if zero_i > 0:
            child = EightPuzzle(self.copy_state())
            child.start_state[zero_i][zero_j] = child.start_state[zero_i-1][zero_j]
            child.start_state[zero_i-1][zero_j] = 0
            child.g = self.g+1
            child.h = child.calculate_h()
            child.f = child.g + child.h
            children.append(child)
        if zero_i < 2:
            child = EightPuzzle(self.copy_state())
            child.start_state[zero_i][zero_j] = child.start_state[zero_i+1][zero_j]
            child.start_state[zero_i+1][zero_j] = 0
            child.g = self.g+1
            child.h = child.calculate_h()
            child.f = child.g + child.h
            children.append(child)
        if zero_j > 0:
            child = EightPuzzle(self.copy_state())
            child.start_state[zero_i][zero_j] = child.start_state[zero_i][zero_j-1]
            child.start_state[zero_i][zero_j-1] = 0
            child.g = self.g+1
            child.h = child.calculate_h()
            child.f = child.g + child.h
            children.append(child)
        if zero_j < 2:
            child = EightPuzzle(self.copy_state())
            child.start_state[zero_i][zero_j] = child.start_state[zero_i][zero_j+1]
            child.start_state[zero_i][zero_j+1] = 0
            child.g = self.g+1
            child.h = child.calculate_h()
            child.f = child.g + child.h
            children.append(child)
        return children

    def calculate_h(self):
        h = 0
        if h == 1:
            for i in range(3):
                for j in range(3):
                    if self.start_state[i][j] != EightPuzzle.goal_state[i][j]:
                        h += 1
        elif h == 2:
            for i in range(3):
                for j in range(3):
                    if self.start_state[i][j] != EightPuzzle.goal_state[i][j] and self.start_state[i][j] != 0:
                        h += 1
        elif h == 3:
            for i in range(3):
                for j in range(3):
                    if self.start_state[i][j] != EightPuzzle.goal_state[i][j] and self.start_state[i][j] != 0:
                        number = self.start_state[i][j]
                        row = (number - 1) // 3
                        col = (number - 1) % 3
                        h += abs(i - row) + abs(j - col)
        return h

    def copy_state(self):
        new_state = []
        for i in range(3):
            new_row = []
            for j in range(3):
                new_row.append(self.start_state[i][j])
            new_state.append(new_row)
        return new_state

    def print_state(self):
        for i in range(3):
            for j in range(3):
                print(self.start_state[i][j], end=" ")
            print()

def a_star(start_state, h_type):
    closed_set = set()
    open_heap = [EightPuzzle(start_state)]
    while open_heap:
        current = heapq.heappop(open_heap)
        if current.start_state == EightPuzzle.goal_state:
            return current
        for child in current.generate_children():
            if child in closed_set:
                continue
            heapq.heappush(open_heap, child)
        closed_set.add(current)
    return None

start_state = [[1, 2, 3], [5, 8, 7], [6, 4, 0]]
h_types = {1: 'h(x) = 0', 2: 'h(x) = misplaced tiles', 3: 'h(x) = Manhattan distance'}
for i in range(1, 4):
    print('h_type:', h_types[i])
    result = a_star(start_state, i)
    if result is not None:
        path = []
        current = result
        while current:
            path.append(current)
            current = current.parent
        path.reverse()
        for p in path:
            p.print_state()
            print()
        print('Steps:', len(path)-1)
        print('Nodes expanded:', len(path))
        print('Efficiency:', len(path)-1, '/', len(closed_set))
    else:
        print("Cannot be solved")