第一次来CSDN求教大神们!恳请多多指教!!我在用matlab编写一个小算法,这个算法里面可能多次循环的嵌套,导致得到最终结果(输入Reader=800,Tag=1000,r=30,范围为[1,900]的时候),花费了将近800多秒!!!劳驾各方神圣给我指点迷津,降低我这个算法的时间复杂度,有什么好点子好方法么?
更新:原题是RFID网络冗余阅读器去除算法,即要去除掉系统网络中冗余的阅读器,就是图中的红色圈圈,下图是已经去除后的效果。
【算法执行结果图如下】
- 算法设计:
① definition:
cc(covered count) ——每个tag被reader覆盖的数量(黑点到红圈圆心的距离:D<=r)
nc(neighbor count)——每个reader邻居的数量(两个圆圈原点距离:L<=2r)
ncc(neighbor cover count)——每个reader的邻居所覆盖的所有tag数量的总和② steps:
a.找出所有cc=1的tag,由于这些tag只被独有的reader覆盖,所以这些对应的reader为非冗余reader,其下所覆盖的所有tag均被该reader锁定(hold);
b.当所有cc=1对应的reader被找到后,即剩下的tag的cc均>1,剩下的reader根据nc值由低到高依次循环执行c,d,e操作(邻居越多的阅读器在实际中越容易对其他阅读器产生干扰);
c.当有多个nc值相等的reader,判断相同nc值的reader的ncc值大小,根据ncc的值由高到低循环进行d,e操作;
d.该reader中所有的tag的cc值减1,该reader为冗余reader;
e.找出c操作中cc=1的tag,重复a操作,假如依旧没有cc=1的tag,重复b操作;
f.直到所有tag均被reader锁定后,去除结束。
【附代码:matlab】
代码写的不漂亮望大神们见谅!!
我没有币实在不好意思啊 T_T..
%x1,y1,x2,y2是随机数,在其他函数里产生的已知变量,Reader, Tag, r均为GUI上输入的变量,输出为冗余阅读器数量和整个算法执行的时间
function [tcbaredundant,TCBAtime]=TCBA(x1,y1,x2,y2,Reader,Tag,r)
%TCBA算法:
tic;
%%%%%%%%%%%%%【计算tagcc的值】%%%%%%%%%%%%%%%%
tagcc=zeros(1,Tag);
for j=1:Reader
for i=1:Tag
if showdistance(x1(j),y1(j),x2(i),y2(i))<=r
tagcc(i)=tagcc(i)+1;
end
end
end
% disp(strcat('tagcc: ',num2str(tagcc)));
%%%%%%%%%%%%%%%%%%%%%【找出cc=1的tag对应的reader(判断reader是否冗余),对于非冗余的reader所覆盖的tag进行锁定】%%%%%%%%%%%%%%%%%%%%%%
tagholder=zeros(1,Tag);
readerclosed=zeros(1,Reader);
readerredundant=ones(1,Reader);
for j=1:Reader
for i=1:Tag
if showdistance(x1(j),y1(j),x2(i),y2(i))<=r && tagcc(i)==1 && tagholder(i)==0
tagholder(i)=j;
for k=1:Tag
if showdistance(x1(j),y1(j),x2(k),y2(k))<=r && tagholder(k)==0
tagholder(k)=j;
end
end
readerclosed(j)=1;
readerredundant(j)=0;
end
end
end
% disp(strcat('tagholder: ',num2str(tagholder)));
% disp(strcat('readerclosed: ',num2str(readerclosed)));
% disp(strcat('readerredundant: ',num2str(readerredundant)));
%%%%%%%%%%%%%【NC】%%%%%%%%%%%%%%%%
for a=1:Reader
reader.nc(a)=0;
reader.ncc(a)=0;
for b=1:Reader
if showdistance(x1(a),y1(a),x1(b),y1(b))<=2*r && showdistance(x1(a),y1(a),x1(b),y1(b))>0 &&readerclosed(a)==0 && readerredundant(a)==1
reader.nc(a)=reader.nc(a)+1;
%%%%%%%%%%%%%【NCC】%%%%%%%%%%%%%%%%
for i=1:Tag
if showdistance(x1(b),y1(b),x2(i),y2(i))<=r
reader.ncc(a)=reader.ncc(a)+1;
end
end
end
end
end
% disp(strcat('reader.nc: ',num2str(reader.nc)));
% disp(strcat('reader.ncc: ',num2str(reader.ncc)));
%%%%%%%%%%%%%【对于冗余的reader进行操作】%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%【根据reader的nc和ncc值由高到低进行筛选】%%%%%%%%%%%%%%%%
while (length(find(reader.nc==0))~=Reader)
reader.ncmax=find(reader.nc==max(reader.nc));
reader.ncc2=reader.ncc(reader.ncmax);
reader.nccmax=reader.ncmax(find(reader.ncc2==max(reader.ncc2)));
ncc=reader.nccmax(1);
% disp(strcat('reader.ncmax对应rid: ',num2str(reader.ncmax)));
% disp(strcat('reader.ncmax对应ncc值(reader.ncc2): ',num2str(reader.ncc2)));
% disp(strcat('reader.nccmax对应rid(ncc),即要去除的reader为: ',num2str(ncc)));
for k=1:Tag
if showdistance(x1(ncc),y1(ncc),x2(k),y2(k))<=r
tagcc(k)=tagcc(k)-1;
end
end
reader.nc(ncc)=0;
readerclosed(ncc)=1;
%对剩下的reader重复最开始的操作进行判断是否为冗余reader
for j=1:Reader
if readerclosed(j)==0 && readerredundant(j)==1
for i=1:Tag
if showdistance(x1(j),y1(j),x2(i),y2(i))<=r && tagcc(i)==1 && tagholder(i)==0
tagholder(i)=j;
for h=1:Tag
if showdistance(x1(j),y1(j),x2(h),y2(h))<=r && tagholder(h)==0
tagholder(h)=j;
end
end
readerclosed(j)=1;
readerredundant(j)=0;
end
end
end
end
end
% disp(strcat('~tagcc: ',num2str(tagcc)));
% disp(strcat('~readerclosed: ',num2str(readerclosed)));
% disp(strcat('~readerredundant: ',num2str(readerredundant)));
% disp(strcat('~reader.nc: ',num2str(reader.nc)));
% disp(strcat('~reader.ncc: ',num2str(reader.ncc)));
% disp(strcat('~tagholder: ',num2str(tagholder)));
%%%%%%%%%%%%%%%%%%%%%【去除没有hold任何标签的reader】%%%%%%%%%%%%%%%%%%%%%%
a=unique(tagholder);
holderid=a(find(a~=0));
disp(strcat('覆盖有标签的reader的rid为:',num2str(holderid)));
cla(gca);
for k=holderid
sita=0:pi/20:2*pi;%角度[0,2*pi]
xr=x1(k)+r*cos(sita);
yr=y1(k)+r*sin(sita);
readers=plot(xr,yr,'-r');
hold on;
end
%对坐标轴进行相关设置
[tags,TO,tid]=tag(x2,y2,Tag);
h=legend([readers,tags],'reader','tag');
set(h,'color',[1 1 0]);
%%%%%%%%%%%%%【计算冗余的reader数量】%%%%%%%%%%%%%%%%
tcbaredundant=Reader-length(holderid);
fprintf('TCBA算法得到冗余阅读器个数:%d\n',tcbaredundant);
%%%%%%%%%%%%%%%%%%%%%【TCBA算法执行所需时间】%%%%%%%%%%%%%%%%%%%%%%
time=toc;
TCBAtime=num2str(time);
fprintf('TCBA算法执行所需时间为:%s秒\n',TCBAtime);
fprintf('------------------------------------------------\n');