约束编程示例【Programming】

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

图片来源：João Trindade. Modified by 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的Fahrenheit-Celsius转换器的启发。

这是约束系统的图：

表示的“问题”被转换成一个由节点（约束）和连接器（变量）组成的约束系统。连接器提供了一个用于获取和设置值的接口。他们还会检查变量的域。当一个值发生更改时，该特定连接器将更改通知其所有连接的节点。反过来，节点满足约束，计算新值，并通过“请求”它们设置一个新值，将它们传播到系统中的其他连接器。传播是使用消息传递技术完成的，这意味着连接器和节点（同步地）获得消息并相应地作出反应。例如，如果系统在“大写字母”连接器上获得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')

其次，将这些连接器链接到节点。 有两种类型： 代码 （将字母来回转换为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)

每个节点只有两个连接器。 如果第一个连接器上有更新，则将调用第一个函数来计算另一个连接器（变量）的值。 如果第二个连接器的值更改，也会发生相同的情况。 例如，如果代码节点在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值（闭包），该函数可以访问“connector”函数的所有本地名称。

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

将字典作为返回值可以创建多个闭包（函数），并且可以访问相同的本地状态。 然后，可以通过使用键作为消息类型来调用这些闭包。

为什么要使用约束编程？

约束编程可以使您对困难的问题有新的认识。并非在每种情况下都可以使用它，但是在某些情况下它可能会为解决方案打开新的机会。如果你发现自己面对的是一个似乎很难在代码中可靠地解决的问题，试着从另一个角度来看待它。 如果最好的角度是约束编程，那么你现在就有了一个如何实现它的例子。

这篇文章最初发表在 Oleksii Tsvietnov的博客，并在他的允许下转载。