数学建模国赛2011B题交巡警服务平台的设置与调度第五问的算法探讨

前几天培训的时候做了国赛2011B题交巡警服务平台的设置与调度,做完后大家讨论的时候焦点都在第五问的算法究竟如何设计。虽然最后老师给出的评分标准第五问只占15分,但是个人还是觉得第五问才是最精彩的地方。下面先介绍下第五问:就是一个市有若干路口节点,其中一些节点设置了一些交巡警平台,有个犯罪嫌疑人从其中一个平台开始逃跑,跑了三分钟,警察接到报警,然后开始围堵,叫你给出一个最佳的围堵方案。(赛题请见这里

这其实就是个图论问题,由所有路口节点构成一张图,嫌犯逃跑和警察围堵都只能沿着两点间的连线来。这里关于最佳围堵方案有两种理解:一是围堵时间最短,也就是最大围堵时间最小;二是围堵节点最少,而不考虑细微的时间差异,这个是基于尽可能少的扰民来考虑的。

做完题后大家也都说了自己设计的算法,大多数都是手工算的,因为这是张包含582个节点的图,处理起来数据量确实有点大。有些是基于贪婪算法和模拟退火设计的,模拟退火我今天才终于搞懂,所以当时也没怎么听。有的组就是把图抽象成一棵树,虽然感觉肯定有问题但是不知道问题在哪。不管别人的算法怎样,他们居然都能算出来只要六七分钟就能实现全部围堵,而且居然只要十几个节点就能实现全封锁(18、19个还能接受),让我觉得很是不可思议,因为我的算法算出来需要21个节点才能实现围堵,而时间需要9分多钟(虽然最后老师公布的参考答案也是21个节点和10分钟以内,擦,简直就是标准答案。。。)。

下面讲一下我的思路。其实思路不难,将这个问题抽象成一个二分图的最大匹配问题,大致有如下几步:

1、建立矩阵Z,存放嫌犯已可达的节点。所谓已可达,指的是在那个节点警察不难将嫌犯围堵住,嫌犯迟早能到达那个节点。这里的判断条件就是警察到那个节点的时间是否小于小偷到那个点的时间减去3分钟。

2、建立矩阵W,存放需要围堵的节点。这里的节点是这样确定的:遍历矩阵Z,找出Z中点的所有邻接点,如果邻接点已在Z中,不考虑,如果邻接点不在Z中,那么对其判断是否有警察平台能将其围堵,若有,将这个邻接点存入W,若没有,将其放入Z。

3、建立匈牙利算法的邻接矩阵:如果W中的点能被80个平台中某个平台围堵,则将它们连线连起来,即设置他们在邻接矩阵中对应的值为1,否则为0,遍历W中所有点和80个平台的关系就能得到这个邻接矩阵。

4、调用匈牙利算法对矩阵W和80个交巡警平台进行匹配,如果完全匹配,算法结束,如果不能完全匹配,则认为W中未匹配的点是嫌犯可达的,将其加入Z,并从W中删除,然后重新确定新的Z对应的W,并重新生成邻接矩阵,调用匈牙利算法进行匹配,直到得到完全匹配为止。

我想来想去,上面的算法似乎确实没啥问题,希望高手能指出问题所在……

下面给出我写的Matlab代码:

%围堵程序
 %先计算嫌犯到每个点的距离和时间
 v=10; %v是嫌犯逃逸速度,单位为mm/min,即60km/h
 [S1,D1]=minRoute(32,582,A,1); %其中32可改为其他起点,D1是距离矩阵
 D11=D1./v; %嫌犯到每个点的时间
%计算80个平台到所有点的距离和时间
 [S2,D2]=minRoute(1,582,A,1);
 for i=2:20 %A区
 [Si,Di]=minRoute(i,582,A,1);
 D2=[D2;Di];
 end
 for i=93:100 %B区
 [Si,Di]=minRoute(i,582,A,1);
 D2=[D2;Di];
 end
 for i=166:182 %C区
 [Si,Di]=minRoute(i,582,A,1);
 D2=[D2;Di];
 end
 for i=320:328 %D区
 [Si,Di]=minRoute(i,582,A,1);
 D2=[D2;Di];
 end
 for i=372:386 %E区
 [Si,Di]=minRoute(i,582,A,1);
 D2=[D2;Di];
 end
 for i=475:485 %F区
 [Si,Di]=minRoute(i,582,A,1);
 D2=[D2;Di];
 end
 %此时的D2已经存储了80个平台到所有点的最短路,并将80个平台分别标号为1到80
 D22=D2./10; %D22存放80个平台到各个点的时间,一个80*582矩阵
%建立矩阵Z,存放嫌犯已跑过的节点
 Z=[];
 for i=1:582 %先将最初3分钟内已跑过的节点存入Z
 if(D11(i)<3)
 Z=[Z,i];
 end
 end
 %建立矩阵W,存放需要围堵的节点
 W=[];
%调用函数生成距离邻接矩阵I
 [I,w]=fenpei(Z,A,W,D11,D22);
 W=w;
 %调用匈牙利算法
 assignment = erfentu(I)
 ass=sum(assignment');
 %判断是否完全匹配
 while(1)
flag3=0;
 for i=1:length(W)
 flag3=flag3+(0==ass(i));
 end
 if(flag3==0)
 W
 assignment
 break
 else
 for j=length(W):-1:1
 if(ass(j)==0)
 Z=[Z,W(j)];%将未分配的点加入Z,即这些点警察追堵不到,只能让小偷经过
 W(j)=[];%将未分配的点从W删除
 end
 end
 assignment=[];
 [I,w]=fenpei(Z,A,W,D11,D22);
 W=w;
 assignment=erfentu(I);
 ass=sum(assignment');
 end
end

function [I,w]=fenpei(Z,A,W,D11,D22)
 %判断Z中节点的下一个节点是否属于Z,若不属于,则再判断他是否满足能够追捕到,最后建立关系矩阵I,利用匈牙利算法
 for i=1:length(Z)
 for j=1:582
 if(A(Z(i),j)<Inf) %寻找Z中节点的邻接节点,满足条件的j即是邻接节点
 flag=0;
 for k=1:length(Z)
 flag=flag+(j==Z(k));%判断Z中某点的邻接节点j是否属于Z
 end
 if(flag==0) %若不属于Z,则存入矩阵W
 flag2=0;
 for p=1:length(W)
 flag2=flag2+(j==W(p));
 end
 if(flag2==0) %判断W中是否已有j,若没有,则将j存入W
 W=[W,j];
 end
 end
 end
 end
 end
 %建立关系矩阵I,方便进行匈牙利算法
 I=zeros(length(W),80);%%%%%%尝试
 w=W;
%计算80个平台到W中所有点的时间,若满足判定条件,则其关系矩阵对应值为平台到该点的时间,否则为Inf
 for i=1:length(W)
 for j=1:80
 if(D11(W(i))-3>D22(j,W(i)))
 I(i,j)=1;%%%%%%%%%%%%%尝试
 end
 end
 end
function assign=assignment(A)
 [m,n] = size(A);
 M(m,n)=0;
 for(i=1:m)
 for(j=1:n)
 if(A(i,j))
 M(i,j)=1;
 break;
 end
 end %求初始匹配 M
 if(M(i,j))
 break;
 end
 end %获得仅含一条边的初始匹配 M
 while(1)
 for(i=1:m)
 x(i)=0;
 end %将记录X 中点的标号和标记*
 for(i=1:n)
 y(i)=0;
 end %将记录Y 中点的标号和标记*
 for(i=1:m)
 pd=1; %寻找X 中 M 的所有非饱和点
 for(j=1:n)
 if(M(i,j))
 pd=0;
 end;
 end
 if(pd)
 x(i)=-n-1;
 end
 end %将X 中 M 的所有非饱和点都给以标号0 和标记*, 程序中用 n+1 表示0 标号, 标号为负数时表示标记*
 pd=0;
 while(1)
 xi=0;
 for(i=1:m)
 if(x(i)<0)
 xi=i;
 break;
 end
 end %假如 X 中存在一个既有标号又有标记*的点, 则任 取X 中一个既有标号又有标记*的点xi
 if(xi==0)
 pd=1;
 break;
 end %假如X 中所有有标号的点都已去掉了标记*, 算法终止
 x(xi)=x(xi)*(-1); %去掉xi 的标记*
 k=1;
 for(j=1:n )
 if(A(xi,j)&y(j)==0)
 y(j)=xi;
 yy(k)=j;
 k=k+1;
 end
 end %对与 xi 邻接且尚未给标号的 yj 都给以标号i
 if(k>1)
 k=k-1;
 for(j=1:k)
 pdd=1;
 for(i=1:m)
 if(M(i,yy(j)))
 x(i)=-yy(j);
 pdd=0;
 break;
 end
 end %将yj 在 M 中与之邻接的 点xk (即xkyj ∈M), 给以标号j 和标记*
 if(pdd)
 break;
 end
 end
 if(pdd)
 k=1;
 j=yy(j); %yj 不是 M 的饱和点
 while(1)
 P(k,2)=j;
 P(k,1)=y(j);
 j=abs(x(y(j))); %任取 M 的一个非饱和点 yj, 逆向返回
 if(j==n+1)
 break;
 end %找到X 中标号为0 的点时结束, 获得 M-增广路
 k=k+1;
 end
 for(i=1:k)
 if(M(P(i,1),P(i,2)))
 M(P(i,1),P(i,2))=0; %将匹配 M 在增广路 P 中出现的边 去掉
 else M(P(i,1),P(i,2))=1;
 end
 end %将增广路 P 中没有在匹配 M 中出现的边加入 到匹配 M 中
 break;
 end
 end
 end
 if(pd)
 break;
 end
 end %假如X 中所有有标号的点都已去掉了标记*, 算法终止
 assign = M ; %显示最大匹配 M, 程序结束

5 thoughts on “数学建模国赛2011B题交巡警服务平台的设置与调度第五问的算法探讨

      1. 你好,我又仔细看了一下代码,发现 你定义了 assignment 函数,但是未使用。是不是 那个erfentu函数就是 assignment函数呢? O(∩_∩)O谢谢!

发表评论

电子邮件地址不会被公开。 必填项已用*标注