Альфа-алгоритм - Alpha algorithm

В α-алгоритм алгоритм, используемый в процесс добычи, направленный на реконструкцию причинности из набора последовательность событий Впервые он был выдвинут ван дер Аалст, Weijters и Măruşter.^[1] С тех пор было представлено несколько его расширений или модификаций, которые будут перечислены ниже.

Он строит P / T сети со специальными свойствами (сети рабочего процесса ) из журналов событий (которые могут быть собраны ERP система). Каждый переход в сети соответствует наблюдаемой задаче.

Краткое описание

Алгоритм ведет журнал рабочего процесса ${ Displaystyle W substeq T ^ {*}}$ в качестве входных данных и приводит к построению сети рабочего процесса.

Это достигается путем изучения причинно-следственных связей между задачами. Например, одна конкретная задача может всегда предшествовать другой конкретной задаче в каждой трассировке выполнения, что может быть полезной информацией.

Используемые определения

А трассировка рабочего процесса или же трассировка выполнения это нить над алфавит ${ displaystyle T}$ из задачи.
А журнал рабочего процесса представляет собой набор трассировок рабочего процесса.

Описание

Декларативно алгоритм можно представить в следующем виде: определены три набора задач:

${ displaystyle T_ {W}}$ это совокупность всех задач, которые встречаются хотя бы в одной трассе
${ displaystyle T_ {I}}$ - это набор всех задач, которые выполняются трассировкой - изначально
${ displaystyle T_ {O}}$ - это набор всех задач, которые происходят в конце трассы

Определены основные упорядочивающие отношения ( ${ displaystyle succ _ {W}}$ во-первых, последние три могут быть построены из него)

${ displaystyle a succ _ {W} b}$ если только ${ displaystyle a}$ непосредственно предшествует ${ displaystyle b}$ в некотором роде
${ displaystyle a rightarrow _ {W} b}$ если только ${ displaystyle a succ _ {W} b wedge b not succ _ {W} a}$
${ displaystyle a # {} _ {W} b}$ если только ${ displaystyle a not succ _ {W} b wedge b not succ _ {W} a}$
${ displaystyle a Vert _ {W} b}$ если только ${ displaystyle a succ _ {W} b wedge b succ _ {W} a}$

Места открыты. Каждое место обозначается парой наборы задачи, чтобы количество мест оставалось низким.

${ displaystyle Y_ {W}}$ $Y_ {W}$ это множество всех пар ${ Displaystyle (А, В)}$ $(А, Б)$ максимальных наборов задач таких, что
- Ни один ${ Displaystyle А раз А}$ и ${ displaystyle B times B}$ содержать любых членов ${ displaystyle succ _ {W}}$ и
- ${ displaystyle A times B}$ это подмножество ${ displaystyle rightarrow _ {W}}$
${ Displaystyle P_ {W}}$ содержит одно место ${ displaystyle p _ {(A, B)}}$ для каждого члена ${ displaystyle Y_ {W}}$ , плюс место ввода ${ displaystyle i_ {W}}$ и место вывода ${ displaystyle o_ {W}}$

Отношение потока ${ displaystyle F_ {W}}$ представляет собой объединение следующего:

${ Displaystyle {(а, п _ {(С, В)}) | (А, В) в Y_ {W} клин а в А }}$
${ Displaystyle {(п _ {(А, В)}, б) | (А, В) в Y_ {W} клин б в В }}$
${ displaystyle {(i_ {W}, t) | t in T_ {I} }}$
${ Displaystyle {(т, я_ {O}) | т ин Т_ {O} }}$

Результат

а Сеть Петри структура ${ Displaystyle альфа (W) = (P_ {W}, T_ {W}, F_ {W})}$
с одним местом ввода ${ displaystyle i_ {W}}$ и одно место вывода ${ displaystyle o_ {W}}$
потому что каждый переход ${ displaystyle T_ {W}}$ находится на ${ displaystyle F_ {W}}$ -путь от ${ displaystyle i_ {W}}$ к ${ displaystyle o_ {W}}$ , это действительно сеть рабочего процесса.

Характеристики

Это можно показать ^[2] что в случае полного журнала рабочего процесса, созданного звук SWF net, порождающую его сеть можно реконструировать. Полный означает, что его ${ displaystyle succ _ {W}}$ отношение максимальное. это нет требовал наличия всех возможных следов (что было бы счетно бесконечным для сети с петлей).

Ограничения

Сети общего рабочего процесса могут содержать несколько типов конструкций. ^[3] которые α-алгоритм не может открыть заново.

Строительство ${ displaystyle Y_ {W}}$ занимает экспоненциальное время в количестве задач, поскольку ${ displaystyle succ _ {W}}$ не ограничен и произвольные подмножества ${ displaystyle T_ {W}}$ должны быть рассмотрены.

Расширения

Например ^[4]^[5]