目标是创建所有路径,其中每个节点只访问一次。1表示可行路由,0表示不存在路由。你知道吗
示例:
假设我有一个矩阵
1 2 3 4 5 6 7
1 [0 1 0 1 0 0 1]
2 [1 0 1 0 0 1 0]
3 [0 1 0 0 1 0 0]
4 [1 0 0 0 0 0 0]
5 [0 0 1 0 0 0 0]
6 [0 1 0 0 0 0 1]
7 [1 0 0 0 0 1 0]
为了这个例子,让我们从4开始
所有可能的途径是:(有点像旅行推销员问题)
[4,1,2,3,5]
[4,1,2,6,7]
[4,1,7,6,2,3,5]
我将矩阵存储为二维数组:
M0 =[[0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 1, 0]]
下面是一些我正在尝试的东西,它不起作用,因为它没有重置回它分支的最前面的坐标。你知道吗
我也认为这可能不是最好的方法,我试图实现贪婪方法的一些变体。一定有更好的方法来修复这个代码。你知道吗
path=[]
allPaths=[]
visited=[]
branchAt=[]
def route():
tempMatrix = genMat() #set this to the above example matrix if you trying to run this code
column = 3 #Starting with a static column for now
#while(column+1 not in path):
for counter in range(0,20): #Static loop as well
path.append(column+1)
delMat(tempMatrix[column]) #Sets all the elements to 0 in that row of the tempMatrix so same path isn't visited twice in subsequent interations (ie when in another column)
oneCount=0 #check if path can branch out in the current column (aka more than one 1's)
for row in range(0,len(matrix)):
if(tempMatrix[row][column]==1):
oneCount+=1
for row in range(0,len(matrix)):
coOrds=([column+1,row+1])
if(tempMatrix[row][column]==1):
#if (coOrds) not in visited and oneCount>1:
if oneCount>1 and coOrds in visited:
continue
else:
if(oneCount>1):
visited.append(coOrds)
if len(branchAt)<1:
branchAt.append(coOrds)
column=row
delMat(tempMatrix[row])
break
# else:
# if(oneCount>1):
# continue
# else:
# continue
else:
if(row==len(matrix)-1):
print("Final Path: ",path)
allPaths.append(tuple(path))
bran.clear()
break
print("allPaths: ", allPaths)
print("Visited: ", visited)
使用来自https://www.geeksforgeeks.org/find-paths-given-source-destination/的算法
修改路径打印以使用节点编号(即从1开始而不是从0开始)
输出
相关问题 更多 >
编程相关推荐