一个通用的回溯约束满足算法。

Dart tests Coverage Status pub package

用法

约束满足问题（CSP）可用于模拟必须找到一个解来满足一个或多个约束的问题。此类问题的例子包括事件调度或地图着色。

CSP 框架是一组*变量*，它们可以在称为*域*的范围内赋值。例如，如果我们为三位客人烹饪晚餐，我们会将他们定义为可以被赋值为一顿饭的变量。

var doug = Person('Doug', dislikes: ['artichoke']);
var patrick = Person('Patrick', dislikes: ['bananas']);
var susan = Person('Susan', dislikes: ['broccoli']);

var variables = [doug, patrick, susan];

每个客人的域（即餐点）可以建模为字符串列表，其中一个字符串将分配给每个变量（客人）。

var meals = ['artichoke', 'bananas', 'broccoli'];

var domains = {
  doug: meals,
  patrick: meals,
  susan: meals,
};

最后，可以通过继承Constraint类来定义约束。

class AvoidDislikes extends Constraint<Person, String> {
  AvoidDislikes(super.variables);

  @override
  bool isSatisfied(Map<Person, String> assignment) {
    // ...
  }
}

要运行回溯搜索解空间，请实例化CSP类并调用backtrackingSearch函数。

var csp = CSP<Person, String>(variables, domains);

csp.addConstraint(AvoidDislikes(variables));

var result = csp.backtrackingSearch();
print(result);

有关完整示例，请参阅examples/目录。

参考

Java 经典计算机科学问题 – David Kopec

GitHub

查看 Github