1、精選文檔圖論 作業(yè)第一題： 記“該公司第i年初購買新設(shè)備”的大事為 Vi ,為制定五年方案，設(shè)置變量 V1，V2，V3，V4，V5，V6 。其中V6表示第五年底。可行的方案如下。 Vi到Vj的權(quán)重由題目表格可以得到，下面是鄰接矩陣0 16 22 30 41 59Inf 0 16 22 30 41a=Inf Inf 0 17 23 31Inf Inf Inf 0 17 23Inf Inf Inf Inf 0 18Inf Inf Inf Inf Inf 0在MATLAB中function d,DD=dijkstra_aiwa(D,s)m,n=size(D);d=inf.*ones(1,m);d(1

2、,s)=0;dd=zeros(1,m);dd(1,s)=1;y=s; DD=zeros(m,m);DD(y,y)=1;counter=1;while length(find(dd=1)<m for i=1:m if dd(i)=0 d(i)=min(d(i),d(y)+D(y,i); end end ddd=inf; for i=1:m if dd(i)=0&&d(i)<ddd ddd=d(i); end end yy=find(d=ddd); counter=counter+1; DD(y,yy(1,1)=counter; DD(yy(1,1),y)=counte

3、r; y=yy(1,1); dd(1,y)=1;end最終得到，d = 0 16 22 30 41 53當(dāng)節(jié)點為6個時，最短路徑53，可以看出V0到V3,V3到V5，即最開頭買一臺，第四年年初買可以最劃算。其次問：針對于其次問問題，定義四維狀態(tài)向量（m,n,p,q）0,1，m、n、p、q分別為人、狼、羊和蔬菜的狀態(tài)，當(dāng)狀態(tài)為0時，該物處在對岸，當(dāng)狀態(tài)為1時，該物在此岸。由于題目要求，狼不能和羊一個狀態(tài)，羊不能和蔬菜一個狀態(tài)，窮舉得可行狀態(tài)（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）

4、,（0,0,0,1）,（0,0,0,0）。 定義狀態(tài)轉(zhuǎn)移向量為M=（1,0,0,0），（1,0,1,0），（1,0,0,1），（1,0,0,1）分別表示只是人的移動，人帶著狼轉(zhuǎn)移，人帶著羊轉(zhuǎn)移和人帶著蔬菜轉(zhuǎn)移。MATLAB代碼a=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;%ÿһÐÐÊÇÒ»¸ö¿ÉÐÐ×&#

5、180;̬b=1 0 0 0;1 1 0 0;1 0 1 0;1 0 0 1;%ÿһÐÐÊÇÒ»¸öתÒÆ״̬ w=zeros(10);%ÁÚ½Ó¾ØÕó³õʼ»¯for i=1:9for j=i+1:10for k=1:4if findstr(xor(a(i,:),b(k,:),a(j,:)w(i,j) = 1;endendendendw=w'%±ä³ÉÏÂÈý½Ç¾ØÕóc=sparse(w);%¹¹ÔìÏ¡Êè¾ØÕóx,y,z=graphshortestpath(c,