Как реализовать FSM - конечный автомат в Java
У меня есть кое-что для работы, и мне нужна ваша помощь. Мы хотим реализовать FSM - Finite State Machine, чтобы определить последовательность символов (например: A, B, C, A, C) и сообщить, принято ли это.
Мы думаем реализовать три класса: State, Event а также Machine, state класс представляет узел в FSMмы думали реализовать это с State design patternкаждый узел будет выходить из состояния абстрактного класса, и каждый класс будет обрабатывать различные типы событий и указывать переходы в новое состояние. Это хорошая идея на ваш взгляд?
Во-вторых, мы не знаем, как сохранить все переходы. Снова мы думали реализовать это с какой-то map, который содержит начальную точку и получает какой-то вектор со следующими состояниями, но я не уверен, что это хорошая идея.
Я был бы рад получить некоторые идеи о том, как это реализовать, или, может быть, вы можете дать мне несколько отправных точек.
Как мне сохранить FSM, то есть как построить дерево в начале программы? Я гуглил это и нашел много примеров, но ничего, что мне не помогло.
Большое спасибо.
8 ответов
Сердцем конечного автомата является таблица переходов, которая переводит состояние и символ (то, что вы называете событием) в новое состояние. Это просто двухиндексный массив состояний. Для безопасности и безопасности типов объявите состояния и символы как перечисления. Я всегда добавляю член "length" каким-то образом (зависящий от языка) для проверки границ массива. Когда я пишу код FSM вручную, я форматирую код в формате строк и столбцов с использованием пробелов. Другими элементами конечного автомата являются начальное состояние и набор принимающих состояний. Наиболее прямая реализация набора принимающих состояний - это массив логических значений, проиндексированных состояниями. Однако в Java перечисления являются классами, и вы можете указать аргумент "принимать" в объявлении для каждого перечисляемого значения и инициализировать его в конструкторе для перечисления.
Для типа машины вы можете написать его как универсальный класс. Потребуется два аргумента типа, один для состояний и один для символов, аргумент массива для таблицы переходов, одно состояние для начального. Единственная другая деталь (хотя и критическая) заключается в том, что вам нужно вызвать Enum.ordinal(), чтобы получить целое число, подходящее для индексации массива переходов, поскольку у вас нет синтаксиса для непосредственного объявления массива с индексом перечисления (хотя следует быть).
Чтобы выгрузить одну проблему, EnumMap не будет работать для таблицы переходов, потому что требуемый ключ - это пара значений перечисления, а не одно.
enum State {
Initial( false ),
Final( true ),
Error( false );
static public final Integer length = 1 + Error.ordinal();
final boolean accepting;
State( boolean accepting ) {
this.accepting = accepting;
}
}
enum Symbol {
A, B, C;
static public final Integer length = 1 + C.ordinal();
}
State transition[][] = {
// A B C
{
State.Initial, State.Final, State.Error
}, {
State.Final, State.Initial, State.Error
}
};
EasyFSM - это динамическая библиотека Java, которую можно использовать для реализации FSM.
Вы можете найти документацию по этому же адресу: конечный автомат в Java
Также вы можете скачать библиотеку по адресу: Java FSM Library: DynamicEasyFSM
Вы можете реализовать Finite State Machine двумя различными способами.
Опция 1:
Конечный автомат с предопределенным рабочим процессом: рекомендуется, если вы заранее знаете все состояния, и конечный автомат почти исправлен без каких-либо изменений в будущем.
Определите все возможные состояния в вашем приложении
Определите все события в вашем приложении
Определите все условия в вашем приложении, которые могут привести к переходу состояния
Возникновение события может вызвать переход состояния
Создайте конечный автомат, решая рабочий процесс состояний и переходов.
Например, если событие 1 происходит в состоянии 1, состояние будет обновлено, и состояние компьютера все еще может находиться в состоянии 1.
Если событие 2 происходит в состоянии 1, при некоторой оценке состояния система переходит из состояния 1 в состояние 2.
Этот дизайн основан на шаблонах State и Context.
Взгляните на классы прототипов Finite State Machine.
Вариант 2:
Поведенческие деревья: рекомендуется при частых изменениях рабочего процесса конечного автомата. Вы можете динамически добавлять новое поведение, не нарушая дерево.
Базовый класс Task предоставляет интерфейс для всех этих задач, только что упомянутые конечные задачи, а родительские задачи - это внутренние узлы, которые решают, какую задачу выполнять дальше.
Задачи имеют только ту логику, которая им необходима для того, чтобы на самом деле делать то, что от них требуется, вся логика принятия решения о том, была ли запущена задача или нет, нужно ли ее обновлять, если она успешно завершена и т. Д., Сгруппирована в TaskController. класс, и добавил по составу.
Декораторы - это задачи, которые "украшают" другой класс, оборачивая его и придавая ему дополнительную логику.
Наконец, класс Blackboard - это класс, принадлежащий родительскому AI, на который ссылается каждая задача. Он работает как база знаний для всех конечных задач.
Взгляните на эту статью Jaime Barrachina Verdia для более подробной информации
Хм, я бы посоветовал вам использовать Flyweight для реализации состояний. Цель: избегать использования памяти большим количеством мелких объектов. Конечные автоматы могут стать очень, очень большими.
http://en.wikipedia.org/wiki/Flyweight_pattern
Я не уверен, что вижу необходимость использовать шаблон проектирования State для реализации узлов. Узлы конечного автомата не имеют состояния. Они просто сопоставляют текущий входной символ с доступными переходами из текущего состояния. То есть, если я полностью не забыл, как они работают (что является определенной возможностью).
Если бы я кодировал это, я сделал бы что-то вроде этого:
interface FsmNode {
public boolean canConsume(Symbol sym);
public FsmNode consume(Symbol sym);
// Other methods here to identify the state we are in
}
List<Symbol> input = getSymbols();
FsmNode current = getStartState();
for (final Symbol sym : input) {
if (!current.canConsume(sym)) {
throw new RuntimeException("FSM node " + current + " can't consume symbol " + sym);
}
current = current.consume(sym);
}
System.out.println("FSM consumed all input, end state is " + current);
Что бы сделал Flyweight в этом случае? Ну, под FsmNode, вероятно, будет что-то вроде этого:
Map<Integer, Map<Symbol, Integer>> fsm; // A state is an Integer, the transitions are from symbol to state number
FsmState makeState(int stateNum) {
return new FsmState() {
public FsmState consume(final Symbol sym) {
final Map<Symbol, Integer> transitions = fsm.get(stateNum);
if (transisions == null) {
throw new RuntimeException("Illegal state number " + stateNum);
}
final Integer nextState = transitions.get(sym); // May be null if no transition
return nextState;
}
public boolean canConsume(final Symbol sym) {
return consume(sym) != null;
}
}
}
Это создает объекты состояния по мере необходимости. Это позволяет использовать гораздо более эффективный базовый механизм для хранения фактического конечного автомата. Тот, который я здесь использую (Map(Integer, Map(Symbol, Integer))), не особенно эффективен.
Обратите внимание, что страница Википедии посвящена случаям, когда многие похожие объекты совместно используют сходные данные, как в случае реализации String в Java. На мой взгляд, Flyweight является более общим и охватывает любое создание объектов по требованию с коротким сроком службы (используйте больше ресурсов ЦП, чтобы сэкономить на более эффективной базовой структуре данных).
Рассмотрим простую, легкую библиотеку Java EasyFlow. Из их документов:
С EasyFlow вы можете:
- реализовать сложную логику, но сохранить ваш код простым и чистым
- обрабатывать асинхронные вызовы легко и элегантно
- избежать параллелизма, используя подход программирования на основе событий
- избежать ошибки Stackru, избегая рекурсии
- упростить дизайн, программирование и тестирование сложных Java-приложений
Я спроектировал и реализовал простой пример конечного автомата с Java.
IFiniteStateMachine: открытый интерфейс для управления конечным автоматом
такие как добавление новых состояний в конечный автомат или переход в следующие состояния
конкретные действия.
interface IFiniteStateMachine {
void setStartState(IState startState);
void setEndState(IState endState);
void addState(IState startState, IState newState, Action action);
void removeState(String targetStateDesc);
IState getCurrentState();
IState getStartState();
IState getEndState();
void transit(Action action);
}
IState: общедоступный интерфейс для получения информации о состоянии
такие как имя состояния и сопоставления с подключенными состояниями.
interface IState {
// Returns the mapping for which one action will lead to another state
Map<String, IState> getAdjacentStates();
String getStateDesc();
void addTransit(Action action, IState nextState);
void removeTransit(String targetStateDesc);
}
Действие: класс, который вызовет переход состояний.
public class Action {
private String mActionName;
public Action(String actionName) {
mActionName = actionName;
}
String getActionName() {
return mActionName;
}
@Override
public String toString() {
return mActionName;
}
}
StateImpl: реализация IState. Я применил структуру данных, такую как HashMap, чтобы сохранить отображения Action-State.
public class StateImpl implements IState {
private HashMap<String, IState> mMapping = new HashMap<>();
private String mStateName;
public StateImpl(String stateName) {
mStateName = stateName;
}
@Override
public Map<String, IState> getAdjacentStates() {
return mMapping;
}
@Override
public String getStateDesc() {
return mStateName;
}
@Override
public void addTransit(Action action, IState state) {
mMapping.put(action.toString(), state);
}
@Override
public void removeTransit(String targetStateDesc) {
// get action which directs to target state
String targetAction = null;
for (Map.Entry<String, IState> entry : mMapping.entrySet()) {
IState state = entry.getValue();
if (state.getStateDesc().equals(targetStateDesc)) {
targetAction = entry.getKey();
}
}
mMapping.remove(targetAction);
}
}
FiniteStateMachineImpl: реализация IFiniteStateMachine. Я использую ArrayList, чтобы сохранить все состояния.
public class FiniteStateMachineImpl implements IFiniteStateMachine {
private IState mStartState;
private IState mEndState;
private IState mCurrentState;
private ArrayList<IState> mAllStates = new ArrayList<>();
private HashMap<String, ArrayList<IState>> mMapForAllStates = new HashMap<>();
public FiniteStateMachineImpl(){}
@Override
public void setStartState(IState startState) {
mStartState = startState;
mCurrentState = startState;
mAllStates.add(startState);
// todo: might have some value
mMapForAllStates.put(startState.getStateDesc(), new ArrayList<IState>());
}
@Override
public void setEndState(IState endState) {
mEndState = endState;
mAllStates.add(endState);
mMapForAllStates.put(endState.getStateDesc(), new ArrayList<IState>());
}
@Override
public void addState(IState startState, IState newState, Action action) {
// validate startState, newState and action
// update mapping in finite state machine
mAllStates.add(newState);
final String startStateDesc = startState.getStateDesc();
final String newStateDesc = newState.getStateDesc();
mMapForAllStates.put(newStateDesc, new ArrayList<IState>());
ArrayList<IState> adjacentStateList = null;
if (mMapForAllStates.containsKey(startStateDesc)) {
adjacentStateList = mMapForAllStates.get(startStateDesc);
adjacentStateList.add(newState);
} else {
mAllStates.add(startState);
adjacentStateList = new ArrayList<>();
adjacentStateList.add(newState);
}
mMapForAllStates.put(startStateDesc, adjacentStateList);
// update mapping in startState
for (IState state : mAllStates) {
boolean isStartState = state.getStateDesc().equals(startState.getStateDesc());
if (isStartState) {
startState.addTransit(action, newState);
}
}
}
@Override
public void removeState(String targetStateDesc) {
// validate state
if (!mMapForAllStates.containsKey(targetStateDesc)) {
throw new RuntimeException("Don't have state: " + targetStateDesc);
} else {
// remove from mapping
mMapForAllStates.remove(targetStateDesc);
}
// update all state
IState targetState = null;
for (IState state : mAllStates) {
if (state.getStateDesc().equals(targetStateDesc)) {
targetState = state;
} else {
state.removeTransit(targetStateDesc);
}
}
mAllStates.remove(targetState);
}
@Override
public IState getCurrentState() {
return mCurrentState;
}
@Override
public void transit(Action action) {
if (mCurrentState == null) {
throw new RuntimeException("Please setup start state");
}
Map<String, IState> localMapping = mCurrentState.getAdjacentStates();
if (localMapping.containsKey(action.toString())) {
mCurrentState = localMapping.get(action.toString());
} else {
throw new RuntimeException("No action start from current state");
}
}
@Override
public IState getStartState() {
return mStartState;
}
@Override
public IState getEndState() {
return mEndState;
}
}
пример:
public class example {
public static void main(String[] args) {
System.out.println("Finite state machine!!!");
IState startState = new StateImpl("start");
IState endState = new StateImpl("end");
IFiniteStateMachine fsm = new FiniteStateMachineImpl();
fsm.setStartState(startState);
fsm.setEndState(endState);
IState middle1 = new StateImpl("middle1");
middle1.addTransit(new Action("path1"), endState);
fsm.addState(startState, middle1, new Action("path1"));
System.out.println(fsm.getCurrentState().getStateDesc());
fsm.transit(new Action(("path1")));
System.out.println(fsm.getCurrentState().getStateDesc());
fsm.addState(middle1, endState, new Action("path1-end"));
fsm.transit(new Action(("path1-end")));
System.out.println(fsm.getCurrentState().getStateDesc());
fsm.addState(endState, middle1, new Action("path1-end"));
}
}
Что ж, это старый вопрос, но, хотя здесь никто не упомянул, я советую проверить два существующих фреймворка, прежде чем внедрять собственные конечные автоматы.
Одним из них является Spring State Machine, большинство из вас знакомы с Spring framework, который позволяет нам использовать несколько функций Spring, таких как внедрение зависимостей и все остальное, что может предложить Spring.
Он отлично подходит для моделирования жизненного цикла аппарата с такими состояниями, как ИНИЦИАЛИЗАЦИЯ, ЗАПУСК, ОШИБКА, ВОССТАНОВЛЕНИЕ, ВЫКЛЮЧЕНИЕ и т. д., но я вижу, что многие люди пытаются моделировать с его помощью Карту покупок, Систему резервирования, память. След Spring State Machine относительно велик, чтобы моделировать миллионы торговых диаграмм или резервирований.
Еще один недостаток, Spring State Machine, хотя и имеет возможность сохранять себя для длительных процессов, но у него нет никакого механизма для адаптации к изменениям в этих процессах, если вы сохраняете процесс и вам нужно его восстановить, скажем, через 10 дней. если в вашем бизнес-процессе произошло изменение из-за новой версии/требования к программному обеспечению, у вас нет встроенных средств для решения этой проблемы.
У меня есть несколько блогов, blog1 blog2 , демонстрирующих, как вы можете программировать Spring State Machine, особенно на основе модели, если вы хотите это проверить.
В основном из-за недостатков, которые я упомянул, я советую вам сначала посмотреть на другой фреймворк, Akka FSM (Конечный автомат) , который больше подходит с его небольшим объемом памяти, чтобы иметь миллионы и миллионы экземпляров и имеет возможность адаптировать изменяющиеся длительные процессы.
Теперь вы можете разрабатывать фреймворк Akka с Java, но, поверьте мне, из-за отсутствия некоторых языковых элементов вы не хотите читать созданный код, Scala — гораздо более подходящий язык для разработки с Akka. Теперь я слышу, как вы говорите, что Scala слишком сложна, я не могу убедить мой проект вести разработку с помощью Scala, чтобы убедить вас, что все это вариант, я разработал приложение Proof of Concept, используя гибрид Java/Scala со всеми Scala Akka Finite Код конечного автомата, созданный из модели UML, если вы хотите проверить его здесь, ссылки на блоги, blog3 blog4.
Я надеюсь, что эта информация поможет вам.
Вот СУПЕР ПРОСТАЯ реализация / пример конечного автомата с использованием только "if-else", который позволяет избежать всех вышеперечисленных ответов подкласса (взятых из Использование конечных автоматов для сопоставления с образцом в Java, где он ищет строку, которая заканчивается на "@", за которым следуют числа, за которыми следует "#"- см. график состояний здесь):
public static void main(String[] args) {
String s = "A1@312#";
String digits = "0123456789";
int state = 0;
for (int ind = 0; ind < s.length(); ind++) {
if (state == 0) {
if (s.charAt(ind) == '@')
state = 1;
} else {
boolean isNumber = digits.indexOf(s.charAt(ind)) != -1;
if (state == 1) {
if (isNumber)
state = 2;
else if (s.charAt(ind) == '@')
state = 1;
else
state = 0;
} else if (state == 2) {
if (s.charAt(ind) == '#') {
state = 3;
} else if (isNumber) {
state = 2;
} else if (s.charAt(ind) == '@')
state = 1;
else
state = 0;
} else if (state == 3) {
if (s.charAt(ind) == '@')
state = 1;
else
state = 0;
}
}
} //end for loop
if (state == 3)
System.out.println("It matches");
else
System.out.println("It does not match");
}
PS: Не отвечает прямо на ваш вопрос, но показывает, как очень легко реализовать FSM на Java.