验证FSM中从'起始'状态到'结束'状态的可达性

Question

我正在研究一个有限状态机（FSM），它有N个状态（也就是状态图上的N个点）。其中一个状态是“开始”状态，另一个是“结束”状态。

我想做的事情是：

1. 检查其他N-2个状态是否可以从“开始”状态到达
2. 检查“结束”状态是否可以从每个N-2个状态到达

有什么好的算法可以实现这个目标吗？
另外，有没有什么Python模块可以轻松完成这个验证（比如只需要调用一个函数）？

Answer 1

如果你在找一个简单的解决办法，可以用 传递闭包 来计算有限状态机（FSM）的转移函数，使用 弗洛伊德-沃尔沙尔算法。这样你就能得到一个 NxN 的数组，告诉你任意两个状态 P 和 Q 之间，Q 是否可以从 P 到达。如果 N 不太大，这个算法的计算量 O(N3) 是可以接受的。

这个算法可以用五行 Python 代码来实现。在这里，trans 是一个列表的列表，trans[s][t] 如果存在从 s 到 t 的直接转移，就为 True，否则为 False。（s 和 t 预计是整数）。这个算法会直接修改这个数组；当它返回时，trans[s][t] 如果存在从 s 到 t 的路径，就为 True：

def warshall(trans):
  for k in range(len(trans)):
    for i in range(len(trans)):
      for j in range(len(trans)):
        trans[i][j] = trans[i][j] or trans[i][k] and trans[k][j]

（最后一行本来可以用 |= 来写，但我觉得那样不太清楚。）

这个算法也可以用来计算“所有最短路径”的数组，通常被认为是解决这个问题的方法。为了做到这一点，我们从一个转移数组开始，其中 trans[i][j] 是从 i 到 j 的转移成本（如果没有直接转移则为 infinity），然后把最后一行替换为：

        trans[i][j] = min(trans[i][j], trans[i][k] + trans[k][j])

对于一个 FSM，通常会把所有的成本设置为 1 或 infinity，这样你就能得到任意 s 和 t 之间的最短路径长度。

你可以在网上找到这个算法的正式证明（以及算法和图论的标准教材中），所以我就简单概述一下：

为了简化输入，我假设节点用范围 0…N-1 的整数来表示。我们称从 s 到 t 的路径 s→p0→…→pi→t 为 <k-路径，如果每个 p0…pi 都小于 k。因此，从 s 到 t 的唯一可能的 <0-路径就是简单路径 s→t，如果它在图中存在，而从 s 到 t 的每条路径都是 <N-路径。

现在，如果从 s 到 t 存在 <k+1-路径，那么要么存在从 s 到 t 的 <k-路径，要么存在从 s 到 k 的 <k-路径，以及从 k 到 t 的另一条 <k-路径。（这只是另一种说法，说明每条非单一路径都有一个最大内部节点，可以在那个节点处分成两条路径，它们的最大值都更小。）

沃尔沙尔算法的每次迭代都是从 <k-路径的转移数组开始，最后得到 <k+1-路径的转移数组，通过添加所有经过节点 k 的路径组合。因此，最后我们得到了 <N-路径的数组，正如我们之前观察到的，它包含了所有可能的路径。

Answer 2

你可以从起始状态出发，使用任何一种遍历方法（比如深度优先搜索DFS或广度优先搜索BFS），把访问过的状态标记为可以到达的。对于可达性问题，只需把边反向，然后从终点开始遍历。

Answer 3

我发现了一个很有用的Python模块，叫做Networkx，它对我帮助很大。
我用的具体功能是这个（networkx.shortest_path）。

下面是我用的解决方案。

import networkx as nx

G = nx.DiGraph()
G.add_nodes_from(["Start", "a", "b", "c", "End"])
G.add_edges_from([("Start", "a"), ("Start", "c"), ("a", "b"), ("b", "a"), ("c", "End")])

total_num_nodes = G.number_of_nodes()

if len(nx.shortest_path(G, source="Start")) < total_num_nodes:
    print "\nThis FSM has inaccessible states"
else:
    print "\nAll nodes reachable from 'Start'"

H = G.reverse()
if len(nx.shortest_path(H, source="End")) < total_num_nodes:
    print "\nThis FSM has dead-end states"
else:
    print "\nAll nodes have a path to reach the 'End' state"