约束编程示例

通过一个示例应用程序来理解约束编程，该应用程序可以转换字符的大小写和 ASCII 码。

图片来源

João Trindade。Jason Baker 修改。CC BY-SA 2.0。

在计算中，有很多不同的方法来解决问题。您可能会通过计算尽可能多的可能性来“蛮力”找到解决方案，或者您可能会采用程序化的方法，并仔细确定影响正确答案的已知因素。在约束编程中，问题被视为对可能成为有效解决方案的一系列限制。这种范式可以有效地应用于解决一组可以转化为变量和约束或表示为数学方程式的问题。这样，它与约束满足问题 (CSP) 相关。

使用声明式编程风格，它描述了一个具有某些属性的通用模型。与命令式风格相反，它不告诉如何实现某事，而是什么要实现。约束编程不是定义一组只有一种明显方法来计算值的指令，而是声明约束内变量之间的关系。最终模型使得计算变量的值成为可能，而无需考虑方向或变化。因此，一个变量值的任何变化都会影响整个系统（即，所有其他变量），并且为了满足定义的约束，它会导致重新计算其他值。

作为一个例子，让我们以毕达哥拉斯定理为例：a² + b² = c²。约束由这个方程表示，它有三个变量（a、b 和 c），每个变量都有一个域（非负）。使用命令式编程风格，如果我们知道另外两个变量，要计算任何一个变量，我们需要创建三个不同的函数（因为每个变量都由不同的方程计算）

c = √(a² + b²)
a = √(c² - b²)
b = √(c² - a²)

这些函数满足主要约束，并且为了检查域，每个函数都应该验证输入。此外，至少还需要一个函数来根据提供的变量选择合适的函数。这是可能的解决方案之一

def pythagoras(*, a=None, b=None, c=None):
    ''' Computes a side of a right triangle '''

    # Validate
    if len([i for i in (a, b, c) if i is None or i <= 0]) != 1:
        raise SystemExit("ERROR: you need to define any of two non-negative variables")

    # Compute
    if a is None:
        return (c**2 - b**2)**0.5
    elif b is None:
        return (c**2 - a**2)**0.5
    else:
        return (a**2 + b**2)**0.5

为了看到与约束编程方法的区别，我将展示一个“问题”的示例，该问题具有四个变量和一个不由直线数学方程式表示的约束。这是一个转换器，可以更改字符的大小写（小写到/从大写/大写）并返回每个字符的 ASCII 码。因此，在任何时候，转换器都知道所有四个值并立即对任何更改做出反应。创建此示例的想法完全受到 John DeNero 的华氏-摄氏度转换器的启发。

这是一个约束系统的图表

所表示的“问题”被转换为一个约束系统，该系统由节点（约束）和连接器（变量）组成。连接器为获取和设置值提供接口。它们还检查变量的域。当一个值发生变化时，该特定连接器会将其连接的所有节点通知有关该变化。节点反过来满足约束，计算新值，并通过“请求”它们设置新值，将它们传播到系统中的其他连接器。传播是使用消息传递技术完成的，这意味着连接器和节点接收消息（同步）并做出相应的反应。例如，如果系统在“大写字母”连接器上收到 A 字母，则其他三个连接器根据节点上定义的约束提供适当的结果：97、a 和 65。不允许在该连接器上设置任何其他小写字母（例如，b），因为每个连接器都有自己的域。

当所有连接器都链接到由约束定义的节点时，系统就完全设置好并准备好在四个连接器中的任何一个上获取值。一旦设置好，系统就会自动计算并在其余连接器上设置值。无需检查设置了哪个变量以及应该调用哪些函数，就像命令式方法中需要的那样——这对于少数变量来说相对容易实现，但在几十个或更多变量的情况下会变得有趣。

它是如何工作的

完整的源代码在我的 GitHub 仓库中可用。我将深入研究一些细节来解释系统是如何构建的。

首先，通过给它们名称并将域设置为一个参数的函数来定义连接器

import constraint_programming as cp

small_ascii = cp.connector('Small Ascii', lambda x: x >= 97 and x <= 122)
small_letter = cp.connector('Small Letter', lambda x: x >= 'a' and x <= 'z')
capital_ascii = cp.connector('Capital Ascii', lambda x: x >= 65 and x <= 90)
capital_letter = cp.connector('Capital Letter', lambda x: x >= 'A' and x <= 'Z')

其次，将这些连接器链接到节点。有两种类型：code（将字母来回转换为 ASCII 码）和 aA（将小写字母转换为大写字母，反之亦然）

code(small_letter, small_ascii)
code(capital_letter, capital_ascii)
aA(small_letter, capital_letter)

这两个节点在应该调用哪些函数方面有所不同，但它们都派生自通用的约束函数

def code(conn1, conn2):
    return cp.constraint(conn1, conn2, ord, chr)

def aA(conn1, conn2):
    return cp.constraint(conn1, conn2, str.upper, str.lower)

每个节点只有两个连接器。如果第一个连接器上有更新，则调用第一个函数来计算另一个连接器（变量）的值。如果第二个连接器的值发生变化，也会发生同样的事情。例如，如果 code 节点在 conn1 连接器上获得 A，则将使用函数 ord 来获取其 ASCII 码。反之亦然，如果 aA 节点在 conn2 连接器上获得 A，则它需要使用 str.lower 函数来在 conn1 上获得正确的小写字母。每个节点都负责计算新值并“发送”消息到另一个连接器，表明有新值要设置。此消息通过请求设置新值的节点的名称以及新值来传达。

def set_value(src_constr, value):
    if (not domain is None) and (not domain(value)):
        raise ValueOutOfDomain(link, value)
    link['value'] = value
    for constraint in constraints:
        if constraint is not src_constr:
            constraint['update'](link)

当连接器收到 set 消息时，它运行 set_value 函数来检查域，设置新值，并向另一个节点发送“update”消息。这只是一个通知，表明该连接器上的值已更改。

def update(src_conn):
    if src_conn is conn1:
        conn2['set'](node, constr1(conn1['value']))
    else:
        conn1['set'](node, constr2(conn2['value']))

然后，被通知的节点请求连接器上的这个新值，计算另一个连接器的新值，依此类推，直到整个系统发生变化。这就是传播的工作原理。

但是消息传递是如何发生的呢？它是通过访问字典的键来实现的。函数（连接器和约束）都返回一个调度字典。这样的字典包含消息作为键，闭包作为值。通过访问一个键，例如 set，字典返回函数 set_value（闭包），该函数可以访问“连接器”函数的所有局部名称。

# A dispatch dictionary
link = { 'name': name,
         'value': None,
         'connect': connect,
         'set': set_value,
         'constraints': get_constraints }

return link

将字典作为返回值使得创建多个闭包（函数）成为可能，这些闭包可以访问相同的局部状态以进行操作。然后，可以通过使用键作为消息类型来调用这些闭包。