返回

确定有限自动机(DFA)最小化

StatechartDiagram1.svg

预备 最简化的DFA:这个DFA没有多余状态、也没有两个相互等价的状态。一个DFA可以通过消除无用状态、合并等价状态而转换成一个与之等价的最小状态的有穷自动机。 无用状态:从自动机开始状态出发,任何输入串也发到达的那个状态,或者这个状态没有通路可达终态。 等价转态:两个状态,识别相同的串,结果都同为正确或错误,这两个状态就是等价的。 区别状态:不是等价状态。

// 基于等价类的思想
split(S) 
    foreach (character c) 
        if (c can split S)
            split S into T1, ..., TK

hopcroft() 
    split all nodes into N, A
    while (set is still changes) 
        split(all S)

根据非终结状态与非终结状态将所有的节点分为 N 和 A 两大类。 N 为非终结状态,A 为终结状态,之后再对每一组运用基于等价类实现的切割算法。

增广路径

从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。

增广路径性质:     (1)P的路径长度必定为奇数,第一条边和最后一条边都不属于M,因为两个端点分属两个集合,且未匹配。     (2)P经过取反操作可以得到一个更大的匹配M’。     (3)M为G的最大匹配当且仅当不存在相对于M的增广路径。

参考文章:

http://spiritsaway.info/hopcroft-karp-algorithm.html https://www-m9.ma.tum.de/graph-algorithms/matchings-hopcroft-karp/index_en.html

Licensed under CC BY-NC-SA 4.0
❤️
Built with Hugo
Theme Stack designed by Jimmy