我有一些工作需要做，需要你的帮助。我们想要实现一个FSM - 有限状态机，用于识别字符序列（例如：A、B、C、A、C），并判断是否接受该序列。
我们打算实现三个类：State、Event和Machine。
State类表示FSM中的节点，我们打算使用State设计模式来实现它，每个节点将扩展自抽象类state，每个类都将处理不同类型的事件并指示转换到新状态。您认为这是一个好主意吗？
其次，我们不知道如何保存所有转换。我们再次考虑使用某种类型的map来实现，它保存起点并获取某种类型的向量，其中包含下一个状态，但我不确定这是否是一个好主意。
我很高兴听取关于如何实现或者可能给我一些起点的想法。
在程序开始时，我该如何保存FSM（即如何构建树状图）？ 我谷歌了很多例子，但没有找到能帮助我的东西。
非常感谢。
状态机的核心是转换表，它将一个状态和一个符号（你所称之为事件）映射到一个新状态。这只是一个包含两个索引的状态数组。为了确保健壮性和类型安全性，需要将状态和符号声明为枚举类型。我总是以某种方式（特定于语言）添加一个“length”成员变量来检查数组边界。当我手写状态机时，我会使用行列格式化代码并进行空格调整。状态机的其它元素是初始状态和接受状态集合。最直接实现接受状态集合的方法是使用由各个状态对应的布尔值构成的数组。但在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
}
};
EasyFSM是一个动态的Java库，可以用来实现有限状态机。
您可以在以下网址找到相关文档： Java中的有限状态机
此外，您还可以在以下网址下载该库： Java FSM库：DynamicEasyFSM
有两种不同的方法可以实现有限状态机。
选项1：
预定义工作流程的有限状态机：如果您事先知道所有状态，并且状态机几乎没有未来变更，那么推荐使用此方法。
确定应用程序中所有可能的状态
确定应用程序中所有的事件
确定应用程序中所有可能导致状态转换的条件
事件的发生可能会导致状态的转换
通过决定状态和转换的工作流程来构建有限状态机。
例如，如果在状态1发生事件1，则将更新状态，但是状态机状态仍可能处于状态1。
如果在状态1发生事件2，在某些条件评估后，系统将从状态1移动到状态2
此设计基于状态和上下文模式。
请查看有限状态机原型类。
选项2：
行为树：如果状态机工作流程经常更改，则推荐使用此方法。您可以动态添加新行为而不破坏树形结构。
基础的任务（Task）类为所有这些任务提供接口，其中叶子任务是刚才提到的那些任务，而父任务则是决定下一个要执行的任务的内部节点。
任务仅具有实际完成所需的逻辑，所有关于任务是否已启动、是否需要更新、是否已成功完成等决策逻辑都被集中在任务控制器（TaskController）类中，并通过组合添加。
装饰器（decorators）是一种“装饰”其他类的任务，通过在其上包装并赋予其额外的逻辑。
最后，黑板（Blackboard）类是由父AI拥有的类，每个任务都引用它。它作为所有叶子任务的知识数据库。
请查看Jaime Barrachina Verdia的文章以获取更多详细信息。
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);
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))）并不特别高效。
请注意，维基百科页面侧重于许多相似对象共享相似数据的情况，就像Java中的String实现一样。在我看来，享元模式要更加通用，并涵盖了任何短暂生命周期对象的按需创建（使用更多CPU来节省更有效的底层数据结构）。
我使用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);
}
Action：引起状态转换的类。
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来保持动作状态映射。
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框架，它允许我们使用Spring的几个功能，如依赖注入和Spring可以提供的其他所有功能。
它非常适合对Apparat的生命周期进行建模，例如INITIALIZING、STARTED、ERROR、RECOVERING、SHUTTINGDOWN等状态。但是我看到很多人试图用它来建模购物车、预订系统等，Spring State Machine的内存占用相对较大，无法建模数百万个购物车或预订。
另一个缺点是，Spring State Machine虽然具有将自身持久化以进行长时间运行过程的能力，但它没有任何机制来适应这些过程中的变化。如果您持久化了一个过程，并且您必须在10天后恢复它，因为由于新软件发布/要求而发生了业务流程的更改，您没有内置的手段来处理它。
我有几篇博客，blog1 blog2，演示了如何使用Spring State Machine进行编程，特别是模型驱动的方式，如果你想检查一下。
主要是因为我提到的缺点，建议你先看另一个框架 Akka FSM (Finite State Machine)，它更适合于低内存占用率的情况，可以拥有数百万个实例，并具备适应长时间运行进程变化的 能力。
现在你可以使用Java开发Akka框架，但是由于一些缺失的语言元素，你不想阅读生成的代码，Scala是更适合开发Akka的语言。我听到你说Scala太复杂了，我无法说服我的项目负责人使用Scala进行开发，为了让你们相信这是一个选择，我开发了一个概念验证应用程序，使用Java / Scala混合编写，并且所有Scala Akka有限状态机代码都是从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");
}
附言：虽然没有直接回答你的问题，但是向你展示了如何在Java中非常容易地实现FSM。