一个关于有限状态机（FSM）的问题

drach

为了处理一段消息，我写了个FSM，其中遇到一些问题，特来请教

假设只有2个状态A，B，并且A，B处理顺序固定，那FSM应该设计如下（简化版）

Start-------A--------B------END

如果A，B处理顺序不定，程序有可能先处理A，也有可能先处理B，则FSM图如下

                      A-------B
Start -----/                  \  ----- END
                 \ B-------A  /
但当我的状态增加到3（ABC，BCA，CAB，ACB.......），4，以至更多的时候这个状态机就会变得非常复杂,请问如何才能简化这种FSM，我的代码基本上是用switch case来转换状态

描述的可能有点乱，希望大家能看明白

Zred

找最简单的regular express

海市蜃楼

设一个或几个状态变量

qwycd

LZ用什么语言写？C和Java都有现成的生成器，你只要写RE。

heavenstar_x

除了每加一种状态，lz要多加一个switch case之外，

其他方面，增加的复杂度在什么地方？

drach

原帖由 heavenstar_x 于 2008-6-29 16:28 发表
除了每加一种状态，lz要多加一个switch case之外，

其他方面，增加的复杂度在什么地方？

因为顺序变了，AB两种状态只要处理2AB，BA，ABC就是4种情况了，每加一种状态，就要多处理2的N-1次方个

Ole_2000_0

好长时间没来了, 看到楼主这个问题不禁手痒, 也来写写自己的看法.

如果用图林机的模式来解决这个问题的话, 不免要走上使用RE的路. 不是说RE不好, RE本身非常强大, 不过在这里就比较尴尬一点, 因为想要动态地解决这个问题, 一个或者几个静态的RE是不太可能做到的. RE比较脆弱的一点就在这里体现出来了. 如果用到的字符出现变动, 比如说从{A, B, C}变到{A, B, C, D}的话, RE势必也要作出相应的改变, 这在程序运行的时候是不太可能做到的.

为什么不用Graph Transition(图)来尝试解决这个问题呢? 用图论来看这个问题, 一切都变得很简单. 所有可能出现的路线只要满足两个条件, 对于n个字符来说:
1. 每个字符不能重复
2. 字符长度等于n

这样就能动态地解决这个问题. 当然, 如果楼主是想动态地对每个状态做出不同的处理的话, 除了用programatically的方法(switch)以外不太可能了, 要是楼主真的解决了的话, 可以写个论文区申请图林奖了.

至于解决这个问题的复杂度, 用最简单的方法应该是 o(n!) 相当于:

for(i = 0; i < n, i++) {
  for(j = 0; j < n-1; j++) {
    ...
  }
}