因此,我试图通过在 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
