<p>如果您正在寻找一个简单的解决方案,您可以使用<a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm" rel="nofollow">Floyd-Warshall algorithm</a>计算FSM转换函数的<a href="http://en.wikipedia.org/wiki/Transitive_closure" rel="nofollow">transitive closure</a>。这将给您一个<code>NxN</code>数组,告诉您对于任何两个状态<code>P</code>和{<cd3>}是否可以从<code>P</code>访问{<cd3>}。它需要<code>O(N<sup>3</sup>)</code>,如果<code>N</code>不是太大,这应该可以。在</p>
<p>算法可以用python的五行代码编写。这里<code>trans</code>是一个列表列表,如果存在从<code>s</code>到{<cd12>}的直接转换,那么{<cd9>}就是{<cd10>},否则{<cd13>}。(<code>s</code>和{<cd12>}应该是整数)。它就地修改这个数组;当它返回时,<code>trans[s][t]</code>是<code>True</code>,如果存在从<code>s</code>到{<cd12>}的路径:</p>
<pre><code>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]
</code></pre>
<p>(最后一行可能是用<code>|=</code>编写的,但我认为这不太清楚。)</p>
<p>该算法也可用于计算“所有最短路径”数组,通常被引用为解决该问题的方法。为此,我们从一个转换数组开始,其中<code>trans[i][j]</code>是从<code>i</code>到{<cd23>}(如果没有直接转换,<code>infinity</code>)的转换成本,并将最后一行替换为:</p>
^{pr2}$
<p>对于一个FSM,您通常会将所有代价设置为<code>1</code>或{<cd24>},然后您将得到从<code>s</code>到{<cd12>}的最短路径长度。在</p>
<p>你会在互联网上找到算法的正式证明(在算法和图论的标准教科书中也有),所以我只做一个大纲:</p>
<p>为了简化类型,我假设节点由<code>0…N-1</code>范围内的整数表示。如果每个<code>p<sub>0</sub>…p<sub>i</sub></code>小于<code>k</code>,我们将称之为路径<code>s→p<sub>0</sub>→…→p<sub>i</sub>→t</code>a<code><<sub>k</sub></code>-path。因此,从<code>s</code>到{<cd12>}的唯一可能的<code><<sub>0</sub></code>-路径是平凡路径<code>s→t</code>,如果它存在于图中,<code>s</code>到{<cd12>}的每一条路径都是<code><<sub>N</sub></code>-路径。在</p>
<p>现在,如果有一条<code><<sub>k+1</sub></code>-路径从<code>s</code>到{<cd12>},那么要么有一条<code><<sub>k</sub></code>-从<code>s</code>到{<cd12>},要么有一条<code><<sub>k</sub></code>-从<code>s</code>到{<cd35>}的路径和另一条{<cd33>}-从{<cd35>}到{<cd12>}的路径。(这只是另一种说法,即每个非单数路径都有一个最大内部节点,并且可以在该节点处划分为两条最大值较小的路径。)</p>
<p>Warshall算法的每次迭代从<code><<sub>k</sub></code>-路径的转移数组开始,通过添加穿过节点<code>k</code>的所有路径组合,以<code><<sub>k</sub></code>-路径的转换数组结束。最后,我们得到了<code><<sub>N</sub></code>-路径的数组,正如我们之前所观察到的,它包含了所有可能的路径。在</p>