我尝试在8数码问题上实现了一个最佳优先搜索算法。但是无论我使用什么矩阵，都得到与A*代码相同的路径。另外，有人能帮我打印出每个矩阵下的启发式值吗？我在输出中只得到了“1”。
最佳优先搜索代码-
from copy import deepcopyfrom collections import dequeclass Node: def __init__(self, state=None, parent=None, cost=0, depth=0, children=[]): self.state = state self.parent = parent self.cost = cost self.depth = depth self.children = children def is_goal(self, goal_state): return is_goal_state(self.state, goal_state) def expand(self): new_states = operator(self.state) self.children = [] for state in new_states: self.children.append(Node(state, self, self.cost + 1, self.depth + 1)) def parents(self): current_node = self while current_node.parent: yield current_node.parent current_node = current_node.parent def gn(self): costs = self.cost for parent in self.parents(): costs += parent.cost return costsdef is_goal_state(state, goal_state): for i in range(len(state)): for j in range(len(state)): if state[i][j] != goal_state[i][j]: return False return Truedef operator(state): states = [] zero_i = None zero_j = None for i in range(len(state)): for j in range(len(state)): if state[i][j] == 0: zero_i = i zero_j = j break def add_swap(i, j): new_state = deepcopy(state) new_state[i][j], new_state[zero_i][zero_j] = new_state[zero_i][zero_j], new_state[i][j] states.append(new_state) if zero_i != 0: add_swap(zero_i - 1, zero_j) if zero_j != 0: add_swap(zero_i, zero_j - 1) if zero_i != len(state) - 1: add_swap(zero_i + 1, zero_j) if zero_j != len(state) - 1: add_swap(zero_i, zero_j + 1) return statesR = int(input("Enter the number of rows:")) C = int(input("Enter the number of columns:")) # Initialize matrix inital = [] print("Enter the entries rowwise:") # For user input for i in range(R): # A for loop for row entries a =[] for j in range(C): # A for loop for column entries a.append(int(input())) inital.append(a) # For printing the matrix for i in range(R): for j in range(C): print(inital[i][j], end = " ") print() R = int(input("Enter the number of rows:")) C = int(input("Enter the number of columns:")) # Initialize matrix final = [] print("Enter the entries rowwise:") # For user input for i in range(R): # A for loop for row entries a =[] for j in range(C): # A for loop for column entries a.append(int(input())) final.append(a) # For printing the matrix for i in range(R): for j in range(C): print(final[i][j], end = " ") print() def search(state, goal_state): def gn(node): return node.gn() tiles_places = [] for i in range(len(goal_state)): for j in range(len(goal_state)): heapq.heappush(tiles_places, (goal_state[i][j], (i, j))) def hn(node): cost = 0 for i in range(len(node.state)): for j in range(len(node.state)): tile_i, tile_j = tiles_places[node.state[i][j]][1] if i != tile_i or j != tile_j: cost += abs(tile_i - i) + abs(tile_j - j) return cost def fn(node): return 1 return bfs_search(state, goal_state, fn)def bfs_search(state, goal_state, fn): queue = [] entrance = 0 node = Node(state) while not node.is_goal(goal_state): node.expand() for child in node.children: #print(child) #print(fn(child)) queue_item = (fn(child), entrance, child) heapq.heappush(queue, queue_item) entrance += 1 node = heapq.heappop(queue)[2] output = [] output.append(node.state) for parent in node.parents(): output.append(parent.state) output.reverse() return (output,fn)l , n = search(inital,final)for i in l: for j in i: print(j) print(n(Node(i))) print("\n")这是输出结果-
Enter the number of columns:3Enter the entries rowwise:2831647052 8 3 1 6 4 7 0 5 Enter the number of rows:3Enter the number of columns:3Enter the entries rowwise:8032641758 0 3 2 6 4 1 7 5 [2, 8, 3][1, 6, 4][7, 0, 5]1[2, 8, 3][1, 6, 4][0, 7, 5]1[2, 8, 3][0, 6, 4][1, 7, 5]1[0, 8, 3][2, 6, 4][1, 7, 5]1[8, 0, 3][2, 6, 4][1, 7, 5]1虽然我达到了正确的目标节点并显示了所有中间步骤，但我无法理解它是基于什么启发式考虑的。
回答：
一般来说，A*和贪婪最佳优先搜索不保证得到相同的解。如果使用可采纳的启发式，A*总是会找到最优解，而这对于最佳优先搜索来说并不成立。
有关A*和最佳优先搜索会给出不同结果的示例，请参见这个回答。
