Récursivité: comment éviter Python définir ensemble modifié au cours de l'itération RuntimeError
Arrière-plan et la Description du Problème:
J'ai un code qui résout le graphique de coloriage problème (défini comme le problème de l'affectation "couleurs" d'un graphe non-dirigé, faire en sorte que deux sommets reliés par une arête de la même couleur). Je suis en train de mettre en œuvre une solution à l'aide de la contrainte de la propagation d'améliorer l'efficacité d'une norme de retour en arrière récursif de l'algorithme, mais je suis en cours d'exécution dans le message d'erreur suivant:
File "C:\Users\danisg\Desktop\coloring\Solver.py",
line 99, in solve
for color in self.domains[var]:
RuntimeError: Set changed size during iteration
Ici, pour chaque sommet, je garde une set
de possible des valeurs particulières pour ce vertex:
self.domains = { var: set(self.colors) for var in self.vars }
Fois que j'ai une mission, je propage cette contrainte que les pays voisins de domaines, afin de limiter l'espace de recherche:
for key in node.neighbors: # list of keys corresponding to adjacent vertices
if color in self.domains[key]: # remove now to prune possible choices
self.domains[key].remove(color)
Ce n'est pas d'où l'erreur est levée (dans mon code, je m'indiquer où est le problème dans un try-except
bloc), mais peut-être la source du problème.
Ma Question:
Puis-je avoir la bonne idée, ici, si on a pas le droit de mise en œuvre? Plus au point, comment puis-je résoudre ce problème? Aussi, est-il nécessaire de garder un domains
dictionnaire? Ou peut-on faire domain
une propriété de chaque nœud dans le graphe?
Mon Code:
Voici la solve
fonction où ce code est appelé:
def solve(self):
uncolored = [var for var in self.vars if self.map[var].color == None]
if len(uncolored) == 0:
return True
var = min(uncolored, key = lambda x: len(self.domains[var]))
node = self.map[var]
old = { var: set(self.domains[var]) for var in self.vars }
for color in self.domains[var]:
if not self._valid(var, color):
continue
self.map[var].color = color
for key in node.neighbors:
if color in self.domains[key]:
self.domains[key].remove(color)
try:
if self.solve():
return True
except:
print('happening now')
self.map[var].color = None
self.domains = old
return False
Mon application utilise un Node
objet:
class Solver:
class Node:
def __init__(self, var, neighbors, color = None, domain = set()):
self.var = var
self.neighbors = neighbors
self.color = color
self.domain = domain
def __str__(self):
return str((self.var, self.color))
def __init__(self, graph, K):
self.vars = sorted( graph.keys(), key = lambda x: len(graph[x]), reverse = True ) # sort by number of links; start with most constrained
self.colors = range(K)
self.map = { var: self.Node(var, graph[var]) for var in self.vars }
self.domains = { var: set(self.colors) for var in self.vars }
Voici deux autres fonctions qui sont utilisées/sont utiles:
def validate(self):
for var in self.vars:
node = self.map[var]
for key in node.neighbors:
if node.color == self.map[key].color:
return False
return True
def _valid(self, var, color):
node = self.map[var]
for key in node.neighbors:
if self.map[key].color == None:
continue
if self.map[key].color == color:
return False
return True
De données et un Exemple pour lequel le Code est un Échec:
L'exemple de graphique que j'utilise peut être trouvé ici.
La fonction pour la lecture des données:
def read_and_make_graph(input_data):
lines = input_data.split('\n')
first_line = lines[0].split()
node_count = int(first_line[0])
edge_count = int(first_line[1])
graph = {}
for i in range(1, edge_count + 1):
line = lines[i]
parts = line.split()
node, edge = int(parts[0]), int(parts[1])
if node in graph:
graph[node].add(edge)
if edge in graph:
graph[edge].add(node)
if node not in graph:
graph[node] = {edge}
if edge not in graph:
graph[edge] = {node}
return graph
Il devrait être appelé comme suit:
file_location = 'C:\\Users\\danisg\\Desktop\\coloring\\data\\gc_50_3'
input_data_file = open(file_location, 'r')
input_data = ''.join(input_data_file.readlines())
input_data_file.close()
graph = read_and_make_graph(input_data)
solver = Solver(graph, 6) # a 6 coloring IS possible
print(solver.solve()) # True if we solved; False if we didn't
source d'informationauteur rookie
Vous devez vous connecter pour publier un commentaire.
Je pense que le problème est ici:
si
key == var
quandself.domains[key].remove(color)
est appelé, vous modifiez la taille de l'ensemble que vous êtes en train de parcourir. Vous pouvez éviter cela en utilisantÀ l'aide de la copie() vous permettra d'effectuer une itération sur une copie de la série, tandis que la suppression d'éléments de l'original.