Проблема: в графе G ребер E и узлов N каждый узел имеет вес c, а вес каждого ребра равен длине. Учитывая ребро, найдите подграф для соединения узлов так, чтобы сумма расстояний была меньше заданного порога, а сумма x была максимальной.
Примечание: граф большой и может содержать ~ 2000 узлов. и ~3000 ребер
Я использовал networkx в Python для создания графика, а затем использовал ChatGPT, чтобы помочь мне решить эту проблему. Он предложил подход dfs. Код приведен ниже. Он работает для небольшого графа, но дает сбой из-за ошибки памяти при запуске исходного графа (~2000 узлов и ~3000 ребер)
G = nx.Graph()
# Add nodes with x values
nodes_x = {0:10, 1: 20, 2: 60, 3: 20, 4: 60, 5: 5, 6:50, 7:80, 8:100, 9:50, 10:2, 11:5}
for node, x_value in nodes_x.items():
G.add_node(node, population=x_value)
# Add edges with distances
edges_d = {
(0,1):100,
(1,2):500, (2,3):400, (1,3):100,
(3,10):40, (10,8):40, (8,9):70,
(6,9):200, (3,6):50, (5,6):100, (4,5):50, (7,4):200, (1,7):150, (4,11):20}
for (u, v), dist in edges_d.items():
G.add_edge(u, v, length=dist)
adj = nx.to_numpy_array(G)
from math import inf
max_dist = 500
points = nodes_x
n = len(G.nodes)
total_points = sum(points.values())
dp = [[-inf for _ in range(total_points + 1)] for _ in range(n)]
path = [["" for _ in range(total_points + 1)] for _ in range(n)]
def dfs(current_node, points_collected, current_distance, visited, current_path):
global max_points, best_path
if current_distance max_points:
max_points = points_collected
best_path = current_path[:]
for neighbor in G.neighbors(current_node):
if not visited[neighbor]:
visited[neighbor] = True
weight = G[current_node][neighbor].get('length', inf)
new_points = points_collected + points[neighbor]
current_path.append(neighbor)
dfs(neighbor, new_points, current_distance + weight, visited, current_path)
visited[neighbor] = False
current_path.pop()
max_points = 0
best_path = ""
for start_vertex in range(n):
visited = [False] * n
visited[start_vertex] = True
current_path = [start_vertex]
dfs(start_vertex, points[start_vertex], 0, visited, current_path)
print("Max Points:", max_points)
print("Best Path:", " -> ".join(map(str, best_path)))
Подробнее здесь: https://stackoverflow.com/questions/790 ... inimizings
