Это вопрос понимания Python списка мутаций. Я решил эту проблему поиска в глубину и получил правильные результаты. Затем я получил отзыв о том, что, по моему мнению, не должно работать, но это работает.
В принципе, если я использую path [0] вместо current_path (переключая строки в парах вне и без комментариев), результаты совпадают. Я пытаюсь понять, почему это работает. Я понимаю, что список внутри пути списка, то есть path [0], не является мутированным. Однако путь к списку должен быть изменен, когда я назначаю другой список 0-му индексу пути. И все же, он работает просто отлично.
Ниже приведен код, я оставил строку документации для дальнейших разъяснений. В конце я вставил код, с которым я играл, чтобы лучше понять мутацию списка, но это не помогло мне. Может кто-нибудь объяснить это?
# Problem 3b: Implement get_best_path
def get_best_path(digraph, start, end, path, max_dist_outdoors, best_dist,
best_path):
"""
Finds the shortest path between buildings subject to constraints.
digraph: Digraph instance
The graph on which to carry out the search
start: string, Building number at which to start
end: string, Building number at which to end
path: list composed of [[list of strings], int, int]
Represents the current path of nodes being traversed. Contains
a list of node names, total distance traveled, and total
distance outdoors.
max_dist_outdoors: int
Maximum distance spent outdoors on a path
best_dist: int
The smallest distance between the original start and end node
for the initial problem that you are trying to solve
best_path: list of strings
The shortest path found so far between the original start
and end node.
Returns:
A tuple with the shortest-path from start to end, represented by
a list of building numbers (in strings), [n_1, n_2, ..., n_k],
where there exists an edge from n_i to n_(i+1) in digraph,
for all 1 <= i < k and the distance of that path.
If there exists no path that satisfies max_total_dist and
max_dist_outdoors constraints, then return None.
"""
if not digraph.has_node(Node(start)) or not digraph.has_node(Node(end)):
raise ValueError('Start or end node, or both not in graph')
current_path = path[0] + [start]
path[0]="This line doesn't change a thing, if I use 'current_path', but why?!"
# path[0] = path[0] + [start]
if start == end:
return [current_path, path[1], path[2]]
# return path
edges = digraph.get_edges_for_node(Node(start))
for edge in edges:
next_node = str(edge.get_destination())
if next_node not in current_path: #avoiding cycles
# if next_node not in path[0]: #avoiding cycles
new_tot = path[1] + edge.get_total_distance()
new_out = path[2] + edge.get_outdoor_distance()
if (best_dist==None or best_dist>=new_tot) and new_out<=max_dist_outdoors:
new_path=get_best_path(digraph, next_node, end, [current_path,new_tot,new_out], \
# new_path=get_best_path(digraph, next_node, end, [path[0],new_tot,new_out], \
max_dist_outdoors, best_dist, best_path)
if new_path != None:
best_path = new_path[0]
best_dist = new_path[1]
if best_path == None:
return None
return [best_path, best_dist]
Я поиграл с этой идеей здесь, но, как и ожидал, список входных данных мутировал. Итак, почему список «путь» в верхнем регистре не изменен?
def foo_mutating(bar):
bar[0] = bar[0] + [1]
print('bar inside foo:', bar)
if len(bar[0]) == 5:
return bar
return foo_mutating(bar)
def foo_nonmut(bar):
temp_bar0 = bar[0]+[1]
print('bar inside foo:', bar)
if len(temp_bar0) == 5:
return [temp_bar0, bar[1], bar[2]]
return foo_nonmut([temp_bar0, bar[1], bar[2]])
def test():
print('-----TESTING NON-MUTATING----')
bar_init = [[], 22, 33]
print('bar_init:', bar_init)
new_bar = foo_nonmut(bar_init)
print('new_bar:', new_bar)
print('bar_init:', bar_init)
print('\n')
print('-----TESTING MUTATING----')
bar_init = [[], 22, 33]
print('bar_init:', bar_init)
new_bar = foo_mutating(bar_init)
print('new_bar:', new_bar)
print('bar_init:', bar_init)
test()
печатает:
-----TESTING NON-MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[], 22, 33]
-----TESTING MUTATING----
bar_init: [[], 22, 33]
bar inside foo: [[1], 22, 33]
bar inside foo: [[1, 1], 22, 33]
bar inside foo: [[1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1], 22, 33]
bar inside foo: [[1, 1, 1, 1, 1], 22, 33]
new_bar: [[1, 1, 1, 1, 1], 22, 33]
bar_init: [[1, 1, 1, 1, 1], 22, 33]