模拟退火,贪婪算法

B5 孙月第八次作业

1、仔细阅读文献《球度误差的网格搜索算法》，编程实现其实例验证部分，并与此文献的结果比较。解：

Matlab程序为： clear

M=load('第一题数据.txt');

P=[-0.0047304,-0.0017027,0.0018167]; f=0.021; n=41; l=1;

zuobiao=zeros(70000,3);%创建m*n全零矩阵 for i=1:n

x(i)=P(1)-f/2+f*(i-1)/n; for j=1:n

y(j)=P(2)-f/2+f*(j-1)/n; for k=1:n

z(k)=P(3)-f/2+f*(k-1)/n; for c=1:36

R(c)=sqrt((M(c,1)-x(i))^2+(M(c,2)-y(j))^2+(M(c,3)-z(k))^2); end

Rmax(l)=max(R,[],2); Rmin(l)=min(R,[],2); W(l)=Rmax(l)-Rmin(l);

zuobiao(l,:)=[x(i),y(j),z(k)]; l=l+1; end end end

w=sort(W,2); %最大内接球法

Rout=min(Rmax,[],2);

Oout=zuobiao(find(Rmax==Rout),:) rout=Rmin(find(Rmax==Rout)); Fout=Rout-rout %最小外接球法

rin=max(Rmin,[],2);

Oin=zuobiao(find(Rmin==rin),:)

Rin=Rmax(find(Rmin==rin)); Fout=Rin-rin %最小区域法

Farea=min(w,[],2)

2、用贪婪算法和模拟退火算法分别求下面背包问题假设有12个物品，质量（磅）和价值（元）如下

2 5 13 2 5 14 17 16

8 0 1 4 5 114 3 1118 17 4 0 3 1 3 0 6

包的最大容量为46磅，则应该装那些东西价值最大？

贪婪算法得到应该装入重量为2磅，5磅，5磅，3磅，2磅，4磅，7磅，6磅,10磅物品时价值最大为5+10+4+3+11+10+16++4+13=76元 Matlab程序如下： n=12;x=zeros(1,n);

w=[4 2 7 5 5 2 3 10 11 18 6 14];%排序后的 v=[10 5 16 11 10 3 4 13 8 13 4 7]; tw=0;%已装入背包的重量； for i=1:n

if tw+w(i)

tv=sum(v(find(x)));

模拟退火算法得到应该装入重量为2磅，5磅，2磅，5磅，10磅，4磅，11磅，7磅时价值最大为5+10+3+11+13+10+8+16=76元 Matlab程序为：

clc,clear

a = 0.95

k = [5;10;13;4;3;11;13;10;8;16;7;4];

k = -k; % 模拟退火算法是求解最小值，故取负数 d = [2;5;18;3;2;5;10;4;11;7;14;6]; n= 12;

sol_new = ones(1,n); % 生成初始解 E_current = inf;E_best = inf;

% E_current是当前解对应的目标函数值（即背包中物品总价值）； % E_new是新解的目标函数值； % E_best是最优解的

sol_current = sol_new; sol_best = sol_new; t0=97; tf=3; t=t0; p=1;

while t>=tf for r=1:100

%产生随机扰动

tmp=ceil(rand.*n);

sol_new(1,tmp)=~sol_new(1,tmp); %检查是否满足约束 while 1

q=(sol_new*d

p=~p; %实现交错着逆转头尾的第一个1 tmp=find(sol_new==1); if p

sol_new(1,tmp)=0; else

sol_new(1,tmp(end))=0; end else

break end end

% 计算背包中的物品价值 E_new=sol_new*k; if E_new

% 把冷却过程中最好的解保存下来 E_best=E_new; sol_best=sol_new; end else

if rand

sol_new=sol_current; end end end t=t.*a; end

disp('最优解为：') sol_best

disp('物品总价值等于：') val=-E_best; disp(val)

disp('背包中物品重量是：') disp(sol_best * d)