资源调度算法

假如要使用RGBY四种颜色对以下地图进行着色

变为点状图

变为树

使用简单点的例子,对以下图进行着色:

*按照先扩充枝条数较小的节点。

对A进行着色的时候,考虑C可以有RGBY颜色可以使用。

1. A:R  C:(R,G,B,Y)

2. B:G ,和A不矛盾  C:(R,G,B,Y)

3. D:B, 和B不矛盾  C:(R,G,B,Y)

4. E:Y,和D不矛盾,(不能先考虑R,因为还有Y可用)  C:(R,G,B,Y)   C无颜色可用   所以第4步要撤销

5.  转而C:Y, 可以重新考虑E用R了,因为颜色已经循环了一次。

 //

按照一个路线,给每一块进行着色后,要进行以下程序:

Foreah 每一个深度优先搜索

  Foreach 每一个“被考虑过的” 块(Vi)

    Foreach 每一个颜色(Xi) in 可选颜色的值域(Di)

      Foreach 每一个约束(Ci)  in C(xi,xj) , xj是属于Dj

        if 不存在Xj,Xj在C(xi,xj)当中  //如果存在Xj,Xj不在C(xi,xj)当中

          从Di中移除Xi    

        if Di是空的

          返回

//先胡乱赋值颜色

foreach in 各个线路

foreach in ABDEC[考虑所有的块]

  A : foreach in (RGBY)

  无事发生

  A填R

  B:  foreach in D(RGBY)   R

     R:违反约束,从D移除

  B填G

  D:foreach in D(RGBY)   RG

    R:还没循环一次,从D移除

    G:违反约束,从D移除  

  D填B

  无事发生

  E:foeach in D(RGBY)  RGBY

     R:还没循环一次,从D移除

     G:还没循环一次,从D移除

     B:违反约束,从D移除

  E填Y

  C:foeach in D(RGBY) 

     R:违反约束,从D移除

     G:违反约束,从D移除

     B:违反约束,从D移除

     Y:违反约束,从D移除

  D为空,C不可填,遍历下一条路线

foreach in ABDCE 

  。。。

原文地址:https://www.cnblogs.com/pylblog/p/10314209.html