递归寻径

Question

我正在做一个练习，给定两点之间的一组连接（即12是1和2等之间的连接）。我决定递归地处理这个方法，以便让它系统地检查每一条路径，并在找到一条到达每个节点并以一条路径开始和结束的路径时返回。你知道吗

然而，在调试时，似乎当我将adjMatrix进一步传递到递归中时，它也在编辑上层，并导致它在返回树时不再进一步搜索。我想当我设置newMatrix = adjMatrix时，它会有一些变化，但我不太确定。你知道吗

def checkio(teleports_string):
    #return any route from 1 to 1 over all points
    firstnode, secondnode, size = 0, 0, 8

    #Makes the adjacency matrix
    adjMatrix = [[0 for i in range(size)] for j in range(size)]

    for x in teleports_string:
        #Assigns Variables
        if firstnode == 0 and x != ",":
            #print("Node1:" + x)
            firstnode = x
        elif secondnode == 0 and x != ",":
            #print("Node2:" + x)
            secondnode = x
        #Marks connections
        if firstnode != 0 and secondnode != 0:
            adjMatrix[int(firstnode) - 1][int(secondnode) - 1] = 1
            adjMatrix[int(secondnode) - 1][int(firstnode) - 1] = 1
            firstnode, secondnode = 0, 0
    print(adjMatrix)

    return findPath(adjMatrix, 1, "1")


def findPath(adjMatrix, currentnode, currentpath):
    if isFinished(currentpath):
        return currentpath

    for x in range(0, 8):
        if adjMatrix[currentnode - 1][x] == 1:
            print(currentpath + "+" + str(x+1))
            newMatrix = adjMatrix
            newMatrix[currentnode - 1][x] = 0
            newMatrix[x][currentnode - 1] = 0
            temp = currentpath
            temp += str(x+1)
            newpath = findPath(newMatrix, x+1,temp)
            print(newpath)
            if isFinished(newpath):
                 print ("Returning: " + newpath)
                 return newpath
    return ""


def isFinished(currentpath):
    #Checks if node 1 is hit at least twice and each other node is hit at least once
    if currentpath == "":
        return False

    for i in range(1, 9):
        if i == 1 and currentpath.count(str(i)) < 2:
            return False
        elif currentpath.count(str(i)) < 1:
            return False
    #Checks if it starts and ends with 1
    if not currentpath.startswith(str(1)) or not currentpath.endswith(str(1)):
        return False
    return True

#This part is using only for self-testing
if __name__ == "__main__":
    def check_solution(func, teleports_str):
        route = func(teleports_str)
        teleports_map = [tuple(sorted([int(x), int(y)])) for x, y in teleports_str.split(",")]
        if route[0] != '1' or route[-1] != '1':
            print("The path must start and end at 1")
            return False
        ch_route = route[0]
        for i in range(len(route) - 1):
            teleport = tuple(sorted([int(route[i]), int(route[i + 1])]))
            if not teleport in teleports_map:
                print("No way from {0} to {1}".format(route[i], route[i + 1]))
                return False
            teleports_map.remove(teleport)
            ch_route += route[i + 1]
        for s in range(1, 9):
            if not str(s) in ch_route:
                print("You forgot about {0}".format(s))
                return False
        return True

    assert check_solution(checkio, "13,14,23,25,34,35,47,56,58,76,68"), "Fourth"

Answer 1

线路

newMatrix = adjMatrix

只会创建对列表的另一个引用。您需要实际创建一个新的列表对象。由于这是一个矩阵，请对内容执行此操作：

newMatrix = [row[:] for row in adjMatrix]

这将创建嵌套列表副本的新列表。你知道吗