·基本信息Practical Antenna Handbook, 4th EditionbyJoseph J.Carr作者 Jeseph J. Carr 美國國防部航空電子(avionics)資深工程師one of the worlds leading and prolific writer and working scientist on electronics and radio, and an
給定n個(gè)整數(shù)a , a , ,an 1 2 組成的序列。序列中元素i a 的符號定義為:
ï î
ï í
ì
- <
=
>
=
1 0
0 0
1 0
sgn( )
i
i
i
i
a
a
a
a
符號平衡問題要求給定序列的最長符號平衡段的長度L,即:
þ ý ü
î í ì
= + - = å
=
£ £ £
max 1| sgn( ) 0
1
j
k i
i j n k
L j i a 。
例如,當(dāng)n=10,相應(yīng)序列為:1,1,-1,-2,0,1,3,-1,2,-1 時(shí),L=9。
Floyd-Warshall算法描述
1)適用范圍:
a)APSP(All Pairs Shortest Paths)
b)稠密圖效果最佳
c)邊權(quán)可正可負(fù)
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)算法結(jié)束:dis即為所有點(diǎn)對的最短路徑矩陣
3)算法小結(jié):此算法簡單有效,由于三重循環(huán)結(jié)構(gòu)緊湊,對于稠密圖,效率要高于執(zhí)行|V|次Dijkstra算法。時(shí)間復(fù)雜度O(n^3)。
考慮下列變形:如(I,j)∈E則dis[I,j]初始為1,else初始為0,這樣的Floyd算法最后的最短路徑矩陣即成為一個(gè)判斷I,j是否有通路的矩陣。更簡單的,我們可以把dis設(shè)成boolean類型,則每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”來代替算法描述中的藍(lán)色部分,可以更直觀地得到I,j的連通情況。
function [U,center,result,w,obj_fcn]= fenlei(data)
[data_n,in_n] = size(data)
m= 2 % Exponent for U
max_iter = 100 % Max. iteration
min_impro =1e-5 % Min. improvement
c=3
[center, U, obj_fcn] = fcm(data, c)
for i=1:max_iter
if F(U)>0.98
break
else
w_new=eye(in_n,in_n)
center1=sum(center)/c
a=center1(1)./center1
deta=center-center1(ones(c,1),:)
w=sqrt(sum(deta.^2)).*a
for j=1:in_n
w_new(j,j)=w(j)
end
data1=data*w_new
[center, U, obj_fcn] = fcm(data1, c)
center=center./w(ones(c,1),:)
obj_fcn=obj_fcn/sum(w.^2)
end
end
display(i)
result=zeros(1,data_n) U_=max(U)
for i=1:data_n
for j=1:c
if U(j,i)==U_(i)
result(i)=j continue
end
end
end