Функции изменяют значения в списке, хотя список не передается в функции

Question

Я пытаюсь реализовать алгоритм, подобный поисковой ширине IA, чтобы решить проблему Water Jugs, но я столкнулся с этой проблемой:

Каждый раз, когда я добавляю новый элемент в массив, он меняет все элементы в массиве, чтобы он был похож на него.

Другими словами...

Массив "frontier" изменяет все элементы внутри него между каждым вызовом функций "jug".

Может ли кто-нибудь поделиться своим пониманием этого кода?

(Я больше беспокоился о реализации логики, поэтому она не оптимизирована)

Код:

J1SIZE = 3
J2SIZE = 4

frontier = []
explored = []


def IsEmpty(array):
    result = False
    if len(array) == 0:
        result = True
    return result


#Fill up a jug
def fillJug(tempNode, jug):
    copyNode = tempNode
    copyNode = copyNode
    if jug == 1:
        copyNode[0] = J1SIZE
    elif jug == 2:
        copyNode[1] = J2SIZE
    print(copyNode)
    return copyNode

#Empty a jug
def emptyJug(tempNode, jug):
    copyNode = tempNode
    if jug == 1:
        copyNode[0] = 0
    elif jug == 2:
        copyNode[1] = 0
    print(copyNode)
    return copyNode

#Pass the content of a jug to another
def passJug(tempNode, jug):
    copyNode = tempNode
    if jug == 1:
        copyNode[1] = copyNode.j1
        copyNode[0] = 0
        if copyNode[1] > J2SIZE:
            copyNode[1] = J2SIZE
    elif jug == 2:
        copyNode[0] = copyNode[1]
        copyNode[1] = 0
        if copyNode[0] > J1SIZE:
            copyNode[0] = J1SIZE
    print(copyNode)
    return copyNode

#Check if solution was found
def goalTest(goalNode,currentNode):
    result = False
    if goalNode == currentNode:
        result = True
    return result

def BFS(start,end,frontier,explored):

    start_node = start
    frontier = [start_node] + frontier

    if goalTest(end,(frontier[0])):
        print('Solution:', frontier[0])
        exit()

    #Loop start
    while IsEmpty(frontier) == False:

        tempNode = frontier.pop(0)

        #Generate nodes (states)
        if tempNode[0] < J1SIZE:
            newNode = fillJug(tempNode, 1)
            if newNode not in explored:
                frontier = [newNode] + frontier
                print('Frontier1: ', frontier)

        if tempNode[1] < J2SIZE:
            newNode = fillJug(tempNode, 2)
            if newNode not in explored:
                frontier = [newNode] + frontier
                print('Frontier2: ', frontier)

        if tempNode[0] == J1SIZE:
            newNode = emptyJug(tempNode, 1)
            if newNode not in explored:
                frontier = [newNode] + frontier
                print('Frontier3: ', frontier)

        if tempNode[1] == J2SIZE:
            newNode = emptyJug(tempNode, 2)
            if newNode not in explored:
                frontier = [newNode] + frontier
                print('Frontier4: ', frontier)

        if (tempNode[0] > 0) and (tempNode[1] < J2SIZE):
            newNode = passJug(tempNode, 1)
            if newNode not in explored:
                frontier = [newNode] + frontier
                print('Frontier5: ', frontier)

        if (tempNode[1] > 0) and (tempNode[0] < J1SIZE):
            new_node = passJug(tempNode, 2)
            if new_node not in explored:
                frontier = [new_node] + frontier
                print('Frontier6: ', frontier)

        print('Frontier: ', frontier)
        print('Explored: ', explored)

        for node in frontier:
            if goalTest(end, node):
                print('Solution:', frontier[0])
                exit()
            if node not in explored:
                explored = [node] + explored

BFS([0,0],[0,2],frontier,explored)

Фиксированный код:

http://codepaste.net/auun4u

Answer 1

Я сделал меньший пример кода, который воспроизводит вашу ошибку:

J1SIZE = 3
J2SIZE = 4


def fillJug(tempNode, jug):
    copyNode = tempNode
    copyNode = copyNode
    if jug == 1:
        copyNode[0] = J1SIZE
    elif jug == 2:
        copyNode[1] = J2SIZE
    return copyNode


frontier = [[0, 0]]
tempNode = frontier.pop(0)

newNode = fillJug(tempNode, 1)
frontier = [newNode] + frontier  # (1)

newNode = fillJug(tempNode, 2)  # (2)
frontier = [newNode] + frontier

Проблема в том, что в строке, которую я отметил (1) Вы устанавливаете newNode, который относится к тому же объекту, что и tempNode быть первым пунктом в frontier, Затем в строке я отметил (2) вы меняете tempNode - внутри fillJug, Таким образом, значение в frontier изменения. В частности, у вас есть copyNode ссылаются на тот же объект, что и tempNode, а затем вы меняете данные, на которые copyNode (а также tempNode) обратитесь.

Вы должны переопределить copyNode как

copyNode = tempNode[:]

Это приведет к copyNode а также tempNode ссылаться на разные объекты в памяти (с одинаковыми значениями). (Другой вариант - установить copyNode в copy.copy(tempNode) после импорта copy.)

Итак, новый fillJug было бы

def fillJug(tempNode, jug):
    copyNode = tempNode[:]
    if jug == 1:
        copyNode[0] = J1SIZE
    elif jug == 2:
        copyNode[1] = J2SIZE
    return copyNode

Это же исправление относится и к другим Jug функции.