python-3.x - 使用 BFS 和 IDFS 进行地图着色 - Python 3

Question

我正在尝试使用深度优先搜索、广度优先搜索和 IDFS 算法来解决地图着色问题（使用 Python 3）。下面是我试图修改的代码（它给出了回溯的结果）。任何人都可以看看并帮助：

这段代码给出了回溯的结果。我无法修改代码，因此它使用 BFS 和 IDFS 搜索节点。

import collections

def bfs(graph, root): 
visited, queue = set(), collections.deque([root])
visited.add(root)
while queue: 
    vertex = queue.popleft()
    for neighbour in graph[vertex]: 
        if neighbour not in visited: 
            visited.add(neighbour) 
            queue.append(neighbour)

def check_valid(graph):
for node,nexts in graph.items():

    assert(nexts) # no isolated node
    assert(node not in nexts) ####### no node linked to itself
    for next in nexts:
        assert(next in graph and node in graph[next]) ####### A linked to B implies B linked to A

class MapColor:

def __init__(self, graph, colors):
    check_valid(graph)
    self.graph = graph
    nodes = list(self.graph.keys())
    self.node_colors  = { node: None for node in nodes }
    self.domains = { node: set(colors) for node in nodes }


def solve(self):
    bfs(map,'R1')
    uncolored_nodes = [n for n,c in self.node_colors.items() if c is None]
    if not uncolored_nodes:
        print (self.node_colors)
        return True

    node = uncolored_nodes[0]
    print ('domain for '  + node + ': ' + str(self.domains[node]))
    for color in self.domains[node]:
        if all(color != self.node_colors[n] for n in self.graph[node]):
            self.set_color(node, color)
            self.remove_from_domains(node, color)

            if self.solve():
                return True

            self.set_color(node, None)
            self.add_to_domains(node, color)

    return False

def set_color(self, key, color):
    self.node_colors[key] = color

def remove_from_domains(self, key, color):
    for node in self.graph[key]:
        if color in self.domains[node]:
            self.domains[node].remove(color)

def add_to_domains(self, key, color):
    for node in self.graph[key]:
        self.domains[node].add(color)

colors    = {'green', 'red', 'blue'}

map={"R1":["R2","R3"],
"R2":["R1","R3","R4"],
"R3":["R1","R2","R4"],
"R4":["R2","R3"]
}

problem = MapColor(map, colors)

problem.solve()

标签： python-3.x