我正在尝试使用 networkx 库绘制卡车路线优化的结果。首先我必须准备数据，但我被困住了。
这是初始数据的小示例：
Vehicle Route
0 V0 [0,3](V0)
1 V0 [3,0](V0)
2 V1 [0,3](V1)
3 V1 [0,8](V1)
4 V1 [2,0](V1)
5 V1 [3,2](V1)
6 V1 [8,0](V1)
有两辆卡车：V0 和 V1。 V0 的路线是：0 到 3 到 0。但是 V1 有两条路线：0 到 8 到 0 和 0 到 3 到 2 到 0。
每次游览必须在节点 0 开始和结束。
我必须解决两个问题：
最终结果一定是这样的：
{'V0': [0,3,0], 'V1': [[0,3,2,0], [0,8,0]]}
我有一个代码，但它没有产生我想要的东西：
tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}
def convert_to_list(s):
return list(map(int, s.split(',')))
# Function to process each value in the 'tours' dictionary
def process_value(value):
result = []
current_list = []
for pair in value:
pair_list = convert_to_list(pair)
if not current_list or pair_list[0] == 0:
current_list.extend(pair_list)
elif pair_list[1] == 0:
current_list.append(pair_list[0])
current_list.append(0)
result.append(current_list)
current_list = [0]
else:
current_list.append(pair_list[0])
if current_list:
current_list.append(0)
result.append(current_list)
return result
# Create the 'tours1' dictionary using the processing functions
tours1 = {key: process_value(value) for key, value in tours.items()}
# Print the result
print(tours1)
输出：
{'V0': [[0, 3, 3, 0], [0, 0]], 'V1': [[0, 3, 0, 8, 2, 0], [0, 3, 8, 0], [0, 0]]}
有什么想法吗？
谢谢！
主要思想是将数据组织成树，然后进行深度优先搜索以检索有效路线。
将数据组织成树：
tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}
tours2 = {}
for vehicle, routes in tours.items():
route_tree = {}
for route in routes:
frm,to = route.split(',')
frm = int(frm)
to = int(to)
if frm in route_tree:
route_tree[frm].append(to)
else:
route_tree[frm] = [to]
tours2[vehicle] = route_tree
旅游2：
{'V0': {0: [3], 3: [0]}, 'V1': {0: [3, 8], 2: [0], 3: [2], 8: [0]}}
DFS有效路线：
routes = {}
for vehicle in tours2:
running_routes = [[0]]
completed_routes = []
while running_routes:
running_route = running_routes.pop()
if running_route[-1] == 0 and len(running_route) > 1:
completed_routes.append(running_route)
else:
for nxt_node in tours2[vehicle][running_route[-1]]:
running_routes.append(running_route + [nxt_node])
routes[vehicle] = completed_routes
路线：
{'V0': [[0, 3, 0]], 'V1': [[0, 8, 0], [0, 3, 2, 0]]}
这是一个 O(N^2) 的可行解决方案，其中 N 是节点数（如果没有点可以到达两次）。
tours = {'V0': ['0,3', '3,0'], 'V1': ['0,3', '0,8', '2,0', '3,2', '8,0']}
def process(value):
result = [] # the final result
nodes = {} # a dictionary in the form of start_node: end_node
starts = [] # a list of pairs (start, end) where start is 0
for val in value: # goes through each step
a, b = val.split(",") # get start and end
nodes[a] = b # add the node to nodes
if a == "0": # if the step is a start, add it to starts
starts.append((a, b))
for a, b in starts: # go through each starts
inter = [a, b] # list representing one route
while b != "0": # as long as we didn't return to 0, continue
b = nodes[b] # get the next node
inter.append(b) # add it to the route
result.append(inter)
return result
def convert():
"""
Goes through each truck and process it's routes.
"""
result = {}
for k, v in tours.items():
result[k] = process(v)
return result
print(convert())
这给出了结果：
{'V0': [['0', '3', '0']], 'V1': [['0', '3', '2', '0'], ['0', '8', '0']]}如果你希望第二个列表的维度为 1，你可以在 process 方法中添加一个 if 检查，如下所示：
def process(value):
result = [] # the final result
nodes = {} # a dictionary in the form of start_node: end_node
starts = [] # a list of pairs (start, end) where start is 0
for val in value: # goes through each step
a, b = val.split(",") # get start and end
nodes[a] = b # add the node to nodes
if a == "0": # if the step is a start, add it to starts
starts.append((a, b))
for a, b in starts: # go through each starts
inter = [a, b] # list representing one route
while b != "0": # as long as we didn't return to 0, continue
b = nodes[b] # get the next node
inter.append(b) # add it to the route
result.append(inter)
if len(result) == 1:
return result[0]
return result