基于广度优先搜索计算词错误率的代码无法运行，求排查

我编写了一段用广度优先搜索（Breadth First Search, BFS）计算词错误率（Word Error Rate, WER）的代码，但无法正常运行。这是机器学习入门课程中搜索算法的作业，课程未教授数据结构、面向对象编程等基础知识，我自行调试许久仍找不到问题所在。

以下是我的代码：

class FIFOQueue :
   def __init__(self) -> None:
       self.__queue = []

   def append(self,item_in) :
       self.__queue.append(item_in)
   
   def extend(self,old_queue):
       self.__queue.extend(old_queue) 

   def pop(self):
       return self.__queue.pop(0)  # 返回节点

   def is_empty(self) :
       return self.__queue ==[]

class TreeNode: 
   def __init__(self,state, step = 0 ,parent=None) -> None:
       self.state = tuple(state)
       self.step = step
       self.parent = parent
       
   def get_state(self):
       return self.state

   def get_parent(self) :
       return self.parent


class RNode(TreeNode) :
   def __init__(self, state, step = 0, parent=None) -> None:
       super().__init__(state, step, parent)
   
   def expand(self,rp) :
       child_list = []
       for new_state in rp.adjacent_states(self.state, self.step) :
           child_list.append(RNode(new_state, self.step+1, self))
       # 修正：将打印移到外层循环外，避免重复打印
       for i in child_list :
           print(i.get_state())
       return child_list 

class RoutingProb :  # 修改
   def __init__(self,initial,destination) -> None:
       self.initial = initial
       self.destination = destination

       des = ''
       for i in destination :
           des += i

       self.des_str = des

   def is_destination(self,state) :
       check_state = ''
       for i in state : 
           if i is None :
               continue
           else :
               check_state += i
       return self.des_str == check_state

   def adjacent_states(self,state, step) : 
       return self.add_action(list(state), step, self.destination)
           
   def add_action(self, state_li, step, des) :
       print(step)
       print(state_li)
       # 修正：处理step超出当前state_li长度的情况
       if step >= len(state_li):
           # 仅执行插入操作
           state_li.insert(step, des[step])
           return [state_li]
       if state_li[step] == des[step]:
           print('pass')
           print(state_li)
           return [state_li]

       if len(state_li) > len(des) : # 删除或替换
           
           state_li2 = state_li[:]
           state_li[step] =  None  # 删除
           state_li2[step] = des[step] # 替换
           # print('pass2')
           return [state_li, state_li2]

       elif len(state_li) < len(des) : # 插入或替换
           state_li2 = state_li[:]
           state_li.insert(step, des[step]) # 插入
           state_li2[step] = des[step] # 替换
           # print('pass3')
           return [state_li, state_li2]

       else : # 长度相等，仅替换
           #print('pass4')
           state_li[step] = des[step]
           return [state_li]
    
   
def breadth_first_search(prob):
   fringe = FIFOQueue()
   fringe.append(RNode(prob.initial))

   reached ={}  # 修正：拼写错误reaeched改为reached
   while not fringe.is_empty():
       node = fringe.pop()
       # print(node.state)
       if prob.is_destination(node.state) :
           print('找到目标节点')
           return node

       if node.state not in reached : 
           reached[node.state] = node
           print(reached)
           fringe.extend(node.expand(prob))
           print('已扩展节点')

def P5_wer(ref,test):
   ref_list = [i for i in ref]
   test_list = [i for i in test]

   rProb = RoutingProb(test_list,ref_list) # 修正：拼写错误rPorb改为rProb
   leave_node = breadth_first_search(rProb)
   # print('leave=',leave_node)

   # 修正：处理未找到路径的情况
   if leave_node is None:
       return 0, len(ref_list)

   x, sol_path = leave_node, [leave_node]
   # print('x=',x.get_state)
   while x.get_parent() is not None :
       sol_path.append(x.get_parent())
       x = x.get_parent()
   
   # 修正：补充WER计算逻辑并返回结果
   wer = len(sol_path) - 1  # 路径长度减1为操作步数（错误数）
   n = len(ref_list)
   return wer, n
    
if __name__ == '__main__':
   wer, n = P5_wer("grit", "greet")
   print("wer = {}, n = {}".format(wer, n))

关键问题修复说明 #

• 拼写错误修正：修正了reaeched、rPorb等拼写错误，避免字典查找和类实例化失败
• 边界情况处理：在add_action中补充了step超出当前状态列表长度的判断，防止索引越界
• 返回值补充：原P5_wer函数未返回计算结果，补充后主函数可正常接收wer和n
• 逻辑优化：调整RNode.expand中的打印位置，避免重复打印子节点状态

内容的提问来源于stack exchange，提问作者Kwankhao