1。保证了过程模型的健壮性。也就是说作用在一个健壮的过程模型 S 上的高层次转换操 作会产生另一个健壮的过程模型 S'。这个同样适用于我们在图 2。2 中描述的例子。相比之

本科毕业设计说明书 第 5 页 下，使用传统的基元转换操作（例如删除 S 中的一条边）不能保证模型的健壮性。通常，如 果我们不小心额外删除 S 中的一条边，产生的过程模型必然不是健壮的。

2。高层次转换操作比低级转换操作提供更丰富的句法含义。通常，一个高层次转换操作 是建立在基元操作基础上的。图 2。2 运用操作Δ1，这个高层次转换操作需要 15 个基元操作才 能实现（比如删除边，添加边，删除空活动，更新结点类型）。文献综述

3。更重要的一点，从模型 S 转换到模型 S'运用高层次转换操作的操作数大大小于基元操 作需要的操作数，这使得问题研究变得很方便。例如，我们只需要一步移动操作就可以实现 图 2。2 中 S 到 S1 或者 S2 的转换。然而上面也提到了，使用基元转换操作时，从 S 转换到 S1 需 要 15 步操作，而第二个转换操作Δ2 可被看作由 6 个低级转换操作组成的。这个例子同样说 明了改变原语不提供充足的方法去判断两个过程模型之间的差异。因此改变原语不能表示过 程模型转换需要的操作数。

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

上文为了引出病人例子给了一个粗略的定义，现在我们来展开说明一下。现在我们有两 个假设：

①过程模型是块结构的。

②过程模型中所有的活动都是独立的。 那么引言中提到的求出两个过程模型之间编辑距离就可以深入讨论一下了，基于这个编

辑距离，我们会给出一个计算两个过程模型量化相似性（相似度）的公式。显然，如果我们 用肉眼观察并且手动操作，最不需要思考的方法就是把第一个过程模型中所有的元素全部删 掉，然后再把第二个过程模型中所有的元素全部加入，这样的话最多需要|N1|+|N2|（N 表示 过程模型的结点数）步操作。再优化一下，如果两个模型中有相同的结点，那不难理解，我 们只需要|N1|+|N2|-|N1+N2|步操作。但是当过程模型有成百上千个结点的时候这种做法无疑 是不可取的。现在我们的研究重心是在保证过程模型健壮性的前提下让过程模型 S 到 S'的转 换操作最小化。来~自,优^尔-论;文*网www.youerw.com +QQ752018766-

我们用 P 表示过程模型集合，定义 S=(N,E,。。。)∈P 为一个健壮的过程模型。N 表示活动 集合，E 表示活动之间的边集合。为了限制范围，我们假定它们都是块结构的。我们假定通 过应用一系列高层次转换操作成功完成一个过程转换。这样的转换操作通过变更活动集合和 它们的优先关系修改最初的过程模型。因此，每个转换操作的使用会产生一个新的过程模 型。

本科毕业设计说明书

表 2。1 中详细描述了高层次转换操作的具体操作种类和操作量，其中包括四个转换操作，添 加、删除、移动和替代，事实证明运用的操作越多反倒对状态空间爆炸问题不利，而替代操 作可以使用前三种操作代替，所以为了简化研究本文只使用前三种操作。其中移动操作是我 们研究的关键，也是过程模型相似性 NP 问题研究的重点。如果我们遇到了一些额外的约束 条件，表 2。1 中的操作在同样适用。尽管我们描述的转换操作是基于 ADEPT 框架[12] 讨论 的，但是一般地它们也同样适用于其他的过程转换模型。例如，表 2。1 中的转换操作也可以 遵循生命周期继承规则扩展到 Petrinet[16]的研究中。本文中提到的 ADEPT 也是我们本文研究 方法的基础。根据定义在 S 上的控制流概念，在过程模型 S 上的一个路径 t 表示活动 ai∈N 上的一个有效的执行序列 t≡<a1,a2,。。。,ak>。过程模型 S 上能产生的所有路径构成了路径集合 TS。t(a<b)表示在路径 t≡<a1,a2,。。。,ak>当且仅当∃i<j:ai=a∧aj=b 上两个活动 a 和 b 之间的优先 关系。在这里，我们不考虑有空活动的路径。最终，我们定义相同的两个过程模型是等价的 也就是说，S≡S'当且仅当 TS≡TS'。 SWF科学工作流模型的差异识别(4):http://www.youerw.com/jisuanji/lunwen_89354.html