閉パケットを伝達するwarshallアルゴリズムを求めます
859 ワード
————————————————————————————
Question:Rは集合S上に定義された二元関係であり,Rの伝達閉包を求める.
Input:relation R,set A
Output:t(R),which is the transitive closure of R
Solution:Warshall algorithm
————————————————————————————
転送閉パケット(transitive closure)R*=R 1≦R 2≦R 3≦・・・ ∪ Rn
説明すると,関係Rの伝達閉パケットも一つの関係であり,R*で表すこともt(R)で表すこともできる.
正直に言うと、離散数学の授業でここを話していたとき、私は聞いていなかったが、その後、小測が間違っていても補充しなかった.最近この2,3日顧雨軒と教室棟の黒板の上で復習を討論して、warshallアルゴリズムを討論して、構想を整理して、これらを書きました.
Warshallアルゴリズムは次のように動作します.
まずRをマトリクスで表し、
次に、最初の列から列ごとに巡回し、i番目の列に対して各要素を上から下まで巡回します.
i列j行目の要素が1である場合、i行目をj行目に対応付けて加算する.
pythonシミュレーションコード:
Question:Rは集合S上に定義された二元関係であり,Rの伝達閉包を求める.
Input:relation R,set A
Output:t(R),which is the transitive closure of R
Solution:Warshall algorithm
————————————————————————————
転送閉パケット(transitive closure)R*=R 1≦R 2≦R 3≦・・・ ∪ Rn
説明すると,関係Rの伝達閉パケットも一つの関係であり,R*で表すこともt(R)で表すこともできる.
正直に言うと、離散数学の授業でここを話していたとき、私は聞いていなかったが、その後、小測が間違っていても補充しなかった.最近この2,3日顧雨軒と教室棟の黒板の上で復習を討論して、warshallアルゴリズムを討論して、構想を整理して、これらを書きました.
Warshallアルゴリズムは次のように動作します.
まずRをマトリクスで表し、
次に、最初の列から列ごとに巡回し、i番目の列に対して各要素を上から下まで巡回します.
i列j行目の要素が1である場合、i行目をj行目に対応付けて加算する.
pythonシミュレーションコード:
# R , 。
def warshall(R):
n = size(R)
for i in range(0,n-1):
for j in range(0,n-1):
if R[j][i]==1:
R[j][:]+=R[i][:]
return R