我有工作要做，我需要你的帮助。我们要实现 a FSM - Finite State Machine，来识别字符序列（例如：A、B、C、A、C），并判断它是否被接受。
我们认为要实现三个类State：Event和Machine。该类state在 中表示一个节点FSM，我们认为用 来实现它State design pattern，每个节点都将从抽象类状态扩展，每个类将处理不同类型的事件并指示到新状态的转换。你认为这是个好主意吗？
第二件事，我们不知道如何保存所有的转换。我们再次考虑用某种 来实现它map，它保持起点并获得某种带有下一个状态的向量，但我不确定这是一个好主意。
我很乐意得到一些关于如何实现它的想法，或者你可以给我一些起点。
我应该如何保存 FSM，这意味着我应该如何在程序开始时构建树？我用谷歌搜索并找到了很多例子，但没有什么对我有帮助。
非常感谢。
状态机的核心是转换表，它将状态和符号（您称之为事件）带到新状态。这只是一个包含两个索引的状态数组。为了理智和类型安全，将状态和符号声明为枚举。我总是以某种方式（特定于语言）添加一个“长度”成员来检查数组边界。当我手动编码 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
}
};
EasyFSM 是一个动态 Java 库，可用于实现 FSM。
您可以在以下位置找到相同的文档： Java 中的有限状态机
此外，您可以在以下位置下载该库： Java FSM 库：DynamicEasyFSM
您可以通过两种不同的方式实现有限状态机。
选项1：
具有预定义工作流的有限状态机：如果您提前知道所有状态并且状态机几乎是固定的，将来没有任何更改，建议您使用
识别应用程序中所有可能的状态
识别应用程序中的所有事件
识别应用程序中可能导致状态转换的所有条件
事件的发生可能会导致状态转换
通过确定状态和转换的工作流程来构建有限状态机。
例如，如果在状态 1 发生事件 1，则状态将被更新并且机器状态可能仍处于状态 1。
如果在状态 1 发生事件 2，在某些条件评估中，系统将从状态 1 移动到状态 2
此设计基于状态和上下文模式。
看看有限状态机原型类。
选项 2：
行为树： 如果状态机工作流程频繁更改，建议使用。您可以在不破坏树的情况下动态添加新行为。
基任务类为所有这些任务提供了一个接口，叶任务就是刚才提到的那些，父任务是决定接下来执行哪个任务的内部节点。
Tasks只有他们需要做的逻辑，所有关于一个task是否开始、是否需要更新、是否成功完成等的决策逻辑都被分组在TaskController中类，并通过组合添加。
装饰器是通过包装另一个类并为其提供额外逻辑来“装饰”另一个类的任务。
最后，Blackboard类是父 AI 拥有的类，每个任务都有引用。它作为所有叶子任务的知识数据库
查看Jaime Barrachina Verdia的这篇文章了解更多详情
嗯，我建议你使用享元来实现状态。目的：避免大量小对象的内存开销。状态机可以变得非常非常大。
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;
}
}
}
这会在需要使用的基础上创建状态对象，它允许您使用更有效的底层机制来存储实际的状态机。我在这里使用的那个 (Map(Integer, Map(Symbol, Integer))) 并不是特别有效。
请注意，Wikipedia 页面侧重于许多有些相似的对象共享相似数据的情况，如 Java 中的 String 实现中的情况。在我看来，享元更通用一点，涵盖了任何按需创建生命周期较短的对象（使用更多 CPU 来节省更高效的底层数据结构）。
考虑简单、轻量级的 Java 库EasyFlow。从他们的文档中：
使用 EasyFlow，您可以：
- 实现复杂的逻辑，但保持代码简单干净
- 轻松优雅地处理异步调用
- 通过使用事件驱动的编程方法避免并发
- 通过避免递归来避免 StackOverflow 错误
- 简化复杂 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);
}
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等数据结构来保持 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"));
}
}
这是一个超级简单的 FSM 实现/示例，仅使用“if-else”，它避免了上述所有子类化答案（取自Using Finite State Machines for Pattern Matching in 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：不直接回答您的问题，而是向您展示如何在 Java 中非常轻松地实现 FSM。