如何在python中跟踪二进制矩阵中1的所有唯一路径?

2024-03-28 14:02:30 发布

您现在位置:Python中文网/ 问答频道 /正文

目标是创建所有路径,其中每个节点只访问一次。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]

Crappy drawing of the path

我将矩阵存储为二维数组:

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)

Tags: thepathinforlenifcolumncoords
1条回答
网友
1楼 · 发布于 2024-03-28 14:02:30

使用来自https://www.geeksforgeeks.org/find-paths-given-source-destination/的算法

修改路径打印以使用节点编号(即从1开始而不是从0开始)

from collections import defaultdict 

#This class represents a directed graph  
# using adjacency list representation 
class Graph: 

    def __init__(self,vertices): 
        #No. of vertices 
        self.V= vertices  

        # default dictionary to store graph 
        self.graph = defaultdict(list)  

    # function to add an edge to graph 
    def addEdge(self,u,v): 
        self.graph[u].append(v) 

    '''A recursive function to print all paths from 'u' to 'd'. 
    visited[] keeps track of vertices in current path. 
    path[] stores actual vertices and path_index is current 
    index in path[]'''
    def printAllPathsUtil(self, u, d, visited, path): 

        # Mark the current node as visited and store in path 
        visited[u]= True
        path.append(u+1)  # add 1 so print output starts at 1

        # If current vertex is same as destination, then print 
        # current path[] 
        if u ==d: 
            print (path)
        else: 
            # If current vertex is not destination 
            #Recur for all the vertices adjacent to this vertex 
            for i in self.graph[u]: 
                if visited[i]==False: 
                    self.printAllPathsUtil(i, d, visited, path) 

        # Remove current vertex from path[] and mark it as unvisited 
        path.pop() 
        visited[u]= False


    # Prints all paths from 's' to 'd' 
    def printAllPaths(self,s, d): 

        # Mark all the vertices as not visited 
        visited =[False]*(self.V) 

        # Create an array to store paths 
        path = [] 

        # Call the recursive helper function to print all paths 
        self.printAllPathsUtil(s, d,visited, path) 

def generate_paths(A):
  g = Graph(len(A))
# We loop over all row, column combinations and add edge
# if there is a connection between the two nodes
  for row in range(len(A)):
    for column in range(len(A[0])):
      if A[row][column] == 1:
        g.addEdge(row, column)

  for row in range(len(A)):
    # show row+1, so row numbering prints starting with 1
    print (f"Following are all different paths starting at {row+1}")
    for column in range(row+1, len(A[0])):
        g.printAllPaths(row, column)


A =[[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]]

generate_paths(A)

输出

Following are all different paths starting at 1
[1, 2]
[1, 7, 6, 2]
[1, 2, 3]
[1, 7, 6, 2, 3]
[1, 4]
[1, 2, 3, 5]
[1, 7, 6, 2, 3, 5]
[1, 2, 6]
[1, 7, 6]
[1, 2, 6, 7]
[1, 7]
Following are all different paths starting at 2
[2, 3]
[2, 1, 4]
[2, 6, 7, 1, 4]
[2, 3, 5]
[2, 1, 7, 6]
[2, 6]
[2, 1, 7]
[2, 6, 7]
Following are all different paths starting at 3
[3, 2, 1, 4]
[3, 2, 6, 7, 1, 4]
[3, 5]
[3, 2, 1, 7, 6]
[3, 2, 6]
[3, 2, 1, 7]
[3, 2, 6, 7]
Following are all different paths starting at 4
[4, 1, 2, 3, 5]
[4, 1, 7, 6, 2, 3, 5]
[4, 1, 2, 6]
[4, 1, 7, 6]
[4, 1, 2, 6, 7]
[4, 1, 7]
Following are all different paths starting at 5
[5, 3, 2, 1, 7, 6]
[5, 3, 2, 6]
[5, 3, 2, 1, 7]
[5, 3, 2, 6, 7]
Following are all different paths starting at 6
[6, 2, 1, 7]
[6, 7]
Following are all different paths starting at 7

相关问题 更多 >