问题有点长,请耐心点看,谢谢。。
问题是:根据事故树求最小割集(所谓最小割集,就是把一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
或者需要更多一些,那需要什么。。
请给出详细一点的算法,包括注释。
问题是:根据事故树求最小割集(所谓最小割集,就是把一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
或者需要更多一些,那需要什么。。
请给出详细一点的算法,包括注释。
解决方案 »
- Delphi 如何实现对谷歌搜索引擎的数据提交
- 错在哪里?
- 请问delphi编译后的程序有没有debug版和relase版的区别?
- 怎样向另一个FORM传递参数?
- 急,哪位高手帮帮我??感谢......
- 一个简单的问题
- Delhi連接數據庫建立動態菜單
- 我在borland裡download了ADO的sp1和sp2,但是沒有key,用不了,那位能夠幫助?將不勝感激!
- 高分请教API函数:getsetting和savesetting在哪里找!
- 随便讨论一下Delphi的编程风格的问题!
- 还是idTCPServer和idTCPClient的问题
- TServerSocket与TClientSocket的问题?高手啊
我自己顶了,呵呵~~~