Как реализовать FSM-конечный автомат в Java

Ответ 1

Сердцем конечного автомата является таблица перехода, которая принимает состояние и символ (то, что вы вызываете событие) в новое состояние. Это всего лишь двухзначный массив состояний. Для здравомыслия и безопасности типов объявите состояния и символы как перечисления. Я всегда добавляю член "длины" каким-то образом (зависит от языка) для проверки границ массива. Когда у меня есть FSM с ручной кодировкой, я форматирую код в формате строк и столбцов с помощью пробелов. Другими элементами конечной машины являются начальное состояние и множество принимающих состояний. Наиболее непосредственная реализация множества принимающих состояний представляет собой массив логических элементов, индексированных состояниями. Однако в Java перечисления являются классами, и вы можете указать аргумент "accepting" в объявлении для каждого перечисленного значения и инициализировать его в конструкторе для перечисления.

Для типа машины вы можете записать его как общий класс. Для этого потребуется два аргумента типа: один для состояний и один для символов, аргумент массива для таблицы перехода, одно состояние для начального. Единственная другая деталь (хотя она критическая) заключается в том, что вам нужно вызвать 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
    }
};

Ответ 2

EasyFSM - это динамическая библиотека Java, которая может использоваться для реализации FSM.

Вы можете найти документацию для этого: Конечный автомат в Java

Кроме того, вы можете загрузить библиотеку по адресу: Библиотека Java FSM: DynamicEasyFSM

Ответ 3

Хм, я бы предположил, что вы используете Flyweight для реализации состояний. Цель: Избегайте нехватки памяти большого количества небольших объектов. Государственные машины могут быть очень, очень большими.

http://en.wikipedia.org/wiki/Flyweight_pattern

Я не уверен, что вижу необходимость использования состояния шаблона проектирования для реализации узлов. Узлы в конечном компьютере не имеют состояния. Они просто соответствуют текущему символу ввода доступным переходам из текущего состояния. То есть, если я не полностью забыл, как они работают (что является определенной возможностью).

Если бы я его кодировал, я бы сделал что-то вроде этого:

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;
    }
  }
}

Это создает объекты State на основе необходимости использования. Это позволяет использовать гораздо более эффективный базовый механизм для хранения фактического конечного автомата. Тот, который я использую здесь (Map (Integer, Map (Symbol, Integer))), не особенно эффективен.

Обратите внимание, что на странице Википедии основное внимание уделяется случаям, когда многие аналогичные объекты совместно используют похожие данные, как это имеет место в реализации String на Java. На мой взгляд, Flyweight является чуть более общим и охватывает любое создание по требованию объектов с коротким сроком службы (используйте больше CPU для экономии на более эффективной базовой структуре данных).

Ответ 4

Рассмотрим легкую, легкую библиотеку Java EasyFlow. Из своих документов:

С EasyFlow вы можете:

• реализовать сложную логику, но сохранить свой код простым и чистым.
• обрабатывать асинхронные вызовы с легкостью и элегантностью.
• избегать concurrency с помощью метода программирования, управляемого событиями
• избежать ошибки StackOverflow, избегая рекурсии
• упростить проектирование, программирование и тестирование сложных Java-приложений.

Ответ 5

Вы можете реализовать машину конечного состояния двумя способами.

Вариант 1:

Конечный автомат с заранее определенным рабочим процессом: рекомендуется, если вы знаете все состояния заранее, а конечный автомат почти исправлен без каких-либо изменений в будущем

• Определите все возможные состояния в приложении

• Определите все события в приложении

• Определите все условия в вашем приложении, которые могут привести к переходу состояния

• Возникновение события может привести к переходу состояния

• Создайте машину конечного состояния, решив рабочий процесс состояний и переходов.

  Например, если событие 1 встречается в состоянии 1, состояние будет обновляться, и состояние машины все еще может находиться в состоянии 1.

  Если событие 2 происходит в состоянии 1, при некоторой оценке состояния система переместится из состояния 1 в состояние 2

Этот проект основан на шаблонах состояний и контекста.

Посмотрите на прототипы конечных машин.

Вариант 2:

Поведенческие деревья: рекомендуется, если частые изменения в рабочем процессе конечного автомата. Вы можете динамически добавлять новое поведение, не разбивая дерево.

Базовый класс Task предоставляет интерфейс для всех этих задач, задачи листа - это только что упомянутые, а родительские задачи - это внутренние узлы, которые решают, какую задачу выполнить дальше.

Задачи имеют только логику, необходимую для того, чтобы на самом деле делать то, что от них требуется, вся логика принятия решения о запуске задачи или нет, если она нуждается в обновлении, если она завершена с успехом и т.д., сгруппирована в классе TaskController и добавлена ​​композицией.

Декораторы - это задачи, которые "украшают" другой класс, обертывая его и предоставляя ему дополнительную логику.

Наконец, класс Blackboard - это класс, принадлежащий родительскому AI, на который ссылается каждая задача. Он работает как база данных знаний для всех задач листа

Посмотрите на статью Jaime Barrachina Verdia для более подробной информации

Ответ 6

Я разработал и реализовал простой пример конечного автомата с 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"));
    }

}

Полный пример на Github