Timefold图着色问题：同边节点异色约束最优实现咨询

一、修复PointPair问题事实方案的无效问题 #

你遇到的分数不随移动变化的核心原因是：约束定义未正确关联Point实体，Timefold无法感知Point颜色变化对约束的影响。按以下步骤调整即可解决：

1. 定义正确的PointPair事实
   确保PointPair持有两个相邻Point的引用，且做去重处理避免重复边（如A-B和B-A）：

   public class PointPair {
       private final Point pointA;
       private final Point pointB;
   
       public PointPair(Point pointA, Point pointB) {
           // 约定id小的在前，避免重复配对
           if (pointA.getId().compareTo(pointB.getId()) > 0) {
               this.pointA = pointB;
               this.pointB = pointA;
           } else {
               this.pointA = pointA;
               this.pointB = pointB;
           }
       }
   
       // 仅提供getter，问题事实需为只读
       public Point getPointA() { return pointA; }
       public Point getPointB() { return pointB; }
   }
   

2. 将PointPair加入问题事实集合
   在你的Solution类中，添加PointPair集合，并在getProblemFacts()方法中返回：

   public class GraphColoringSolution implements Solution<HardSoftScore> {
       private List<Point> pointList;
       private List<PointPair> pointPairList; // 存储所有边对应的PointPair
   
       // 其他属性、getter/setter...
   
       @Override
       public Collection<?> getProblemFacts() {
           List<Object> facts = new ArrayList<>();
           facts.addAll(pointPairList);
           return facts;
       }
   }
   

3. 编写关联实体的约束逻辑
   通过join操作将PointPair与对应的两个Point实体绑定，让Timefold能感知Point颜色变化：

   public class GraphColoringConstraintProvider implements ConstraintProvider {
       @Override
       public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
           return new Constraint[] {
               adjacentPointsDifferentColor(constraintFactory)
           };
       }
   
       private Constraint adjacentPointsDifferentColor(ConstraintFactory constraintFactory) {
           return constraintFactory.from(PointPair.class)
                   .join(Point.class, Joiners.equal(PointPair::getPointA))
                   .join(Point.class, Joiners.equal(PointPair::getPointB))
                   .filter((pair, a, b) -> a.getColor().equals(b.getColor()))
                   .penalize("Adjacent same color", HardSoftScore.ONE_HARD);
       }
   }
   

二、优化第一种isNeighbour判断的效率问题 #

如果不想用PointPair，可以通过预计算邻居集合减少重复判断：

1. 给Point预存邻居集合
   在初始化Point时，直接把所有相邻点存入集合，避免每次判断都遍历全图：

   public class Point {
       private Integer id;
       @PlanningVariable(valueRangeProviderRefs = "colorRange")
       private String color;
       private Set<Point> neighbours; // 初始化时填充好邻居
   
       public boolean isNeighbour(Point other) {
           return neighbours.contains(other);
       }
   
       // getter/setter...
   }
   

2. 优化约束中的配对逻辑
   用Joiners.greaterThan(Point::getId)避免重复配对，减少计算量：

   private Constraint adjacentPointsDifferentColor(ConstraintFactory constraintFactory) {
       return constraintFactory.from(Point.class)
               .join(Point.class, Joiners.greaterThan(Point::getId))
               .filter((a, b) -> a.isNeighbour(b) && a.getColor().equals(b.getColor()))
               .penalize("Adjacent same color", HardSoftScore.ONE_HARD);
   }
   

三、最优方案推荐 #

优先选择PointPair问题事实的方案，因为Timefold对join操作有索引优化，比filter判断邻居的效率高得多，尤其在大规模图场景下差距明显。

内容的提问来源于stack exchange，提问作者Alexey