python - 我一直在用我自己的例子在 python 中练习星搜索算法，但是我的算法的答案是错误的

Question

树节点与启发式一起显示在图像中：https : //imgur.com/Fa9MgP3。

def astaralgo():
   global tree, heuristic      
   openedlist = [['A', 390]]
   closedlist = []          

   #Finding the first visited node and the rest
   while True:
       fn =  [i[1] for i in openedlist]             
       chosen_index = fn.index(min(fn))             
       node = openedlist[chosen_index][0]         
       closedlist.append(openedlist[chosen_index])  
       del openedlist[chosen_index]                 
       if closedlist[-1][0] == 'Z':                
           break
       
       for item in tree[node]:
           if item[0] in [closedlist_item[0] for closedlist_item in closedlist]:  
               continue                                 
           cost.update({item[0]: cost[node] + item[1]}) 
           fn_node = cost[node] + heuristic[item[0]] + item[1] 
           temp = [item[0], fn_node] 
           openedlist.append(temp)
    
   #Optimal path search 
   trace_node = 'Z'
   optimal_path = ['Z']    
   for i in range(len(closedlist)-2, -1, -1):    
       check_node = closedlist[i][0]            
       if trace_node in [children[0] for children in tree[check_node]]: 
           children_costs = [temp[1] for temp in tree[check_node]]
           children_nodes = [temp[0] for temp in tree[check_node]]
           
           if cost[check_node] + children_costs[children_nodes.index(trace_node)] == cost[trace_node]: 
               optimal_path.append(check_node)          
               trace_node = check_node                  
  
   optimal_path.reverse()       
   return closedlist, optimal_path  

这是它的代码。一切正常，但答案是错误的。输出如下

Nodes visited with the optimal path: [['A', 390], ['D', 390], ['C', 396], ['F', 405], ['G', 414], ['B', 435], ['F', 448], ['J', 453], ['Z', 447]]
Chosen Optimal path from A to Z: ['A', 'D', 'G', 'J', 'Z']

但这不是最佳路径。

标签： pythonalgorithmsearcha-star