300分求一题，此题和前面两题一样，急急急，求各位大虾帮忙看一题(用行列法求最小割集)，分不够发帖再加

Question

下面是说明，如果清楚的话可跳过。
下面字母分三中情况，T：top事件,A:中间时间,X，基本事件，其中T和A得分解
比如T=A1*A2=(x1*x2)*(x1+x3),图这里画不了，是一个树的形状，我想到的算法是：
用一数组myarray:array[0..9] of array[0..9] of string(假设范围不超过10)
---------------------
top  |      |       |
---------------------
     |      |       |
--------------------
因为T=A1*A2
然后把他替换为：
---------------------
 A1  |  A2  |       |
---------------------
     |      |       |
--------------------
如果是A1+A2
---------------------
 A1  |      |       |
---------------------
 A2  |      |       |
--------------------
因为A是中间事件，得替换，先换A1
---------------------
 x1  |  A2  |  x2   |
---------------------
     |      |       |
--------------------
因为A2=x1+x3
那么,x1,x2下面不变,A2所在列替换成如下：
---------------------
 x1  |  x1  |  x2   |
---------------------
 x1  |  x3  |  x2   |
--------------------
那么最小割集就{x1,x1,x2}和{x1,x3,x2}
当然得化简x1*x1*x2+x1*x3*x2=x1*x2*(1+x3)=x1*x2
求各位大虾帮帮忙，这是老师的作业，快要交了。我写得都烦死了，太多东西不懂，请大虾花几分钟写个代码让我参考一下，分不够再加。谢谢

Answer 1

感动~~~
我只稍微看了一点离散数学，不懂图论
不过应该可以用逻辑代数理解吧。这些都是在在二进制里面计算 1+x=1 1*x=x
比如一棵树这样表示
         T
         and
    A1       A2
    and       or
x1     x2   x1  x3
可以表示为：T=A1*A2=(x1*x2)*(x1+x3)=x1*x2*x1+x1*x2*x3
由吸收率（好象是这么说吧）x1*x2*x1=x1*x2
而x1*x2*x3+x1*x2=x1*x2*(1+x3)=x1*x2
上面符号：A1,A2是中间值，x123是基础值，我们的目标是把Top直接用基础值表示，如果最后结果化简为T=x1*x2*x3+x4*x5,那么我们说
{x1,x2,x3}和{x4,x5}就是他的最小割集。
上面写这么多是我的一个算法，具体怎么来的这里说不清楚，反正只要能编码就可以吧。
这样说好了吧。
谢谢你， xthmpro_cn(安徽农民*在外打工)，你是D一个理我的人。

Answer 2

唉，熄灯了，时间好快，周四就要交了。
我现在的做法是，先创建一个表储存树的信息。先提几个问吧，
1，因为用户能做的就是输入：数字代表数目
top and 2 A1 A2   
A1  and 2 X1 X2
A2  or  2 X1 X3
当然我们要的是任意树，而不会针对这个测试树这么简单。
问题1：该怎么设计这个表，因为只有中间事件A12才替换。而X12不替换
问题2：熄灯了，先走。。

Answer 3

基本明白,需要用到二叉树的遍历.现在关键看你怎么存储这个输入树.中间节点的AND/OR怎么表示?
另外用户输入这个二叉树有没有遵循什么规则.如果是任意深度,用户按照:
top and 2 A1 A2   
A1  and 2 X1 X2
A2  or  2 X1 X3
这样输下去可能难以构造二叉树.建议让用户风别输入入先根和中根或中根和后根来构造二叉树.
and/or的关系在二叉树构造好后一次按某种遍历方式输入.
请发布一个复杂的用例.
[email protected]

Answer 4

不过如果任意深度不行的话，先做个二叉树交一下0.9.9-alpha版再说，1.0只好以后补了。

Answer 5

本题其实利用的原理是：逻辑乘只增加割集的大小，逻辑加才增加割集的个数。比如：
A=x1*x2，相比A=x1，他的割集变为{x1,x2},但A=x1+x2不一样，他则是{x1}和{x2}
上面所说的行列法就是利用这样的原理。
个人觉得不用二叉树也行，直接用二维数组完成。问题是编码。
imacih() ，输入基本是：
top and 2 A1 A2   
A1  and 2 X1 X2
A2  or  2 X1 X3
也就是一棵树的信息
D1:输出先是:{x1,x1,x2}和{x1,x3,x2}
---------------------
 x1  |  x1  |  x2   |
---------------------
 x1  |  x3  |  x2   |  (这个仅供帮助理解用用，不是说要输出这个图)
--------------------
D2:之后是化简后的结果:x1*x1*x2+x1*x3*x2=x1*x2*(1+x3)=x1*x2
即{x1,x2}
其实我的问题是，数组里面数的代换，你们可以先别一次解决，先没有必要考虑如何存储，那当然好，不过我实在等不及，能不能先给点算法让我参考一下，就是关于数组里面的代换的。

Answer 6

你的问题的关键是在于生成一个类似于:{x1,x1,x2}和{x1,x3,x2}的表达试,你目前的思路是什么样的?你已经实现到什么地方了?

Answer 7

http://202.112.154.83/zskj/4027/classroom/3system-analise/5shigu/05geji.htm
看一下这个吧，或者能找到思路。。我是晕的要死啊。

Answer 8

对不起啦。。我帮不了你！
wind5110(叶之落) ：我毕业一年多了。。