图论习题及答案

作业解答练习题2利用matlab编程FFD算法完成下题：设有6种物品，它们的体积分别为：60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。解答一：function[num,s]=BinPackingFFD(w,capacity)%一维装箱问题的FFD（降序首次适应）算法求解:先将物体按长度从大到小排序,%然后按FF算法对物体装箱%输入参数w为物品体积，capacity为箱子容量%输出参数num为所用箱子个数，s为元胞数组，表示装箱方案，s{i}为第i个箱子所装%物品体积数组%例w=[60,45,35,20,20,20];capacity=100;%num=3,s={[1,3],[2,4,5],6};w=sort(w,'descend');n=length(w);s=cell(1,n);bin=capacity*ones(1,n);num=1;fori=1:nforj=1:num+1ifw(i)bin(j)bin(j)=bin(j)-w(i);s{j}=[s{j},i];ifj==num+1num=num+1;endbreak;endendends=s(1:num);解答二：clear;clc;V=100;v=[604535202020];n=length(v);v=fliplr(sort(v));box_count=1;x=zeros(n,n);V_Left=100;fori=1:nifv(i)=max(V_Left)box_count=box_count+1;x(i,box_count)=1;V_Left=[V_LeftV-v(i)];elsej=1;while(v(i)V_Left(j))j=j+1;endx(i,j)=1;V_Left(j)=V_Left(j)-v(i);endtemp=find(x(i,:)==1);fprintf('第%d个物品放在第%d个容器\n',i,temp)endoutput:第1个物品放在第1个容器第2个物品放在第2个容器第3个物品放在第1个容器第4个物品放在第2个容器第5个物品放在第2个容器第6个物品放在第3个容器解答三：functionbox_count=FFD(x)%降序首次适应算法v=100;x=fliplr(sort(x));%v=input('请输入箱子的容积:');n=length(x);I=ones(n);E=zeros(1,n);box=v*I;box_count=0;fori=1:nj=1;while(j=box_count)ifx(i)box(j)j=j+1;continue;elsebox(j)=box(j)-x(i);E(i)=j;break;endendifjbox_countbox_count=box_count+1;box(box_count)=box(box_count)-x(i);E(i)=j;endenddisp(E);在命令窗口输入：x=[60,45,35,20,20,20];FFD(x)121223ans=3练习题5“超市大赢家”提供了50种商品作为奖品供中奖顾客选择,车的容量为1000dm3,奖品i占用的空间为widm3,价值为vi元,具体的数据如下:vi={220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1}wi={80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1}。问如何装车才能总价值最大。解答：clear;clc;v=[220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1];w=[80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1];totalw=1000;limitw=1000;n=length(w);fori=1:nf(1,i)=v(i)/w(i);f(2,i)=w(i);f(3,i)=i;endfori=1:(n-1)forj=(i+1):niff(1,i)f(1,j)t=f(1,i);f(1,i)=f(1,j);f(1,j)=t;t=f(2,i);f(2,i)=f(2,j);f(2,j)=t;t=f(3,i);f(3,i)=f(3,j);f(3,j)=t;endendendtotalv=0;a=[];fori=1:niff(2,i)=limitwa=[a,f(3,i)];%disp(f(3,i));limitw=limitw-f(2,i);totalv=totalv+f(1,i)*f(2,i);endendatotalvtotalw=totalw-limitw结果a=Columns1through2110401725281619353782620131124279234114Columns22through272263014247totalv=3103totalw=1000练习题8对最后一个求有向圈的示例用matlab程序实现。解答：H=[01000;00011;11100;00101;01000];n=size(H,1);%顶点个数p=zeros(1,n);%存储搜索过的顶点X=zeros(n,n);%用来设置禁止矩阵，往回返的时候设置此路已被搜索k=1;p(1)=1;%第一个点作为初始点开始搜索whilep(1)=n%每个顶点都作为初始点搜索包含p(1)的有向圈，i=p(1)+1;%当前点k往后搜索时都是从p(1)+1开始，从而也可以搜索下标小于k的点whilei=n%还有后续点没有搜索（这些点有可能比当前点k小）if(H(p(k),i)==1)&(X(p(k),i)==0)&isempty(find(p==i))%满足三个条件k=k+1;%搜索路径上增加一个点p(k)=i;%搜索路径向前延伸一个点elsei=i+1;%当前被搜索点不满足条件，换下一个点endendifin%k点往后的所有点都被搜索ifH(p(k),p(1))==1%有圈，每次搜索的都是包含初始点的圈disp(p(1:k));%输出圈end%不管有没有圈，此时k点要往回返ifk1%路径上不止出发点forj=1:nX(p(k),j)=0;%取消以前的限制通行endX(p(k-1),p(k))=1;%增加此路已搜索p(k)=0;%撤销路径上的k点k=k-1;%返回上一个点作为当前点else%返回到出发点了p(1)=p(1)+1;%换下一个出发点（初始点）endendend运行结果：1243245243253练习题9选址问题现准备在7个居民点中设置一银行，路线与距离如下图，问设在哪个点，可使最大服务距离最小？若设两个点呢？1v4v3v2v5v6v7v3265.15.2435.18.11v4v3v2v5v6v7v3265.15.2435.18.1解答：第一步：function[D,R]=floyd(A)%用floyd算法实现求任意两点之间的最短路程。可以有负权%参数D为连通图的权矩阵A=[03infinfinfinfinf302infinf1.5infinf206inf2.54infinf60infinf3infinfinfinf01.5infinf1.52.5inf1.501.8infinf43inf1.80];D=A;n=length(D);fori=1:nforj=1:nR(i,j)=i;%赋路径初值endendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);%更新D(i,j)，说明通过k的路程更短R(i,j)=R(k,j);%更新R(i,j)，需要通过kendendendhl=0;fori=1:nifD(i,i)0hl=1;break;%跳出内层的for循环endendif(hl==1)fprintf('有负回路')break;%跳出最外层循环endendD运行结果：D=03.00005.00009.30006.00004.50006.30003.000002.00006.30003.00001.50003.30005.00002.000006.00004.00002.50004.00009.30006.30006.000006.30004.80003.00006.00003.00004.00006.300001.50003.30004.50001.50002.50004.80001.500001.80006.30003.30004.00003.00003.30001.80000第二步：对于第一问在矩阵D中每一个取大得到一列数，再在这列数中取小，[m,n]=size(D);p=[];fori=1:mp(i)=max(D(i,:));endfori=1:mifp(i)==min(p)disp(i);endendmin(p)在顶点6建立银行，最大服务距离最小，最小是4.8.第三步：对于第二问任取两个点做集合，计算每个点到这个集合的最小值，再在这个最小值中取大，即在矩阵D中任取两行，对应比较取小得一向量，将所有这样的向量写成行向量构成一矩阵，然后用问题一的算法程序即可。a=0;b=[];n=size(D,1);fori=1:(n-1)forj=(i+1):na=a+1;fork=1:ns{a}=[ij];b(a,k)=min(D(i,k),D(j,k));endendendm=size(b,1);p=[];fori=1:mp(i)=max(b(i,:));endfori=1:mifp(i)==min(p)disp(s{i});endendmin(p)结果，在顶点2,4或2,7点建立银行都使得最大服务距离最小，最小值是3练习题10货物调运已知该地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个，其分布情况见下面的附件1。经核算该物资的运输成本为高等级公路2元/公里•百件，普通公路1.2元/公里•百件，假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运，请给出各个仓库应该从哪个企业调运。解答：首先建立各个交汇点的距离矩阵m。然后建立函数文件。%各仓库到各企业的最小运费functionmin_spend(m)c=[28,23,35,31,22,36,29,38];%仓库cc=[27,30];%国家储存库C=[c,cc];g=[8,15,11,27,7,10,17,14,28,16,18,25,6,5,39,35,13,40,4,29];%高级公路上的点n=length(g);A=zeros(42);fori=1:42forj=1:42ifm(i,j)~=0A(i,j)=1.2*m(i,j);%普通公路上每百件的运费elseA(i,j)=inf;endendendfori=1:nforj=1:nA(g(i),g(j))=2*A(g(i),g(j))/1.2;%高