如何用OptaPlanner的Constraint Streams实现相邻数值分组求平均得分规则？

问题场景 #

规划实体持有Integer列表，目标是对列表排序后，将其划分为数值连续递增的子列表（子列表内相邻元素差值为1，子列表间元素不连续），计算每个子列表的平均值之和作为得分（如输入[12,1,4,5,6,7,11,9,10]，排序后划分为[1]、[4,5,6,7]、[9,10,11,12]，总得分为1+5.5+10.5=17），需用Constraint Streams实现该逻辑。

实现步骤 #

1. 定义规划模型 #

规划实体（NumberElement）

代表列表中的每个数字元素，包含唯一标识、数值和规划变量（位置索引）：

public class NumberElement {
    private Integer id;
    private Integer value;
    @PlanningVariable(valueRangeProviderRefs = "positionRange")
    private Integer position; // 0-based位置，每个位置唯一

    // 构造函数、Getter、Setter省略
}

解决方案类（NumberSortingSolution）

管理规划实体集合、位置范围和得分：

public class NumberSortingSolution {
    @PlanningEntityCollectionProperty
    private List<NumberElement> elements;
    @ValueRangeProvider(id = "positionRange")
    private ValueRange<Integer> positionRange;
    @PlanningScore
    private SimpleScore<BigDecimal> score; // 用BigDecimal处理小数得分

    public NumberSortingSolution(List<NumberElement> elements) {
        this.elements = elements;
        this.positionRange = ValueRangeFactory.createIntValueRange(0, elements.size());
    }

    // Getter、Setter省略
}

2. 用Constraint Streams实现约束逻辑 #

核心思路：

• 所有元素单独作为子列表时，得分等于元素总和；每将两个连续数值的元素合并为一个子列表，得分会减少(a+b)/2（因为a+b变为(a+b)/2，差值为(a+b)/2）。
• 因此，只需惩罚所有位置相邻但数值不连续的元素对，惩罚值为两元素和的一半，OptaPlanner会自动优化排序，减少惩罚，最终得分即为连续子列表的平均值之和。

约束实现代码：

public class NumberConstraints implements ConstraintProvider {
    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
                penalizeNonConsecutivePairs(constraintFactory)
        };
    }

    private Constraint penalizeNonConsecutivePairs(ConstraintFactory constraintFactory) {
        // 1. 按position排序所有元素
        UniConstraintStream<NumberElement> sortedElements = constraintFactory.from(NumberElement.class)
                .sorted(Comparator.comparing(NumberElement::getPosition));

        // 2. 关联每个元素与它的下一个位置元素
        BiConstraintStream<NumberElement, NumberElement> consecutivePositionPairs = sortedElements.join(
                sortedElements,
                Joiners.equal(element -> element.getPosition() + 1, NumberElement::getPosition)
        );

        // 3. 筛选出数值不连续的位置相邻对，进行惩罚
        return consecutivePositionPairs
                .filter((prev, next) -> !next.getValue().equals(prev.getValue() + 1))
                .penalize("Penalize non-consecutive value pairs",
                        SimpleScore.ofBigDecimal((prev, next) -> {
                            BigDecimal sum = BigDecimal.valueOf(prev.getValue()).add(BigDecimal.valueOf(next.getValue()));
                            return sum.divide(BigDecimal.valueOf(2)); // 惩罚值为两元素和的一半
                        }))
                .asConstraint();
    }
}

3. 运行求解 #

创建求解器并运行，最终得到的最优解即为符合要求的排序结果，其得分就是连续子列表的平均值之和：

public class NumberSortingApp {
    public static void main(String[] args) {
        // 初始化元素列表
        List<NumberElement> elements = Arrays.asList(
                new NumberElement(1, 12, null),
                new NumberElement(2, 1, null),
                new NumberElement(3, 4, null),
                new NumberElement(4, 5, null),
                new NumberElement(5, 6, null),
                new NumberElement(6, 7, null),
                new NumberElement(7, 11, null),
                new NumberElement(8, 9, null),
                new NumberElement(9, 10, null)
        );

        // 创建解决方案
        NumberSortingSolution solution = new NumberSortingSolution(elements);

        // 构建求解器
        SolverFactory<NumberSortingSolution> solverFactory = SolverFactory.create(
                SolverConfig.createFromXmlResource("numberSortingSolverConfig.xml")
        );
        Solver<NumberSortingSolution> solver = solverFactory.buildSolver();

        // 求解
        NumberSortingSolution bestSolution = solver.solve(solution);

        // 输出结果
        System.out.println("最优排序结果：");
        bestSolution.getElements().stream()
                .sorted(Comparator.comparing(NumberElement::getPosition))
                .forEach(element -> System.out.print(element.getValue() + " "));
        System.out.println("\n总得分为：" + bestSolution.getScore().getScore());
    }
}

对应的求解器配置文件numberSortingSolverConfig.xml示例：

<?xml version="1.0" encoding="UTF-8"?>
<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
        xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
    <solutionClass>com.example.NumberSortingSolution</solutionClass>
    <entityClass>com.example.NumberElement</entityClass>
    <scoreDirectorFactory>
        <constraintProviderClass>com.example.NumberConstraints</constraintProviderClass>
    </scoreDirectorFactory>
    <termination>
        <secondsSpentLimit>30</secondsSpentLimit>
    </termination>
</solver>

原理说明 #

• 当两个数值连续的元素在排序后相邻时，不会产生惩罚；若数值不连续的元素相邻，则会被惩罚(a+b)/2。
• OptaPlanner通过优化排序，尽可能减少惩罚次数和惩罚值，最终得到的得分等于所有连续子列表的平均值之和（总元素和减去所有连续数值对的(a+b)/2之和）。

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