5달 만에 돌아온 Alignment based conformance checking 포스팅. 이번 포스팅은 저번 Alignment based conformance checking이란? (Alignment를 이용한 적합도 검증) - 심화편 (2) (synchronous product net이란?) 포스팅에 이은 마지막 alignment based conformance checking 포스팅이다. 저번 포스팅에서 우리는 synchronous product net을 어떻게 구하고, 이를 이용해 어떻게 optimal alignment를 계산하는지에 대해 알아보았다. 하지만 저번 포스팅에서는 optimal alignment를 구할 때 휴리스틱한 방법을 사용했다. 이번 포스팅에서는 이를 shortest path algorithm을 이용하여 계산하는 방법에 대해 알아보겠다.
우선, 저번 포스팅에서 구한 synchronous product net을 살펴 보자. (이를 구하는 과정은 생략한다. 저번 포스팅을 참고하자.)
여기서 optimal alignment를 구하기 위해 우리는 초록색의 synchronous product net의 transition을 최대한 많이 이용하고, 노란색의 event net이나 보라색의 process net에만 있는 transition을 최소한으로 이용해야 한다. 저번 포스팅에서처럼 그냥 직관에 따라, synchronous product net을 최대한 이용하도록 alignment를 구해도 되지만, 이는 정확한 방법이라고 할 수 없다. 그래서 우리는, 위 페트리 넷을 이용해 Reachability Graph를 구한다. 위 페트리 넷의 place의 marking이 state, 트랜지션이 transition이 되는 reachability graph를 구하는 것이다. 그 결과는 다음과 같다. (이 과정은 생략한다. 위 포스팅을 참고하면 된다.)
여기서 initial state는 [p1, p1'], final state는 [p5', p4]가 된다. 여기서 우리는 위에서 말했듯이 초록색의 synchronus move를 가장 많이 사용하고, 노란색의 move on log와 보라색의 move on model을 가장 적게 사용하는 방향으로 state를 진행해야 한다. 이러한 경로를 어떻게 찾을 수 있을까? 이 때 사용하는 것이 바로 shortest path algorithm이다.
Shortest path problem은 출발지와 목적지가 정해져 있을 때 가장 비용이 적게 드는 경로를 찾는 것을 말한다. 이에는 A*, Dijkstra 등 다양한 알고리즘이 있다. (각 알고리즘에 대한 설명은 생략한다.) 우리가 위의 reachability graph에서 synchronus move와 invisible move들의 cost를 0으로, move on log와 move on net의 cost를 1로 하여 shortest path를 찾는다면 이것이 우리가 원하는 optimal alignment가 될 것이다. initial state로부터 각 state로 가는 최소의 cost를 그림으로 나타내면 다음과 같다.
즉, 위 예시에서 최적의 경로 (shortest path)는 [p1', p1] > [p2', p2] > [p3', p2] > [p4', p3] > [p4', p2] > [p5', p3] > [p5', p4]의 경로가 되고 cost는 1이다. 이것이 우리의 optimal alignment의 경로가 되는 것이다.
이번 포스팅에서는 저번 포스팅에 이어 shortest path algorithm을 이용하여 optimal alignment를 찾는 방법에 대해 알아보았다. 이것으로 alignment based conformance checking에 대한 기본적인 내용은 모두 다루었다.
최근댓글