Floyd-Warshall算法描述
1)適用范圍：
a)APSP(All Pairs Shortest Paths)
b)稠密圖效果最佳
c)邊權可正可負
2)算法描述：
a)初始化：dis[u,v]=w[u,v]
b)For k:=1 to n
For i:=1 to n
For j:=1 to n
If dis[i,j]>dis[i,k]+dis[k,j] Then
Dis[I,j]:=dis[I,k]+dis[k,j]
c)算法結束：dis即為所有點對的最短路徑矩陣
3)算法小結：此算法簡單有效，由于三重循環結構緊湊，對于稠密圖，效率要高于執行|V|次Dijkstra算法。時間復雜度O(n^3)。
考慮下列變形：如(I,j)∈E則dis[I,j]初始為1,else初始為0，這樣的Floyd算法最后的最短路徑矩陣即成為一個判斷I,j是否有通路的矩陣。更簡單的，我們可以把dis設成boolean類型，則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍色部分，可以更直觀地得到I,j的連通情況。
標簽：
Floyd-Warshall
Shortest
Pairs
Paths
上傳時間：
2013-12-01
上傳用戶：dyctj
批處理感知器算法的代碼matlab
w1=[1,0.1,1.1;1,6.8,7.1;1,-3.5,-4.1;1,2.0,2.7;1,4.1,2.8;1,3.1,5.0;1,-0.8,-1.3;
1,0.9,1.2;1,5.0,6.4;1,3.9,4.0];
w2=[1,7.1,4.2;1,-1.4,-4.3;1,4.5,0.0;1,6.3,1.6;1,4.2,1.9;1,1.4,-3.2;1,2.4,-4.0;
1,2.5,-6.1;1,8.4,3.7;1,4.1,-2.2];
w3=[1,-3.0,-2.9;1,0.5,8.7;1,2.9,2.1;1,-0.1,5.2;1,-4.0,2.2;1,-1.3,3.7;1,-3.4,6.2;
1,-4.1,3.4;1,-5.1,1.6;1,1.9,5.1];
figure;
plot(w3(:,2),w3(:,3),'ro');
hold on;
plot(w2(:,2),w2(:,3),'b+');
W=[w2;-w3];%增廣樣本規范化
a=[0,0,0];
k=0;%記錄步數
n=1;
y=zeros(size(W,2),1);%記錄錯分的樣本
while any(y<=0)
k=k+1;
y=a*transpose(W);%記錄錯分的樣本
a=a+sum(W(find(y<=0),:));%更新a
if k >= 250
break
end
end
if k<250
disp(['a為：',num2str(a)])
disp(['k為：',num2str(k)])
else
disp(['在250步以內沒有收斂，終止'])
end
%判決面：x2=-a2*x1/a3-a1/a3
xmin=min(min(w1(:,2)),min(w2(:,2)));
xmax=max(max(w1(:,2)),max(w2(:,2)));
x=xmin-1:xmax+1;%(xmax-xmin):
y=-a(2)*x/a(3)-a(1)/a(3);
plot(x,y)
標簽：
批處理
算法matlab
上傳時間：
2016-11-07
上傳用戶：a1241314660
