WikiDer > Альфа-алгоритм

В α-алгоритм алгоритм, используемый в процесс добычи, направленный на реконструкцию причинности из набора последовательность событийВпервые он был выдвинут ван дер Аалст, 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}}$ это множество всех пар ${ 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] которые α-алгоритм не может открыть заново.

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Май 2010 г.)

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

Расширения

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Май 2010 г.)

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

Рекомендации