質問

背景と問題の説明

私はグラフの色付け問題（広義には無向グラフに「色」を割り当て、エッジで結ばれた2つの頂点が同じ色にならないようにする問題）を解くコードをいくつか持っています。標準的な再帰的バックトラックアルゴリズムの効率を向上させるために、制約伝搬を用いた解法を実装しようとしているのですが、次のようなエラーに遭遇しています。

  File "C:\Users\danisg\Desktop\coloring\Solver.py", 
  line 99, in solve
  for color in self.domains[var]:
  RuntimeError: Set changed size during iteration

ここでは、各頂点に対して set を、その特定の頂点に可能な特定の値で表現します。

  self.domains = { var: set(self.colors) for var in self.vars }

割り当てた後、この制約を隣接するドメインに伝搬させ、探索空間を限定するのです。

  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)

これは、実際にエラーが投げられた場所ではない（私のコードでは、問題が発生した場所を try-except ブロック)ですが、問題の原因である可能性があります。

私の質問です。

私は正しい考えを持っているのだろうか、ここで、正しい実装ではないにしても？もっと言えば、どうすればこれを修正できるのでしょうか？また、別の domains の辞書を参照してください。それとも {コード をグラフの各ノードのプロパティにすることはできますか？

私のコード

以下は domain 関数で、このコードが呼び出されます。

solve

私の実装では 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 オブジェクトを作成します。

Node

その他に使っている/役にたっている機能を2つ紹介します。

コードが失敗しているデータと例

私が使っているグラフの例は、以下の通りです。 こちら .

データを読み込むための関数です。

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

次のように呼び出す必要があります。

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

解決するには？

問題はここだと思うのですが。

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

もし 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) # This is potentially bad. いつ key == var が呼ばれると、現在反復しているセットのサイズを変更することになります。これを避けるには

self.domains[key].remove(color)

copy() を使用すると、元のセットから項目を削除しながら、そのコピーに対して反復処理を行うことができます。