建模考试4
- 格式：doc
- 大小：46.00 KB
- 文档页数：6
隔离设计
有8个犯人，为防止他们串供，必须把有牵连的犯人互相隔离，问至少需要
几个关押室，给出计算方法与程序。已知有牵连的情况如下表：
犯人 有牵连的犯人
A B C D E F G H B C E G
A C H
A B D
C E H
A D F H
F G
A F H
B D E G
有8个犯人，为防止他们串供，必须把有牵连的犯人互相隔离，问至少需要几个
关押室，给出计算方法与程序。已知有牵连的情况如下表：
犯人
有牵连的犯人
A BCEG
B ACH
C ABD
D CEH
E ADH
F G
G AFH
H BDEG
我不熟悉这类匹配问题的优化算法，先用遍历算法计算一下，程序如下：
clc;clear;close all;
tic;
Pa='BCEG';
Pb='ACH';
Pc='ABD';
Pd='CEH';
Pe='ADH';
Pf='G';
Pg='AFH';
Ph='BDEG';
S=zeros(8);
for k=1:8;
T=eval(['P',char(96+k)]);
S(k,T-64)=1;
end
imagesc(S);axis square;colormap(gray)
set(gca,'xticklabel',char(65:72)','XAxisLocation','top')
set(gca,'yticklabel',char(65:72)')
ss=perms(1:8);
N=ones(1,size(ss,1));
for k=1:size(ss,1);
sst=ss(k,:);
St=S(sst,sst);
fs=1;
for L=2:8;
if sum(sum(St(fs:L,fs:L)))>0.5;
N(k)=N(k)+1;
fs=L;
end
end
k
end
[Mn,Ik]=min(N);
Sr=char(65:72);
Sr=Sr(ss(Ik(1),:));
sst=ss(Ik(1),:);
St=S(sst,sst);
figure;imagesc(St);axis square;colormap(gray)
k0=1;
k00=k0;
for k=1:8;
stt=St(k0:k,k0:k);
if sum(stt(:))>0;
k0=k;
k00=[k00,k0];
stt=St(k0:k,k0:k);
sm(k)=sum(stt(:));
else
sm(k)=sum(stt(:));
end
end
k0=1;
k00(1)=[];
k00=[k00,9];
for k=1:length(k00);
eval(['G',num2str(k),'=Sr(k0:k00(',num2str(k),')-1)']);
k0=k00(k);
end
toc
上面程序输出结果为：
G1 =
HFC
G2 =
EGB
G3 =
DA
elapsed_time =
18.6460
就是说用时18.646s，这个数值与计算机速度有关。分组结果为：
DA, EGB, HFC
即至少需要3个关押室
论文摘要：将8个犯人之间的牵连关系做成一个8*8矩阵，其中“1”表示二者有牵连，“0”表
示二者无牵连, 利用表达式： （ ， 表示各个犯人，），将所有相互之间无牵连的犯人
放在同一个房间，将剩下有牵连的按同样方式选出无牵连的犯人放在另一个房间，用同样方
法安排剩下所有的人，即将所有结果为零的 放在同一个房间。审问完后的犯人可以放在同
一个房间。
（1）问题的分析：
要利用最少的关押室，就必须让更多不相牵连的人关押在同一个关押室，就必须找出这尽可
能多的犯人之间牵连关系的衡量标准。因为两人之间的牵连关系只有“有”和“无”两种，于是
就可以将各犯人之间的牵连关系转化为如下矩阵：将这语言文字转化为数学表达式更有利于
问题的解决。
“1”表示两者有牵连，“0”表示两者无牵连
（2）模型假设 根据以上分析做如下假设：
1.不考虑审问过程中由于其中个别人的关系而导致审问的正常进行，即关键人物于次要人物
的影响。
2.各个犯人在审问后与审问前一样，不会导致信息的透露而使原有的相互之间的牵连关系发
生改变；
3.审问后的犯人可以放在同一个房间，而且在审问的过程中，犯人可以换关押室来腾出关押
室。
4.审问完后的人不会因为在接受审问过程中得知其他信息而改变自身于他人的牵连关系。
（3）模型建立：
建立犯人之间的相互关系，很自然联系计算一组内所有犯人之间都无牵连，即相互之间的乘
积为零。即首先选出其中任何一个犯人，然后利用所给牵连关系找出与他无牵连的一组人，
在排除这一组里面有相互牵连的一个犯人，用数学表达式即为：
（ ， 表示各个犯人，）二者的乘积表示两者的牵连关系，即对应矩阵中的关系。
有8个犯人，为防止他们串供，必须把有牵连的犯人互相隔离，问至少需要几个关押室，
给出计算方法与程序。已知有牵连的情况如下表：
犯人 有牵连的犯人
A B C E G
B A C H
C A B D
D C E H
E A D F H
F F G
G A F H
H B D E G
请帮忙写出详细的过程，用一个叫MATLAB的数学软件做，谢谢了。
12月15号以前。感谢啊。
提问者： yb07341 - 二级
答复 共 1 条
先对两个字母进行检验看能否放在一个盒子中，能则返回0，不能则返回1
function d=test(x,y)
d=0;
if x==1
if (y==2)|(y==3)|(y==5)|(y==7)
d=1;
end
elseif x==2
if (y==1)|(y==3)|(y==8)
d=1;
end
elseif x==3
if (y==1)|(y==2)|(y==4)
d=1;
end
elseif x==4
if (y==3)|(y==5)|(y==8)
d=1;
end
elseif x==5
if (y==1)|(y==4)|(y==6)|(y==8)
d=1;
end
elseif x==6
if (y==5)|(y==7)
d=1;
end
elseif x==7
if (y==1)|(y==6)|(y==8)
d=1;
end
elseif x==8
if (y==2)|(y==4)|(y==5)|(y==7)
d=1;
end
end
设A=1,B=2...H=8最后返回的c值是需要的牢房个数
function c=Nbcrim()
clc
clear all
c=1;
s=1;
for i=2:8
for j=1:(i-1)
s=s*test(i,j);
end
c=c+s;
end
回答者： liuya8737
