问题有点长,请耐心点看,谢谢。。
问题是:根据事故树求最小割集(所谓最小割集,就是把一Top事件,比如T去除中间所有的事件,留下最基础的就行)。比如:T=A1+A2=X1*X2+X3*X4*X5(A1,A2是中间事件),那么,最小割集就是{X1,X2},和{X3,X4,X5},用图可以这样表示(这里不能发图片,只好这样子了):
          T
          |or
      A1      A2
      |and     |and
   X1   X2  X3  X4  X5 
还可以把X3变成中间事件A3,再向下延伸。。(如果用另外的方法,可以不看下面的算法)
我能想到的算法是:
先用一个联接矩阵,A=(aij)m*n (注:i,j,m,n为下标)(看来还是举个例子比较好,kn表示事件,如果是and,那么只有一个,如果是or,如果输入有一个,就有几个k)
                      T
                      |or(k8,k9) 
             A1                  A2
             |and(k6)            |and(k7)
     X1      A3     X2       X4      A4
             |or (k2,k3)           |or(k4,k5)
          X1   X3                A5      X6
                                 |and k1(因为是and,所以只有一个)
                              X4    X5
T=A1+A2=(X1*A3*X2)+X4*A4=X1*X2*(X1+X3)+X4*(A5+X6)=X1*X2*(X1+X3)+X4*(X4*X5+X6)
当然如果是人的话,可以用boolean逻辑乘求出来:T=x4*x5+x1*x2+x4*x6,最小割集是{x4,x5},{x1,x2},{x4,x6},我在资料上看到这样一个算法:
比如:k1的输入是x4和x5,而k1的输出是A5所以第一列为-1,-1,1(省去中间的0没写,请原谅,输入为-1,输出为1)
  k1  k2  k3  k4  k5  k6  k7  k8  k9
      -1               -1              x1
                      -1               x2
          -1                           x3
  -1                      -1           x4
  -1                                   x5
                   -1                  x6
                       1*     -1*      A1
                           1       -1  A2
       1   1           -1              A3
               1    1      -1          A4
  1           -1                       A5
                                1   1  T  (空着的为0)
因为我们的目标是去除中间事件,所以A1,A2,A3,A4,A5所在的行要全部为0,运用矩阵的列相加,比如A1行,有1和-1,相加,同理。但注意的是,这里是逻辑加。-1+1=0,-1+-1=-1,0+-1=-1
并消掉一些列,比如1+4,把结果放在1,4列就去掉。
最后结果可以化简为:
  k1  k2  k3  k5 
      -1  -1     x1
      -1  -1     x2
          -1     x3
  -1          -1 x4
  -1             x5
              -1 x6
(A的全部为0了,消掉,最后结果还必须满足T这一行全为1)
  1   1    1   1 T
那么最小割集就是(从k1列到k5列),{x4,x5},{x1,x2},{x1,x2,x3},{x4,x6}.
因为x1*x2+x1*x2*x3=x1*x2*(1+x3)=x1*x2,所以最后结果为:
{x4,x5},{x1,x2},{x4,x6}问题如下:
(1)不知道谁有没有更好的算法,如果这样的话,用数组好还是直接用数据库操作。请给出算法(Delphi实现)
(2)如果用数据库,怎么定义数据结构才能让算法复杂度最低,毕竟我们能让用户做的只是插入这样的东西:
Top  or   2   A1  A2  
A1   and  3   x1  x2  x3
A2   and  2   x4  x3
或者需要更多一些,那需要什么。。
请给出详细一点的算法,包括注释。