编程知识 cdmana.com

Algorithm experiment report 3 - coloring problem - December 21, 2020

Please attach :https://blog.csdn.net/weixin_43402353/article/details/111547003

1. Coloring

A map visible as the following figure , Each area in the picture represents a province , Now please use red (1)、 LAN (2)、 yellow (3)、 green (4) Four colors, color the provinces , Ask each province to use one color , And the colors of any two neighboring provinces cannot be the same , Please give a color scheme that meets the conditions .
 Insert picture description here

2. Operation results

 Insert picture description here

Test question code

# Project name :
# Project brief introduction :
# do     person :key
# Development time :2020/12/21 21:06

''' Of Graphs m The coloring problem '''

#  Graph with adjacency table 
n = 5  #  Number of nodes 
count = 0 #  Number of schemes 
a, b, c, d, e = range(n)  #  The name of the node 
graph = [
    {
   
   b, c, d},
    {
   
   a, c, d, e},
    {
   
   a, b, d},
    {
   
   a, b, c, e},
    {
   
   b, d}
]

m = 4  # m Color 
Color = [' red ',' blue ',' yellow ',' green ']

x = [0] * n  #  A solution (n Meta array , Fixed length ) Be careful : Explain x The subscript of is a,b,c,d,e!!!
X = []  #  A set of solutions 


#  Collision detection 
def conflict(k):
    global n, graph, x

    #  Find out the k Adjacent nodes that have been colored in front of nodes 
    nodes = [node for node in range(k) if node in graph[k]]
    if x[k] in [x[node] for node in nodes]:  #  There are already adjacent nodes painted this color 
        return True

    return False  #  No conflict 


#  Of Graphs m To color ( Complete solution )
def dfs(k):  #  arrive ( Explain x Of ) The first k Nodes 
    global n, m, graph, x, X, count

    if k == n:  #  The length of the solution exceeds 
        print(x)
        count+=1
        # return
        # X.append(x[:])
    else:
        for color in range(m):  #  Traversal node k Can be painted color number of ( The state space ), It's all the same 
            x[k] = Color[color]
            if not conflict(k):  #  prune 
                dfs(k + 1)


#  test 
dfs(a)  #  From the node a Start 
print(' Altogether {} Kind of plan '.format(count))
—— Dream around the border city , The heart flies home building ——

版权声明
本文为[osc_ ixxabuu0]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201224100744076s.html

Scroll to Top