深度优先搜索，约束失败回溯
Depth-First-Search, Backtracking when constraint failed
所以，我知道深度优先搜索不适合这个问题，像 UCS 或 Astar 这样的东西会好得多，只是想看看是否可以使用 DFS 方法。
我需要在成本预算内找到一条路径，我使用 dfs 的方法是在它们被推送时保持到达堆栈中下一个节点的成本，如果到达下一个节点超过，它会忽略不推。
我面临的问题是，当超出预算时，我正在努力寻找一种方法来将导致这条路径的节点设置为未访问过的节点，以便较新的路径可以考虑它们。我觉得这与正确设置 visited/unvisited 有关并且已经测试了几个但在更大的图形输入中，它总是无法在约束内找到路径（已确认它存在使用其他方法）
def DFS(start, end, budget, adj_list, dist_list, cost_list):
# TODO Depth-First Search
print(f"DFS path from {start} to {end} with budget of {budget}...")
# Set all initial to not visited
visited = [False] * (len(adj_list) + 1)
parent = [None] * (len(adj_list) + 1)
stack = deque()
# Push starting node into the stack
stack.append((start, 0))
parent[start] = -1
path = deque()
pathFound = False
while (len(stack)):
next_node_tup = stack.pop()
next_node = int(next_node_tup[0])
energy_used = next_node_tup[1]
# Found target, proceed to print path
if (next_node == end):
pathFound = True
break
# Set to visited if not yet
# if (not visited[next_node]):
# visited[next_node] = True
# Add all connecting nodes to top of stack
edgeNodes = adj_list[str(next_node)]
#print(f"There are {len(edgeNodes)} nodes connecting to {next_node}")
for node in edgeNodes:
node = int(node)
#print(f"Node {node} connecting to node {next_node}")
if (not visited[node]):
# If taking this node exceeds budget, we dont want it
minipath = str(next_node) + "," + str(node)
print(f"Cost to go from {next_node} to {node} is {cost_list[minipath]}")
energy_if_take = energy_used + cost_list[minipath]
print(f"Energy used if path taken is {energy_if_take}")
if (energy_if_take <= budget):
parent[node] = next_node
stack.append((node, energy_if_take))
visited[node] = True
else:
print(f"Budget exceeded")
# ! Need to set backtracked nodes to not visited
# ! Problem is here!
visited[node] = False
print(stack)
if pathFound:
curr = end
path = []
distance = 0
energy = 0
print("Printing path")
while(curr != -1):
path.append(curr)
if (parent[curr] != -1):
miniPath = str(parent[curr]) + "," + str(curr)
distance += dist_list[miniPath]
energy += cost_list[miniPath]
curr = parent[curr]
# Reverse and print path
path.reverse()
print(*path, sep = " -> ")
print(f"Number of jumps is {len(path)}")
print(f"Distance from {start} to {end} is {distance}")
print(f"Cost from {start} to {end} is {energy}")
else:
print("No path that satisfies budget")
如果有任何提示或建议，我们将不胜感激，在这里停留了好几天:(
这是您的代码的修改版本，带有测试用例，可以解决您问题中的问题。
假设：
- 图形是有向的，边按照
adj_list;
- 图表可能有循环（因此希望使用
visited 来追踪之前的相遇）；
- 我们想使用 DFS 遍历图。
关键逻辑：
- 将
start 节点附加到 stack，并将 waiting_for_adj_list 标志设置为 False
- 在 DFS 循环中，从
stack 中弹出一个节点，然后 (1) 将其标记为已访问，re-append 将其标记为 stack，并将 waiting_for_adj_list 标志设置为True 并将其 children 附加到 stack（以检测到循环或预算中断为准）或 (2) 重置节点及其 children. 的已访问状态
- 达到
end 节点达到或低于预算时提前退出。
请注意，我在类型使用上有些随意（list 而不是 deque stack，dict 而不是 list parent 和 visited，也许还有其他几个）以避免复杂性 and/or 问题焦点之外的并发症。
def DFS(start, end, budget, adj_list, dist_list, cost_list):
visited = {start: True}
parent = {}
path = []
pathFound = False
stack = [(start, 0, False)] #node, energy, waiting_for_adj_list
while stack:
next_node, energy_used, waiting_for_adj_list = stack.pop()
next_node = int(next_node)
if next_node == end:
pathFound = True
print(f"Path found at cost {energy_used}: {path + [next_node]}")
break
if waiting_for_adj_list:
# now that we're done with next_node and its children, mark children unvisited
edgeNodes = adj_list[str(next_node)]
for node in edgeNodes:
node = int(node)
if parent[node] == next_node:
visited[node] = False
visited[next_node] = False
print(f"done traversing {next_node}, visited {[node for node, v in visited.items() if v]}")
path.pop()
continue
stack.append((next_node, energy_used, True)) # append to stack again with waiting_for_adj_list == True
visited[next_node] = True
path.append(next_node)
edgeNodes = adj_list[str(next_node)]
for node in edgeNodes:
node = int(node)
if node in visited and visited[node]:
# detected a cycle, don't follow it
print(f"Cycle detected: {path + [node]}")
else:
minipath = str(next_node) + "," + str(node)
energy_if_take = energy_used + cost_list[minipath]
if (energy_if_take <= budget):
parent[node] = next_node
stack.append((node, energy_if_take, False))
else:
print(f"Budget {budget} exceeded at cost {energy_if_take} for path {path + [node]}")
# node is still available to be explore from other parents, but don't put on stack
print(f"stack {stack}")
print(f"path {path}")
if pathFound:
curr = end
path = []
distance = 0
energy = 0
print("Printing path")
while(curr != -1):
path.append(curr)
if (curr in parent):
miniPath = str(parent[curr]) + "," + str(curr)
distance += dist_list[miniPath]
energy += cost_list[miniPath]
curr = parent[curr] if curr in parent else -1
# Reverse and print path
path.reverse()
print(*path, sep = " -> ")
print(f"Number of jumps is {len(path)}")
print(f"Distance from {start} to {end} is {distance}")
print(f"Cost from {start} to {end} is {energy}")
else:
print("No path that satisfies budget")
# Test case
start, end = 0, 7
budget = 200
adj_list = {
'0':{1, 2, 3},
'1':{4}, '2':{4}, '3':{4},
'4':{5, 6},
'5':{7},
'6':{7, 8},
'7':{},
'8':{4}
}
#4,6,8,4 is a cycle
cost_list = {
'0,1':10,
'0,2':20,
'0,3':30,
'1,4':40,
'2,4':400,
'3,4':40,
'4,5':50,
'4,6':60,
'5,7':100,
'6,7':700,
'6,8':8,
'8,4':40
}
#0,3,4,6,8,4 has a cycle
#0,3,4,6,7 short-circuits at 830 cost
#0,3,4,5,7 short-circuits at 220 cost
#0,2,4 short-circuits at 420 cost
#0,1,4,6,8,4 is a cycle
#0,1,4,5,7 costs 200
dist_list = {
'0,1':1,
'0,2':1,
'0,3':1,
'1,4':1,
'2,4':1,
'3,4':1,
'4,5':1,
'4,6':1,
'5,7':1,
'6,7':1,
'6,8':1,
'8,4':1
}
DFS(start, end, budget, adj_list, dist_list, cost_list)
此代码：
- 扩展堆栈上的元组以具有第三个元素
waiting_for_adj_list，因此当我们 pop 一个 next_node 我们立即再次 append 它并将此标志设置为True，或者如果已经是 True，我们为 next_node 的 children 做一些 clean-up。
- 纯粹使用
visited 来检测循环，并在 children 之前将其清除，作为上述 clean-up 的一部分，因此如果 next_node 下游的节点也被在 next_node 上游节点的其他路径上，可以遍历它们，并且可以畅通无阻地进行此类路径特有的成本分析。
- 检测到循环时，除了中断循环外不采取任何特殊操作。
测试用例标准输出为：
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, False)]
path [0]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, False)]
path [0, 3]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, False), (6, 130, False)]
path [0, 3, 4]
Budget 200 exceeded at cost 830 for path [0, 3, 4, 6, 7]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, False), (6, 130, True), (8, 138, False)]
path [0, 3, 4, 6]
Cycle detected: [0, 3, 4, 6, 8, 4]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, False), (6, 130, True), (8, 138, True)]
path [0, 3, 4, 6, 8]
done traversing 8, visited [0, 3, 6]
done traversing 6, visited [0, 3]
Budget 200 exceeded at cost 220 for path [0, 3, 4, 5, 7]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, True)]
path [0, 3, 4, 5]
done traversing 5, visited [0, 3]
done traversing 4, visited [0, 3]
done traversing 3, visited [0]
Budget 200 exceeded at cost 420 for path [0, 2, 4]
stack [(0, 0, True), (1, 10, False), (2, 20, True)]
path [0, 2]
done traversing 2, visited [0]
stack [(0, 0, True), (1, 10, True), (4, 50, False)]
path [0, 1]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, False), (6, 110, False)]
path [0, 1, 4]
Budget 200 exceeded at cost 810 for path [0, 1, 4, 6, 7]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, False), (6, 110, True), (8, 118, False)]
path [0, 1, 4, 6]
Cycle detected: [0, 1, 4, 6, 8, 4]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, False), (6, 110, True), (8, 118, True)]
path [0, 1, 4, 6, 8]
done traversing 8, visited [0, 6, 1]
done traversing 6, visited [0, 1]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, True), (7, 200, False)]
path [0, 1, 4, 5]
Path found at cost 200: [0, 1, 4, 5, 7]
Printing path
0 -> 1 -> 4 -> 5 -> 7
Number of jumps is 5
Distance from 0 to 7 is 4
Cost from 0 to 7 is 200
毫无疑问，还有优化机会，但根据我对您的问题的理解以及 objective 如本回答中的假设所述，我相信该代码应该使用 DFS 在成本预算内找到一条路径。
所以，我知道深度优先搜索不适合这个问题，像 UCS 或 Astar 这样的东西会好得多，只是想看看是否可以使用 DFS 方法。
我需要在成本预算内找到一条路径，我使用 dfs 的方法是在它们被推送时保持到达堆栈中下一个节点的成本，如果到达下一个节点超过，它会忽略不推。
我面临的问题是，当超出预算时，我正在努力寻找一种方法来将导致这条路径的节点设置为未访问过的节点，以便较新的路径可以考虑它们。我觉得这与正确设置 visited/unvisited 有关并且已经测试了几个但在更大的图形输入中，它总是无法在约束内找到路径（已确认它存在使用其他方法）
def DFS(start, end, budget, adj_list, dist_list, cost_list):
# TODO Depth-First Search
print(f"DFS path from {start} to {end} with budget of {budget}...")
# Set all initial to not visited
visited = [False] * (len(adj_list) + 1)
parent = [None] * (len(adj_list) + 1)
stack = deque()
# Push starting node into the stack
stack.append((start, 0))
parent[start] = -1
path = deque()
pathFound = False
while (len(stack)):
next_node_tup = stack.pop()
next_node = int(next_node_tup[0])
energy_used = next_node_tup[1]
# Found target, proceed to print path
if (next_node == end):
pathFound = True
break
# Set to visited if not yet
# if (not visited[next_node]):
# visited[next_node] = True
# Add all connecting nodes to top of stack
edgeNodes = adj_list[str(next_node)]
#print(f"There are {len(edgeNodes)} nodes connecting to {next_node}")
for node in edgeNodes:
node = int(node)
#print(f"Node {node} connecting to node {next_node}")
if (not visited[node]):
# If taking this node exceeds budget, we dont want it
minipath = str(next_node) + "," + str(node)
print(f"Cost to go from {next_node} to {node} is {cost_list[minipath]}")
energy_if_take = energy_used + cost_list[minipath]
print(f"Energy used if path taken is {energy_if_take}")
if (energy_if_take <= budget):
parent[node] = next_node
stack.append((node, energy_if_take))
visited[node] = True
else:
print(f"Budget exceeded")
# ! Need to set backtracked nodes to not visited
# ! Problem is here!
visited[node] = False
print(stack)
if pathFound:
curr = end
path = []
distance = 0
energy = 0
print("Printing path")
while(curr != -1):
path.append(curr)
if (parent[curr] != -1):
miniPath = str(parent[curr]) + "," + str(curr)
distance += dist_list[miniPath]
energy += cost_list[miniPath]
curr = parent[curr]
# Reverse and print path
path.reverse()
print(*path, sep = " -> ")
print(f"Number of jumps is {len(path)}")
print(f"Distance from {start} to {end} is {distance}")
print(f"Cost from {start} to {end} is {energy}")
else:
print("No path that satisfies budget")
如果有任何提示或建议，我们将不胜感激，在这里停留了好几天:(
这是您的代码的修改版本，带有测试用例，可以解决您问题中的问题。
假设：
- 图形是有向的，边按照
adj_list; - 图表可能有循环（因此希望使用
visited来追踪之前的相遇）； - 我们想使用 DFS 遍历图。
关键逻辑：
- 将
start节点附加到stack，并将waiting_for_adj_list标志设置为 False - 在 DFS 循环中，从
stack中弹出一个节点，然后 (1) 将其标记为已访问，re-append 将其标记为stack，并将waiting_for_adj_list标志设置为True 并将其 children 附加到stack（以检测到循环或预算中断为准）或 (2) 重置节点及其 children. 的已访问状态
- 达到
end节点达到或低于预算时提前退出。
请注意，我在类型使用上有些随意（list 而不是 deque stack，dict 而不是 list parent 和 visited，也许还有其他几个）以避免复杂性 and/or 问题焦点之外的并发症。
def DFS(start, end, budget, adj_list, dist_list, cost_list):
visited = {start: True}
parent = {}
path = []
pathFound = False
stack = [(start, 0, False)] #node, energy, waiting_for_adj_list
while stack:
next_node, energy_used, waiting_for_adj_list = stack.pop()
next_node = int(next_node)
if next_node == end:
pathFound = True
print(f"Path found at cost {energy_used}: {path + [next_node]}")
break
if waiting_for_adj_list:
# now that we're done with next_node and its children, mark children unvisited
edgeNodes = adj_list[str(next_node)]
for node in edgeNodes:
node = int(node)
if parent[node] == next_node:
visited[node] = False
visited[next_node] = False
print(f"done traversing {next_node}, visited {[node for node, v in visited.items() if v]}")
path.pop()
continue
stack.append((next_node, energy_used, True)) # append to stack again with waiting_for_adj_list == True
visited[next_node] = True
path.append(next_node)
edgeNodes = adj_list[str(next_node)]
for node in edgeNodes:
node = int(node)
if node in visited and visited[node]:
# detected a cycle, don't follow it
print(f"Cycle detected: {path + [node]}")
else:
minipath = str(next_node) + "," + str(node)
energy_if_take = energy_used + cost_list[minipath]
if (energy_if_take <= budget):
parent[node] = next_node
stack.append((node, energy_if_take, False))
else:
print(f"Budget {budget} exceeded at cost {energy_if_take} for path {path + [node]}")
# node is still available to be explore from other parents, but don't put on stack
print(f"stack {stack}")
print(f"path {path}")
if pathFound:
curr = end
path = []
distance = 0
energy = 0
print("Printing path")
while(curr != -1):
path.append(curr)
if (curr in parent):
miniPath = str(parent[curr]) + "," + str(curr)
distance += dist_list[miniPath]
energy += cost_list[miniPath]
curr = parent[curr] if curr in parent else -1
# Reverse and print path
path.reverse()
print(*path, sep = " -> ")
print(f"Number of jumps is {len(path)}")
print(f"Distance from {start} to {end} is {distance}")
print(f"Cost from {start} to {end} is {energy}")
else:
print("No path that satisfies budget")
# Test case
start, end = 0, 7
budget = 200
adj_list = {
'0':{1, 2, 3},
'1':{4}, '2':{4}, '3':{4},
'4':{5, 6},
'5':{7},
'6':{7, 8},
'7':{},
'8':{4}
}
#4,6,8,4 is a cycle
cost_list = {
'0,1':10,
'0,2':20,
'0,3':30,
'1,4':40,
'2,4':400,
'3,4':40,
'4,5':50,
'4,6':60,
'5,7':100,
'6,7':700,
'6,8':8,
'8,4':40
}
#0,3,4,6,8,4 has a cycle
#0,3,4,6,7 short-circuits at 830 cost
#0,3,4,5,7 short-circuits at 220 cost
#0,2,4 short-circuits at 420 cost
#0,1,4,6,8,4 is a cycle
#0,1,4,5,7 costs 200
dist_list = {
'0,1':1,
'0,2':1,
'0,3':1,
'1,4':1,
'2,4':1,
'3,4':1,
'4,5':1,
'4,6':1,
'5,7':1,
'6,7':1,
'6,8':1,
'8,4':1
}
DFS(start, end, budget, adj_list, dist_list, cost_list)
此代码：
- 扩展堆栈上的元组以具有第三个元素
waiting_for_adj_list，因此当我们pop一个next_node我们立即再次append它并将此标志设置为True，或者如果已经是 True，我们为next_node的 children 做一些 clean-up。 - 纯粹使用
visited来检测循环，并在 children 之前将其清除，作为上述 clean-up 的一部分，因此如果next_node下游的节点也被在next_node上游节点的其他路径上，可以遍历它们，并且可以畅通无阻地进行此类路径特有的成本分析。 - 检测到循环时，除了中断循环外不采取任何特殊操作。
测试用例标准输出为：
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, False)]
path [0]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, False)]
path [0, 3]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, False), (6, 130, False)]
path [0, 3, 4]
Budget 200 exceeded at cost 830 for path [0, 3, 4, 6, 7]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, False), (6, 130, True), (8, 138, False)]
path [0, 3, 4, 6]
Cycle detected: [0, 3, 4, 6, 8, 4]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, False), (6, 130, True), (8, 138, True)]
path [0, 3, 4, 6, 8]
done traversing 8, visited [0, 3, 6]
done traversing 6, visited [0, 3]
Budget 200 exceeded at cost 220 for path [0, 3, 4, 5, 7]
stack [(0, 0, True), (1, 10, False), (2, 20, False), (3, 30, True), (4, 70, True), (5, 120, True)]
path [0, 3, 4, 5]
done traversing 5, visited [0, 3]
done traversing 4, visited [0, 3]
done traversing 3, visited [0]
Budget 200 exceeded at cost 420 for path [0, 2, 4]
stack [(0, 0, True), (1, 10, False), (2, 20, True)]
path [0, 2]
done traversing 2, visited [0]
stack [(0, 0, True), (1, 10, True), (4, 50, False)]
path [0, 1]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, False), (6, 110, False)]
path [0, 1, 4]
Budget 200 exceeded at cost 810 for path [0, 1, 4, 6, 7]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, False), (6, 110, True), (8, 118, False)]
path [0, 1, 4, 6]
Cycle detected: [0, 1, 4, 6, 8, 4]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, False), (6, 110, True), (8, 118, True)]
path [0, 1, 4, 6, 8]
done traversing 8, visited [0, 6, 1]
done traversing 6, visited [0, 1]
stack [(0, 0, True), (1, 10, True), (4, 50, True), (5, 100, True), (7, 200, False)]
path [0, 1, 4, 5]
Path found at cost 200: [0, 1, 4, 5, 7]
Printing path
0 -> 1 -> 4 -> 5 -> 7
Number of jumps is 5
Distance from 0 to 7 is 4
Cost from 0 to 7 is 200
毫无疑问，还有优化机会，但根据我对您的问题的理解以及 objective 如本回答中的假设所述，我相信该代码应该使用 DFS 在成本预算内找到一条路径。