已知犯人8名，要将其中有关联者隔离，怎么做？
某案件中捕获了8名犯人，代号分别为A-H，为了防止他们互相串供，必须将其中有关联的人互相隔离，问至少需要几个关押室？请给出计算方法与程序。
已知犯人之间的牵连情况如下表所示：
犯人——有牵连的犯人
A————B C E G
B————A C H
C————A B D
D————C E H
E————A D F H
F————E G
G————A F H
H————B D E G
新手求解，这个是一定要用图论做吗……
可以使用关系矩阵圈0，步骤如下：
step1：写出关系矩阵，有关系为1，无关系为1，自己和自己设定为0
step2：数出每行0的个数
step3：从0最多的行开始（如有相同的则选择这行中0所对应的列中0个数最多的），选择这一行中除行首元素外所对应的0所在列中0个数最多的列（如果相同则可任意选择）与该行逻辑加（1+1=1，1+0=1，0+0=0），该列上所有的0变为1，并将选择出来的行列做标记。标记过的可以不再做运算，因为标记过后对其后的运算没有影响
step4：然后以同样的方法再在该行中选择下一个做加法的列（每次相加时行都用最初未做任何加法时的行）。直到该行中没有没有标记过的0.同时将该行所对应的行首元素所在的列全部的0变为1.
step5：重复234步，直到没有没做标记的0为止
step6：该行首元素与该行做标记的0所对应的元素为最后的结果
以给出的数据为例
1、写出关系矩阵并标出0的个数
A B C D E F G H 0的个数
A 0 1 1 0 1 0 1 0 4
B 1 0 1 0 0 0 0 1 5
C 1 1 0 1 0 0 0 0 5
D 0 0 1 0 1 0 0 1 5
E 1 0 0 1 0 1 0 1 4
F 0 0 0 0 1 0 1 0 6
G 1 0 0 0 0 1 0 1 5
H 0 1 0 1 1 0 1 0 4
最多的为F，F行中所对应的有0的列为ABCDH，其中BCD列都为5个0
在这三个中任意选择一个，在此选择B，标记F行B列的0.
F行与B列相加
+
=
将B列除标记的0外所有的0变为1，得到新的矩阵
A B C D E F G H 0的个数
A 0 1 1 0 1 0 1 0 4
B 1 1 1 0 0 0 0 1 4
C 1 1 0 1 0 0 0 0 5
D 0 1 1 0 1 0 0 1 4
E 1 1 0 1 0 1 0 1 3
F 1 0 1 0 1 0 1 1
G 1 1 0 0 0 1 0 1 4
H 0 1 0 1 1 0 1 0 4
F行剩下D列，，标记F行D列的0。同样用F行与D列相加
+
=
将D列除标记的0外所有的0变为1，得到新的矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 0 1 0 3
B 1 1 1 1 0 0 0 1 3
C 1 1 0 1 0 0 0 0 5
D 0 1 1 1 1 0 0 1 3
E 1 1 0 1 0 1 0 1 3
F 1 0 1 0 1 0 1 1
G 1 1 0 1 0 1 0 1 3
H 0 1 0 1 1 0 1 0 4
该行中出F列无未标记的0
将F列全部的0变为1得到新矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 1 1 0 2
B 1 1 1 1 0 1 0 1 2
C 1 1 0 1 0 1 0 0 4
D 0 1 1 1 1 1 0 1 2
E 1 1 0 1 0 1 0 1 3
F 1 0 1 0 1 1 1 1
G 1 1 0 1 0 1 0 1 3
H 0 1 0 1 1 1 1 0 3
重新选择行
C行0最多
C行中有EGH列为0，E列为4个0，G为5个0，H为3个0，选择G列，标记C行G列的0
C行加最初的G列
+
=
将G列全部0变为1
得到新矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 1 1 0 2
B 1 1 1 1 0 1 1 1 1
C 1 1 0 1 0 1 0 1
D 0 1 1 1 1 1 1 1 1
E 1 1 0 1 0 1 1 1 2
F 1 0 1 0 1 1 1 1
G 1 1 0 1 0 1 1 1 2
H 0 1 0 1 1 1 1 0 3
选择E列做加法，标记C行E列的0
+
=
E列所有0变为1，C行除C列外没有没标记的0，将C列全部0变为1
得到新矩阵
A B C D E F G H 0的个数
A 0 1 1 1 1 1 1 0 2
B 1 1 1 1 1 1 1 1 0
C 1 1 1 1 0 1 0 1
D 0 1 1 1 1 1 1 1 1
E 1 1 1 1 1 1 1 1 0
F 1 0 1 0 1 1 1 1
G 1 1 1 1 1 1 1 1 0
H 0 1 1 1 1 1 1 0 2
A行与H行0最多，A行中对应有H列为0且对应H列0的个数为2。H行对应有A列为0且A列0的个数为3。所以选择A行。
A行与H列相加，标记A行H列的0
+
=
将H列所有0变为1，A行中除A列为0外均为1，所以将A列所有0变为1
得到新矩阵
A B C D E F G H 0的个数
A 1 1 1 1 1 1 1 0
B 1 1 1 1 1 1 1 1 0
C 1 1 1 1 0 1 0 1
D 1 1 1 1 1 1 1 1 0
E 1 1 1 1 1 1 1 1 0
F 1 0 1 0 1 1 1 1
G 1 1 1 1 1 1 1 1 0
H 1 1 1 1 1 1 1 1 0
矩阵中没有没标记过的0
计算结束。
得出结果为最少为3个
分配方案为
A-H
C-E-G
F-B-D．
这种方法使用纯数学计算的方法得到最后的结果。每次选择都是以0最多为准，减少了过多消除无关联量的情况。
另外，不需要太多的逻辑分析，完全依赖矩阵简单的特殊计算，比较容易在计算机上编程实现。
整数规划
本帖最后由 liwenhui 于 2017-6-2 21:02 编辑楼上的回答很好，能解决问题，但只是一种算法逻辑，没能很好地体现数学建模的方法特点。这类问题除图论方法之外，还有多种方法可以求解，我能想到的至少有：1、整数规划 2、动态规划；两种。这里先使用整数规划来解决，使用LINGO编写了一个模型如附件所示，求解的结果为： Global optimal solution found.
Objective value: 3.000000
Objective bound: 3.000000
Infeasibilities: 0.000000
Extended solver steps: 1
Total solver iterations: 135
Variable Value Reduced Cost
Y( R1) 1.000000 0.000000
Y( R2) 0.000000 0.000000
Y( R3) 0.000000 0.000000
Y( R4) 0.000000 0.000000
Y( R5) 1.000000 0.000000
Y( R6) 1.000000 0.000000
Y( R7) 0.000000 0.000000
Y( R8) 0.000000 0.000000
Z( A, A) 1.000000 0.000000
Z( A, B) 1.000000 0.000000
Z( A, C) 1.000000 0.000000
Z( A, D) 0.000000 0.000000
Z( A, E) 1.000000 0.000000
Z( A, F) 0.000000 0.000000
Z( A, G) 1.000000 0.000000
Z( A, H) 0.000000 0.000000
Z( B, A) 1.000000 0.000000
Z( B, B) 1.000000 0.000000
Z( B, C) 1.000000 0.000000
Z( B, D) 0.000000 0.000000
Z( B, E) 0.000000 0.000000
Z( B, F) 0.000000 0.000000
Z( B, G) 0.000000 0.000000
Z( B, H) 1.000000 0.000000
Z( C, A) 1.000000 0.000000
Z( C, B) 1.000000 0.000000
Z( C, C) 1.000000 0.000000
Z( C, D) 1.000000 0.000000
Z( C, E) 0.000000 0.000000
Z( C, F) 0.000000 0.000000
Z( C, G) 0.000000 0.000000
Z( C, H) 0.000000 0.000000
Z( D, A) 0.000000 0.000000
Z( D, B) 0.000000 0.000000
Z( D, C) 1.000000 0.000000
Z( D, D) 1.000000 0.000000
Z( D, E) 1.000000 0.000000
Z( D, F) 0.000000 0.000000
Z( D, G) 0.000000 0.000000
Z( D, H) 1.000000 0.000000
Z( E, A) 1.000000 0.000000
Z( E, B) 0.000000 0.000000
Z( E, C) 0.000000 0.000000
Z( E, D) 1.000000 0.000000
Z( E, E) 0.000000 0.000000
Z( E, F) 1.000000 0.000000
Z( E, G) 0.000000 0.000000
Z( E, H) 1.000000 0.000000
Z( F, A) 0.000000 0.000000
Z( F, B) 0.000000 0.000000
Z( F, C) 0.000000 0.000000
Z( F, D) 0.000000 0.000000
Z( F, E) 1.000000 0.000000
Z( F, F) 1.000000 0.000000
Z( F, G) 1.000000 0.000000
Z( F, H) 0.000000 0.000000
Z( G, A) 1.000000 0.000000
Z( G, B) 0.000000 0.000000
Z( G, C) 0.000000 0.000000
Z( G, D) 0.000000 0.000000
Z( G, E) 0.000000 0.000000
Z( G, F) 1.000000 0.000000
Z( G, G) 1.000000 0.000000
Z( G, H) 1.000000 0.000000
Z( H, A) 0.000000 0.000000
Z( H, B) 1.000000 0.000000
Z( H, C) 0.000000 0.000000
Z( H, D) 1.000000 0.000000
Z( H, E) 1.000000 0.000000
Z( H, F) 0.000000 0.000000
Z( H, G) 1.000000 0.000000
Z( H, H) 1.000000 0.000000
X( R1, A) 0.000000 0.000000
X( R1, B) 0.000000 0.000000
X( R1, C) 1.000000 0.000000
X( R1, D) 0.000000 0.000000
X( R1, E) 1.000000 0.000000
X( R1, F) 0.000000 0.000000
X( R1, G) 1.000000 0.000000
X( R1, H) 0.000000 0.000000
X( R2, A) 0.000000 0.000000
X( R2, B) 0.000000 0.000000
X( R2, C) 0.000000 0.000000
X( R2, D) 0.000000 0.000000
X( R2, E) 0.000000 0.000000
X( R2, F) 0.000000 0.000000
X( R2, G) 0.000000 0.000000
X( R2, H) 0.000000 0.000000
X( R3, A) 0.000000 0.000000
X( R3, B) 0.000000 0.000000
X( R3, C) 0.000000 0.000000
X( R3, D) 0.000000 0.000000
X( R3, E) 0.000000 0.000000
X( R3, F) 0.000000 0.000000
X( R3, G) 0.000000 0.000000
X( R3, H) 0.000000 0.000000
X( R4, A) 0.000000 0.000000
X( R4, B) 0.000000 0.000000
X( R4, C) 0.000000 0.000000
X( R4, D) 0.000000 0.000000
X( R4, E) 0.000000 0.000000
X( R4, F) 0.000000 0.000000
X( R4, G) 0.000000 0.000000
X( R4, H) 0.000000 0.000000
X( R5, A) 0.000000 0.000000
X( R5, B) 1.000000 0.000000
X( R5, C) 0.000000 0.000000
X( R5, D) 1.000000 0.000000
X( R5, E) 0.000000 0.000000
X( R5, F) 0.000000 0.000000
X( R5, G) 0.000000 0.000000
X( R5, H) 0.000000 0.000000
X( R6, A) 1.000000 0.000000
X( R6, B) 0.000000 0.000000
X( R6, C) 0.000000 0.000000
X( R6, D) 0.000000 0.000000
X( R6, E) 0.000000 0.000000
X( R6, F) 1.000000 0.000000
X( R6, G) 0.000000 0.000000
X( R6, H) 1.000000 0.000000
X( R7, A) 0.000000 0.000000
X( R7, B) 0.000000 0.000000
X( R7, C) 0.000000 0.000000
X( R7, D) 0.000000 0.000000
X( R7, E) 0.000000 0.000000
X( R7, F) 0.000000 0.000000
X( R7, G) 0.000000 0.000000
X( R7, H) 0.000000 0.000000
X( R8, A) 0.000000 0.000000
X( R8, B) 0.000000 0.000000
X( R8, C) 0.000000 0.000000
X( R8, D) 0.000000 0.000000
X( R8, E) 0.000000 0.000000
X( R8, F) 0.000000 0.000000
X( R8, G) 0.000000 0.000000
X( R8, H) 0.000000 0.000000
可以看到，最少需要3个房间，安排方案是：
C E G
B D
A F H
页:
[1]