2。3 高层次转换操作的具体种类 5

2。4 高层次转换操作面临的问题 6

3 算法的理论分析 8

3。1 算法的一般描述 8

3。2 移动操作的具体探究 9

3。3QUINE-McCLUSKEY算法 11

3。4 转换操作中的空活动 13

4 工具设计实现以及实验分析 15

4。1 模块的整体框架设计 15

4。2 建模过程 16

4。3 科学工作流差异识别工具的实现 18

4。4 数据测试与分析 20

4。5 算法存在的缺陷和不足 22

5 课题的展望和相关工作 23

5。1 相关工作 23

5。2 对未来的展望 23

结论 24

致谢 25

参考文献 26

II 本科毕业设计说明书

1 引言

本科毕业设计说明书 第 1 页

业务过程模型（process model）之间的差异对比已经被证明是一个 NP-Hard 问题[15]。传 统的过程模型差异识别算法是基于边和结点操作的，操作复杂且稳定性差，现有的算法提出 了高层次转换操作（high-level change operation）[1]并且和数字电路中的 Quine-McCluskey 算 法巧妙地结合了起来[15]，使得过程模型差异识别算法优化了许多。本文基于这种算法来研究 科学工作流（scientific workflow）之间的差异，把它们抽象成过程模型并且计算二者之间的 编辑距离，并且采用多个样例佐证算法的正确性。由于最短编辑距离问题是一个 NP-Hard 问 题，其中涉及到状态空间爆炸以及搜索权衡，所以其他的算法研究本文不深入讨论。

1。1 课题背景

如今全球各地的商业活动变得越来越动态化和规范化，企业需要适应一种“商业过程模 式”才能在企业间竞争中获得优势。这要求各企业要遵循 PAISs[4]（Process-Aware Information Systems）以对付在商业环境中频繁的变动[19]。商业团体需要不断地重新设计他们的商业过 程。另外，为了在商业市场中更有竞争力量，它们需要不断地优化其商业执行过程。PAISs 允许用户在要求范围内脱离原先定义的过程模型。过去的几年中，针对业务过程灵活性上进 行的研究给我们提供了一种理论基础[2][12]，就是在 PAISs 中进行动态过程转换以减少过程转 换的耗费。而过程灵活性是一种只需要转换部分元素而保持其他元素不变的性质，符合业务 过程的稳定性要求。这些研究基础对计算两个基于高层次转换操作的过程模型之间的最小差 异来说是非常重要的。例如，如果我们需要从一个模型转换成另一个模型，理论上来说我们 可以用最少的转换操作得到我们想要的结果，这样我们就不用重新定义一个新的过程模型， 只需要在原过程模型中执行高层次转换操作即可。PAISs 现有的算法有 ADEPT[12]，WASA[21] 还有 TRAM[7] 等。