Intenté aplicar un algoritmo genético al problema anterior. Hice una suposición inicial de que dos nodos adicionales conectarían los tres componentes desconectados.

 import networkx as nx import pygad import math from libpysal import weights import numpy as np no_comps_target = 1 # a connected graph has 1 component max_dist_between_nodes = math.sqrt(2) # in km num_pts = 2 # number of additional nodes to add num_genes = num_pts*2 # number of genes required with the GA. A gene each for x and y coordinates. # Generate coordinate np array of existing components centroids = np.array([(v) for k, v in pos.items()]) # Create indcies for new nodes within the GA solution list y_ix = [x for x in range(num_genes) if x % 2 != 0] x_ix = [x for x in range(num_genes) if x % 2 == 0] # Define fitness function def my_fitness_func(solution, solution_idx): # Select coordinates of GA solution xs = np.array(solution[x_ix]) ys = np.array(solution[y_ix]) new_pts = np.column_stack((xs,ys)) # Create one set for all coordinates all_pts = np.append(centroids, new_pts,axis=0) # Calculate weights using a distance band equal to the max distance between nodes w = weights.DistanceBand.from_array(all_pts, threshold=max_dist_between_nodes, silence_warnings=True) # Convert to a networkx obejct G = w.to_networkx() # Calculate the number of graph components for G # Target is 1 - fully connected graph no_comps_solution = nx.number_connected_components(G) # Calculate solution fitness fitness = 1.0 / np.abs(no_comps_target - no_comps_solution + 0.000001) return fitness # Set constraints on possible solution locations x_max = 5 x_min = 0 y_max = 5 y_min = 1 ga_instance = pygad.GA( num_generations=20, num_parents_mating=2, fitness_func=my_fitness_func, sol_per_pop=10, num_genes=num_genes, gene_type= int, gene_space= [{'low': x_min, 'high': x_max, 'step': 1}, {'low': y_min, 'high': y_max, 'step': 1}] * num_pts, mutation_num_genes=1, parent_selection_type = "sss", keep_parents =2, stop_criteria="saturate_10" # Stop if no progress after 10 generations ) ga_instance.run() # If final reached a maximum we should expect a fitness of 100,000. solution, solution_fitness, solution_idx = ga_instance.best_solution() print("Parameters of the best solution : {solution}".format(solution=solution)) print("Fitness value of the best solution = {solution_fitness}".format(solution_fitness=solution_fitness))

Esto da una solución válida:

 Parameters of the best solution : [3 3 2 4] Fitness value of the best solution = 1000000.0

Y al ejecutarlo varias veces, obtengo múltiples soluciones válidas. Lo cual creo que tiene sentido. Además, ¿cómo determinar el número óptimo de nodos adicionales? Especialmente si este problema fuera mucho más grande. Todavía me gustaría saber si hay otras formas de resolver este problema. ¡Especialmente si vienen con menos código!

Estoy bastante convencido de que este problema es NP-difícil. El problema más cercano que conozco es el problema del árbol geométrico de Steiner con métrica octilínea. Tengo dos sugerencias bastante rápidas y sucias. Ambos son heurísticos.

Primera idea: Formule el problema como un problema de árbol Euclidean Steiner ( https://en.wikipedia.org/wiki/Steiner_tree_problem#Euclidean_Steiner_tree ), donde considera solo los nodos de su problema y se olvida de los bordes al principio. Resuelva el problema usando GeoSteiner: http://www.geosteiner.com/ Esto debería darle una solución rápida para problemas con 10000 o más nodos (si necesita resolver problemas más grandes, puede escribir el problema con GeoSteiner después de la generación completa de árboles de Steiner y uso https://scipjack.zib.de/ ). No hay una interfaz de Python, solo escriba su problema en un archivo de texto sin formato, la sintaxis es bastante fácil. Luego, coloque nodos adicionales en la solución provista por GeoSteiner de modo que se cumpla la condición \sqrt(2). Finalmente, debe realizar una limpieza para deshacerse de los bordes redundantes, porque la solución no tendrá en cuenta que ya tiene bordes en su problema original. Tome todos los bordes y nodos que ha calculado hasta ahora y defina un gráfico ponderado dando a todos sus bordes originales un peso de 0 y todos los bordes recién agregados un peso de 1. Considere un problema de árbol de Steiner en gráficos ( https://en. wikipedia.org/wiki/Steiner_tree_problem#Steiner_tree_in_graphs_and_variants ) en este gráfico ponderado, donde el conjunto de terminales corresponde a sus nodos originales. Resuelva este problema del árbol de Steiner con SCIP-Jack: https://scipjack.zib.de/ .

Segunda idea: considere su problema directamente como un problema de árbol de Steiner en gráficos de la siguiente manera: a cada uno de los bordes originales se le asigna un peso 0, considere todos los nodos originales como terminales. Agregue nodos y bordes adicionales a una distancia máxima de \sqrt(2) entre sí. Por ejemplo, podría poner un gran rectángulo alrededor de todos sus componentes conectados y desde cada nodo agregar recursivamente 8 nodos adicionales en un ángulo en grados 0,45,90,... a una distancia de sqrt(2) y con borde de peso 1 en el problema del árbol de Steiner en gráficos, siempre que estén dentro del rectángulo. Si uno de estos nodos está a una distancia sqrt(2) de uno de sus nodos originales, conéctelos directamente con un borde de peso 1. Resuelva el problema del árbol de Steiner correspondiente en gráficos con SCIP-Jack.