Skip to main content
 首页 » 编程设计

python之如果达到基本情况,为什么这个递归函数永远不会结束

2025年04月02日18mfrbuaa

因此,我试图通过在 Python 上实现 Ullmann 算法来解决子图同构问题。它说当找到兼容矩阵时停止算法,但我的代码继续打印找到的其余矩阵,即使它到达基本情况。我做错了什么?

recurse(used_columns, cur_row, G, P, M) 
    if cur_row = num_rows(M) 
        if  M is an isomorphism: 
            output yes and end the algorithm 
 
    for all unused columns c 
        set column c in M' to 1 and other columns to 0 
        mark c as used 
        recurse(used_column, cur_row+1, G, P, M') 
        mark c as unused 
 
    output no  

我是这样写的:

def permute(m0,row,h,g): 
    if(row==len(m0)-1): 
        n=0 
        for i in range(len(m0[0])): 
            for j in range(len(m0)): 
                n+=m0[j][i] 
            if(n>1): 
                return 
            n=0 
        res=[[sum(a*b for a,b in zip(m0_row,h_col)) for h_col in zip(*h)] for m0_row in m0] 
        resTr=[[res[j][i] for j in range(len(res))] for i in range(len(res[0]))] 
        arr=[[sum(a*b for a,b in zip(m0_row,resTr_col)) for resTr_col in zip(*resTr)] for m0_row in m0] 
        for row in arr: 
            print(row) 
        if(g==arr): 
            print("YES!") 
            return 
    for n in range(len(m0[0])): 
        m0[row][n]=0 
    for n in range(len(m0[0])): 
        m0[row][n]=1 #mark c as used 
        permute(m0,row+1,h,g)       
        m0[row][n]=0 #mark c as unused 
    print("No") 
    return 

这是输出:

[0, 0, 1] 
 
[0, 0, 1] 
 
[1, 1, 0] 
 
YES! 
 
[0, 0, 1] 
 
[0, 0, 1] 
 
[1, 1, 0] 
 
YES! 
 
No 
 
No 
 
[0, 0, 1] 
 
[0, 0, 1] 
 
[1, 1, 0] 
 
YES! 
 
[0, 0, 1] 
 
[0, 0, 1] 
 
[1, 1, 0] 
 
YES! 
 
No 
 
[0, 0, 1] 
 
[0, 0, 1] 
 
[1, 1, 0] 
 
YES! 
 
[0, 0, 1] 
 
[0, 0, 1] 
 
[1, 1, 0] 
 
YES! 
 
No 
 
No 

我只想打印第一次出现并实际停止,并在没有找到相同的矩阵时打印“否”。谁能帮忙?

请您参考如下方法:

您没有任何退出条件。 Python 不关心你是否打印了“YES!”所以利用返回值变得有必要。当算法完成时,您应该返回 True,否则返回 False。此外,您必须在函数调用自身时(您的最终 for 循环)检查此值并传递该 True 值,以便它立即停止:

def permute(m0,row,h,g): 
    if(row==len(m0)-1): 
        n=0 
        for i in range(len(m0[0])): 
            for j in range(len(m0)): 
                n+=m0[j][i] 
            if(n>1): 
                return False 
            n=0 
        res=[[sum(a*b for a,b in zip(m0_row,h_col)) for h_col in zip(*h)] for m0_row in m0] 
        resTr=[[res[j][i] for j in range(len(res))] for i in range(len(res[0]))] 
        arr=[[sum(a*b for a,b in zip(m0_row,resTr_col)) for resTr_col in zip(*resTr)] for m0_row in m0] 
        for row in arr: 
            print(row) 
        if(g==arr): 
            print("YES!") 
            return True 
    for n in range(len(m0[0])): 
        m0[row][n]=0 
    for n in range(len(m0[0])): 
        m0[row][n]=1 #mark c as used 
        if permute(m0,row+1,h,g): #exit when finished 
            return True      
        m0[row][n]=0 #mark c as unused 
    print("No") 
    return False 

或者,如果您想稍后在程序中实际使用输出;您可以返回该变量而不是 True,向下传递值,否则返回 None。变化很小,新的最终 for 循环将变成这样:

for n in range(len(m0[0])): 
    m0[row][n]=1 #mark c as used 
    out=permute(m0,row+1,h,g) 
    if out: #exit when finished 
        return out 
    m0[row][n]=0 #mark c as unused