没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记48(2001)网址: http://www.elsevier.nl/locate/entcs/volume48.htmlpp. 1- 12AJACS设计,另一个Java约束编程框架1萨尔瓦多·阿布雷乌3DepartmentodeInforma′ticaUniversidadedeE′voraE′vora,葡萄牙摘要本文介绍了一个用Java语言实现的并发约束编程工具包AJACS(AnotherJa vaConstraint ProgrammingS它是我们以前在Java中实现约束编程习惯用法GC [5]的工作的继承者我们声称AJACS提供了一个非常灵活的工具包,用于一般应用程序,可能会受益于约束编程技术。我们还声称,AJACS允许编码的CSP问题,其解决方案是服从一个几乎无边界的并行化。关键词:约束逻辑程序设计,并发约束,Java.1介绍将编程方法与特定的现有语言相结合可能会有所帮助,因为结果将继承宿主语言在CLP [7]的例子中,Prolog最大的缺陷之一这方面严重限制了已知的技术被应用于制造设备的容易性。1作者要感谢匿名评审对本文早期版本的建设性审查。UnivereducadedeE'vora、CENTRIA和FundacaodaCieTecnologia(根据合同PRAXISP/EEI/10191/98“O AR”)是众所周知的感谢他们对本文所述工作的支持2电子邮件地址:lsf@di.uevora.pt3电子邮件:spa@di.uevora.pt2001年由ElsevierScienceB出版。 诉 操作访问和C CB Y-NC-ND许可证。费雷拉和阿布鲁2有用的(CLP)可以被证明,并实际投入使用,在非专业化的环境。Java语言被吹捧为在源代码和编译对象级别都具有高度的机器独立性,从而为应用程序的开发提供了一个有吸引力的平台这方面已经稍微受到了可用Java实现的效率的阻碍,但是随着更好的编译器和运行时支持系统的出现,这种情况正在迅速改变JVM(Java虚拟机)实现的效率低下似乎阻碍了使用它来实现其他编程范式,特别是那些关注(相对)效率的编程范式。然而,在CLP的情况下,拥有广泛的二进制兼容平台的吸引力似乎解决了这些系统所面临的困难,并且之前提到过:缺乏广泛使用(易于安装)的实现。只要考虑到大多数Web浏览器都有一个内置的Java运行时系统,而不管它们运行在什么硬件/软件平台上。这种情况已经通过约束编程包Ilog:Solver [9]得到了承认和处理,尽管是用不同的语言(C++)。我们的目标是进一步采用这种方法,并在Java中构建一个类似但改进的系统在这个阶段,原始效率(根据基准测试结果)不是我们的目的,我们宁愿设计和实现一个Java语言的另一个特性是它包含了高级图形工具包,这些工具包共享了该语言这些工具包,特别是Java基础类或Swing,将使我们能够构建复杂的编程环境,并更容易地支持我们在可视化编程语言方向的研究。在我们之前的工作中[5],我们提出了一个Java约束编程工具包,与经典的CLP实现(如Ilog:Solver [9],CHIP [4]或CLP(FD)[2])非常相似。虽然GC相对容易编程,但在Java环境中复制CLP搜索过程的负担很重,特别是• 它跟踪变量• GC中使用的数据结构并不真正适合并行化,这缩短了我们进行并发和分布式实现的尝试。• GC实现了变量域的几种表示意识到这些缺点,我们决定重新开始,在CC上工作费雷拉和阿布鲁3类似[10]的方法,提供了一个基于Java的并发约束编程工具包我们的一些主要目标是:• 自动迁移值的表示• 提供一种在并发和并行执行设置中更容易编程的设置• 避免完全尾随这个目标可以被认为是前一个目标的一部分(启用并行执行),因为尾随的目的是用以前的值覆盖变量• 提供一个框架,使程序员可以很容易地指定不同的搜索策略,同时为最常见的搜索过程提供合理的实现。AJACS的体系结构围绕着几个关键概念,这些概念将在下面的部分中描述。本文其余部分的结构如下:第2节给出了AJACS中每个主要概念的形式化描述。在第3节中,我们描述了Java实现的结构。第4节更详细地讨论了我们如何处理探索搜索空间的问题最后,第5节在AJACS和其他方法之间进行了比较平衡,在第6节中,我们总结并讨论了一些计划中的发展。2概念标记约定:单个对象将用小写字母表示,相同类型的对象集将用相应的大写字母表示2.1值一个值表示一个变量的域的子集被指定为奇异值的一组元素。如果一个值只包含一个奇异值,则称该值为基我们将使用字母u来指定一个值,而值的集合将由U表示。2.2可变AJACS中没有明确的变量概念这些抽象地被认为是位于一组存储中相同索引处的值的集合(关于存储的定义,请参见下一费雷拉和阿布鲁4···2.3店存储区是值的索引集合。目标是,在求解CSP时,将创建几个类似的存储(关于值的数量),其中由所有存储中的相同索引给出的值集表示一个变量。由于一个存储是通过应用约束传播步骤(见下文)从另一个存储获得的,因此存储必须包含对其祖先的引用在初始存储的特殊情况下,祖先是unfined。存储的每一行4都与特定变量的值相关此外,由于存储是通过限制变量的值从祖先存储获得的,因此每个存储必须提及其哪些行已被限制,商店s的定义是:其中:s(U,i,sp)• U=(u1,u2,...,u n),其中u i是与存储行i相关联的值(在当前存储中)。• i是变量s的索引,该变量的域已在s所有存储器SJ=(UJ,IJ,sjp)/sjp=s。• sp是%s2.4约束约束是问题中出现的变量之间的关系。AJACS的约束概念期望这些是负责将对一个变量所做的更改传播到存储中发生的其余变量的机制约束c可以定义为对:c(f,(i1,i2···in))其中f = λx1x2. x n·e是一个布尔值函数,范围覆盖存储中的变量集。 这个函数应该将(i1,i2in)映射到当约束对于由存储行i1、i2···in指示的值成立时为真,并且当所得到的存储不一致时为假元组(i1,i2···in)称为约束2.5问题CSP由问题概念建模,问题概念由一组具有相关初始域(即,存储)以及对这些变量的一组问题被公式化的目的是获得它的解即与约束集一致的问题变量的基础值集4我们将使用费雷拉和阿布鲁5在AJACS中,解决方案是从存储中获得的,因此存储属于我们对问题的表述。问题p定义为:p= p(sinit,C,Cv)其中:• sinit=(U,−,−)是初始存储。• C={c1,c2···ck}是我们要用来求解CSP的约束集这些引用sinit中的存储行。• Cv={(i,CiJ)/i≤#U,CiJ={(cj,n)/cj=(f,X)∈Cv=Xn}}.非正式地,Cv是由存储线(即,的东西指定一个问题变量)和它发生的一组约束后一个集合实际上是由对组成的,其中我们有一个特定的约束和约束参数的索引此组件的目的是指示变量出现的约束集。问题的初始存储由变量的初始值获得请注意,问题中的所有存储都具有相同的结构。2.6搜索和搜索策略搜索的概念体现了这样一个过程,即给定一个问题,解决方案(即全地面商店)。搜索过程可以被认为是搜索步骤的重复应用,直到找到解或搜索空间耗尽。 为了与我们尽可能灵活的目标保持一致,搜索过程可以是顺序的或并行的,与搜索步骤的性质无关。“搜索步骤”可以定义为搜索策略或简称策略所规定的具体行动。策略应用于计算的状态即存储,并在搜索过程中指定其后继状态寻找后继商店需要决定:• 选择其余非地面5个变量中的哪一个,以及:• 对于选定的变量,它的域将如何减少。通常这意味着决定它将采用什么样的奇异值。此值必须始终是变量原始域的子集为了实现这些目标,策略e可以定义为:e(fv,fu)其中,fv是从s中选择要修改的变量的函数,fu是选择上述变量的特定值的函数。5地面变量已经有了单例域,因此不容易细分。费雷拉和阿布鲁6--∈变量将在新存储中使用这些函数是每个策略特有的,必须按以下方式键入:fv:s<$→ifu:(s,i,j)<$→u其中i是存储中的变量(的索引),v是奇异值,j是其解释取决于策略的特定实例fv和fu)。例如,搜索策略e0=(fv,fu),用于深度优先和广度优先搜索,它选择存储中的任何非基础变量并迭代其奇异值,可以由下式给出fv(s)=i/U= vars(s)#Ui>1fu(s,i,j)=u/u={x}<$x= nth(Ui,j)其中vars是变量提取函数,nth(u,j)是第j个单个从定义域u指定的集合中取值。例如,u= 4, 5, 6, 7,第n(u,3)=6.例如,返回第一个解的顺序搜索过程的算法由算法顺序搜索优先(s,C)给出,其中s是存储,C是一组约束。该算法如第6页图1所示该循环适用于此搜索过程的并行版本可以函数顺序搜索优先(s,C)如果然后返回sintn= nums(n);i=fv(s);foreachjUidosJ =fu(s,i,j);propagate(sJ,C);如果
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功