Page 178 - 《软件学报》2020年第10期

3154 Journal of Software 软件学报 Vol.31, No.10, October 2020

Algorithm2. Generating core.
Input: All complete simple routes R;
Output: Core c;
19. define returned core c=(C,c 0 ,C e ,A,Δ);
20. for each complete simple route r in R do
21. get the length len of complete simple route r
22. for i∈[0..len−1] do
23. get from=r[i], task=r[i+1], and to=r[i+1];
24. if from is not in C then
25. add from to C;
26. end if
27. if to is not in C then
28. add to to C;
29. end if
30. if task is not in A then
31. add task to A;
32. end if
33. if (from, task, to) is not in Δ then
34. add (from, task, to) to Δ;
35. end if
36. end for
37. end for
38. set the srart state to c 0 ;
39. for each elem e in C do
40. if e is c e then
41. add e to C e ;
42. end if
43. end for
44. return c;
算法 2 的基本思想是通过将完整的简单路径中的格局集和格局迁移集分别设置为核中的格局集和格局迁
移集,从而构建核.算法 2 的时间复杂度取决于完整的简单路径的条数及其长度.不妨设完整的简单路径条数为
m,每条完整的简单路径的长度为 n,则算法 2 的时间复杂度为 O(m×n).
特别需要说明的是:由于完整的简单路径中记录了循环结构,因此最终构建的核中循环结构不会丢失.由此
可以推断,对于部分正确的协同业务过程,通过算法 2 生成的核中只含有此协同业务过程中所有完整的简单路
径,见定理 2.
定理 2. 给定部分正确的协同业务过程 CBP,CBP 中含有的所有完整的简单路径记为 R c .设 c 是根据 R c 构
建的核,则对于 CBP 中任意完整的简单路径 r c ,c 中也存在 r c ,反之亦然.
n a
1 a
证明:充分性.设 r c =c 0 ⎯⎯→ c 1 …c n−1 ⎯⎯→ c n 为 CBP 中任意一条完整的简单路径 r c ,分下面两种情况讨论.
1) 若 r c 满足∀1≤i,j≤n∧j≠i,c i ≠c j ,可知 r c 为完整的简单路径,推出 r c ∈R c .由算法 2 可知,由 R c 构建后的 c 中
必定存在格局迁移关系集合{(c 0 ,a 1 ,c 1 ),…,(c n−1 ,a n ,c n )}⊆Δ,由此格局迁移关系可生成路径 r c .
k a
i a +
2) 若 r c 中存在路径片段 c i ⎯⎯⎯→ c i+1 …c j …c k−1 ⎯⎯→ c k (1≤i,j,k≤n),满足 c i =c j =c k ∧∀i<x,y<k∧x≠{i,j,k}∧y≠
1
j a
i a +
{i,j,k}∧x≠y,c x ≠c y ,可知 r c 中存在重复次数大于 2 的循环结构 η=c i ⎯⎯⎯→ c i+1 … ⎯⎯→ c j ,则在 r c 中使用 c i 替换掉
1