故障树割集生成方法求助：适配嵌套AND/OR门与可变规模

问题概述 #

基于TreeView表示的故障树结构，需生成所有割集（包含AND门的全部子事件、OR门的所有排列组合）。故障树支持任意嵌套的AND/OR门结构，规模从数十到上千元素不等。

示例1：基础结构 #

原始故障树结构：

Root 
---AND_GATE
------A
------B
---OR_GATE
------C1
------C2
------AND_GATE
---------D1
---------D2
---OR_GATE
------E1
------E2
------E3
---AND_GATE
------F
------G

简化表达式：A, B, (C1 | C2 | (D1, D2)), (E1|E2|E3), F, G
预期割集输出：

A , B, C1, E1, F, G
A , B, C1, E2, F, G
A , B, C1, E3, F, G

A , B, C2, E1, F, G
A , B, C2, E2, F, G
A , B, C2, E3, F, G

A , B, D1, D2, E1, F, G
A , B, D1, D2, E2, F, G
A , B, D1, D2, E3, F, G

示例2：嵌套结构 #

原始故障树结构：

A(AND)
---A1
---A2(AND)
------B1
------B2(OR)
---------C1
---------C2
---A3(OR)
------D1
------D2

简化表达式：A1,(B1,(C1|C2)),(D1|D2)
预期割集输出：

A1  B1  C1  D1  
A1  B1  C1  D2  
A1  B1  C2  D1  
A1  B1  C2  D2  

现有实现 #

已完成故障树的结构解析，能生成简化表达式，但无法完成割集的排列组合生成。现有VB代码如下：

Public Class Cut
    Public Property Node As TreeNode
    Public Property Name As String
    Public Property GT As String
    Public Property Elements As List(Of Cut)

    Public Sub New(n As TreeNode)
        Node = n
        Name = Node.Name
        GT = GetNodeType(Node)
    End Sub

    Public Function Trace() As String
        If Elements Is Nothing OrElse Elements.Count = 0 Then
            Return Name
        Else
            Dim ans As String = ""
            Dim sep As String = IIf(GT = "or", "|", ",").ToString
            For Each el As Cut In Elements
                DbHelper.MergeIn(ans, el.Trace, sep)
            Next
            ans = Name & "=(" & ans & ")"
            Return ans
        End If
    End Function
End Class

Private Sub ReadTree(parent As TreeNode, collector As List(Of Cut))
    Dim pt, nt As Cut
    pt = New Cut(parent)

    Dim subcollector As New List(Of Cut)
    For Each node As TreeNode In parent.Nodes
        nt = New Cut(node)
        If node.GetNodeCount(True) = 0 Then
            If nt.GT = "be" Then subcollector.Add(nt)
        Else
            Call ReadTree(node, subcollector)
        End If
    Next
    pt.Elements = subcollector
    collector.Add(pt)
End Sub

核心实现思路 #

通过递归处理门逻辑，利用集合的笛卡尔积和合并操作生成割集：

• 底事件（BE）：自身就是一个单元素割集，返回[[事件名]]
• AND门：将所有子节点的割集做笛卡尔积——因为AND门要求所有子事件同时发生，每个子节点的割集必须全部组合
• OR门：将所有子节点的割集做直接合并——因为OR门要求任意一个子事件发生，每个子节点的割集都是独立的有效割集

代码实现补充 #

在现有Cut类中添加割集生成方法，递归处理每个节点：

Public Function GenerateCutSets() As List(Of List(Of String))
    ' 底事件：返回包含自身的单元素割集
    If Elements Is Nothing OrElse Elements.Count = 0 Then
        Return New List(Of List(Of String)) From {New List(Of String) From {Name}}
    End If

    Dim result As New List(Of List(Of String))
    Select Case GT
        Case "and"
            ' AND门：计算所有子节点割集的笛卡尔积
            result = Elements(0).GenerateCutSets()
            For i = 1 To Elements.Count - 1
                Dim nextChildSets = Elements(i).GenerateCutSets()
                Dim tempCombined As New List(Of List(Of String))
                ' 遍历现有割集和下一个子节点的割集，合并为新割集
                For Each existingSet In result
                    For Each nextSet In nextChildSets
                        Dim newCutSet = New List(Of String)(existingSet)
                        newCutSet.AddRange(nextSet)
                        tempCombined.Add(newCutSet)
                    Next
                Next
                result = tempCombined
            Next
        Case "or"
            ' OR门：合并所有子节点的割集
            For Each child In Elements
                result.AddRange(child.GenerateCutSets())
            Next
    End Select
    Return result
End Function

调用方式 #

解析故障树后，获取根节点的Cut对象，调用GenerateCutSets方法，再将结果格式化为字符串输出：

' 假设已通过ReadTree获取根Cut对象rootCut
Dim allCutSets = rootCut.GenerateCutSets()
For Each cutSet In allCutSets
    Console.WriteLine(String.Join(", ", cutSet))
Next

规模优化建议 #

当故障树规模较大（上千元素）时，笛卡尔积可能导致割集数量爆炸，可考虑以下优化：

1. 最小割集剪枝：生成过程中剔除包含其他割集的冗余项（比如如果存在[A,B]和[A,B,C]，则后者是冗余的）
2. 并行计算：利用多线程处理独立的OR分支，提升生成效率
3. 内存优化：采用迭代方式替代递归，避免栈溢出；使用流式处理减少内存占用

内容的提问来源于stack exchange，提问作者Berries