cuda编程示例_约束编程示例-白红宇

cuda编程示例_约束编程示例

阅读量：2526 次

发布时间：2019-05-11

本文共 6597 字，大约阅读时间需要 21 分钟。

cuda编程示例

解决计算问题的方法有很多种。您可以通过尽可能多地计算可能性来“蛮力”解决问题，或者可以采用程序方法并仔细建立影响正确答案的已知因素。在，问题被视为对可能是有效解决方案的一系列限制。此范例可用于有效解决一组问题，这些问题可以转换为变量和约束或表示为数学方程式。这样，它与约束满足问题（）有关。

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

例如，我们以毕达哥拉斯定理为例： 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码。因此，转换器在任何时候都知道所有四个值，并对任何变化立即做出React。创建此示例的想法完全受到John DeNero的启发。

这是约束系统的图：

表示的“问题”被转换为一个约束系统，该约束系统由节点（约束）和连接器（变量）组成。连接器提供用于获取和设置值的接口。他们还检查变量的域。当一个值更改时，该特定的连接器会将该更改通知所有连接的节点。节点依次满足约束条件，计算新值，然后通过“询问”它们以设置新值，将它们传播到系统中的其他连接器。传播使用消息传递技术完成，这意味着连接器和节点（同步）获取消息并做出相应React。例如，如果系统在“大写字母”连接器上获得A字母，则其他三个连接器将根据在节点上定义的约束提供适当的结果：97，a和65。不允许将其他下限设置为更低该连接器上的-case字母（例如b），因为每个连接器都有自己的域。

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

这个怎么运作

完整的源代码可在我的。我将深入研究一些细节，以解释系统的构建方式。

首先，通过给连接器命名并根据一个参数设置域来定义连接器：

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_value函数以检查域，设置新值并将“更新”消息发送到另一个节点。这只是该连接器上的值已更改的通知。

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

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

为什么要使用约束编程？

约束编程可以使您对困难的问题有新的认识。不是在每种情况下都可以使用的东西，但是在某些情况下，它可能会为解决方案打开新的机会。如果您发现似乎很难用代码可靠地解决的方程式，请尝试从另一个角度看待它。如果看似最有效的角度是约束编程，那么现在您将有一个如何实现它的示例。

本文最初发表在，经他的许可转载。

翻译自:

cuda编程示例

你可能感兴趣的文章