第一次 图论 作业

第一次图论作业第一次图论作业第一次图论作业资料仅供参考文件编号：2022年4月第一次图论作业版本号：A修改号：1页次：1.0审核：批准:发布日期：图论作业第一题： 记“该公司第i年初购买新设备”的事件为Vi,为制定五年计划，设置变量V1，V2 Vi到Vj的权重由题目表格可以得到01622304159Inf016223041InfInf0172331InfInfInf01723InfInfInfInf018InfInfInfInfInf0在MATLAB中function[d,DD]=dijkstra_aiwa(D,s)[m,n]=size(D);d=inf.*ones(1,m);d(1,s)=0;dd=zeros(1,m);dd(1,s)=1;y=s;DD=zeros(m,m);DD(y,y)=1;counter=1;whilelength(find(dd==1))<mfori=1:mifdd(i)==0d(i)=min(d(i),d(y)+D(y,i));endendddd=inf;fori=1:mifdd(i)==0&&d(i)<dddddd=d(i);endendyy=find(d==ddd);counter=counter+1;DD(y,yy(1,1))=counter;DD(yy(1,1),y)=counter;y=yy(1,1);dd(1,y)=1;end最后得到，d=01622304153当节点为6个时，最短路径53，可以看出V0到V3,V3到V5，即最开始买一台，第四年年初买可以最划算。第二问： 针对于第二问问题，定义四维状态向量（m,n,p,q）∈{0,1}，m、n、p、q分别为人、狼、羊该物处在对岸，当状态为1时，该物在此岸。由于题目要求，狼不能和羊一个状态，羊不能和蔬菜一个状态，穷举得可行状态（1,1,1,1）,（1,1,1,0）,（1,1,0,1）,（1,0,1,1）,（1,0,1,0）,（0,1,0,1）,（0,1,0,0）,（0,0,1,0）,（0,0,0,1）,（0,0,0,0）。 定义状态转移向量为M=（1,0,0,0），（1,0,1,0），（1,0,0,1），（1,0,0,1）分别表示只是人的移动，人带着狼转移，人带着羊转移和人带着蔬菜转移。 MATLAB代码a=[1111;1110;1101;1011;1010;0101;0100;0010;0001;0000];%ÿһÐÐÊÇÒ»¸ö¿ÉÐÐ״̬b=[1000;1100;1010;1001];%ÿһÐÐÊÇÒ»¸öתÒÆ״̬w=zeros(10);%ÁÚ½Ó¾ØÕó³õʼ»¯fori=1:9forj=i+1:10fork=1:4iffindstr(xor(a(i,:),b(k,:)),a(j,:))w(i,j)=1;endendendendw=w';%±ä³ÉÏÂÈý½Ç¾ØÕóc=sparse(w);%¹¹ÔìÏ¡Êè¾ØÕó[x,y,z]=graphshortestpath(c,1,10,'Directed',0)最后得到输