3

G を、隣接行列によって与えられる n 個の頂点と m 個の辺を持つ DAG とします。クロージャーも行列の形で計算する必要があります。各単語が b ビットであるコンピューターがあります。そして、推移閉包を計算するアルゴリズムを見つける必要があります(n^2+nm/b)

bits意味と使い方がよくわからない

dag の推移閉包を見つけるためのアルゴリズムを追加します。

TransitiveForDAG (Graph G)
int T[1...n,1...n] ={0,...,0}
List L <- TopologicalSort(G)
For each v in reverse(L)
   T[v,v]<-1
    For each u in Adj[v]
       for j<-1,...,n do
         T[v,j]<-T[v,j] or T[u,j]
4

2 に答える 2

1

ビットの意味がわからないと言うので、それから始めましょう。

  • ビットはデジタル情報の最小単位です-0または1
  • Wordは、コンピューターによって一度に処理されるデータの単位です。プロセッサは個々のビットを取得して処理するのではなく、それらの小さなチャンクを処理します。今日のほとんどのコンピュータアーキテクチャは、32ビットまたは64ビットのワードを使用しています。

では、バイナリデータの単語をどのように処理するのでしょうか。ほとんどのプログラミング言語では、数値データ型を使用してデータを格納します。それらを操作するために、ほとんどの言語はビット単位の演算子を提供します-ビット単位または（|）はここで必要なものです。

では、アルゴリズムを高速化するにはどうすればよいでしょうか。T行列を見てください。0または1の値のみを持つことができます-その情報を格納するには1ビットで十分です。マトリックスのフィールドを1つずつ処理しています。アルゴリズムの最後の行を処理するたびに、v番目の行から1ビット、u番目の行から1ビットのみを使用します。

前に述べたように、プロセッサはこれらの各ビットを読み取って処理するためにワード全体を読み取る必要があります。それは効果がありません。ほとんどの場合、そのような詳細は気にしないでしょうが、ここでは重要な場所にあります。最後の行は最も内側のサイクルにあり、非常に何度も実行されます。

さて、どうすればもっと効果的になることができますか？データの保存方法を変更します-行列のデータ型として単語の長さの型を使用します。元の行列のb値を、新しい行列のすべての値に格納します。これはパッキングと呼ばれます。アルゴリズムの動作方法により、行ごとに格納する必要があります。i番目の行の最初の値には、元のマトリックスのi番目の行の最初のb個の値が含まれます。

それとは別に、アルゴリズムの最も内側のサイクルを変更するだけで済みます。サイクルは個々のフィールドではなく単語を反復処理し、内部ではビット単位またはを使用して単語全体を一度に処理します。

T[v,j]<-T[v,j] | T[u,j]

サイクルは、アルゴリズムの時間計算量を生成するものです。これで、反復回数がb倍少なくなったため、複雑さが次のようになります。(n^2+nm/b)

于 2013-01-04T11:37:46.250 に答える
0

単純なグラフの場合、隣接行列の各エントリは 0 または 1 であり、1 ビットで表すことができます。bこれにより、エントリを各コンピューター ワードにパックすることで、行列のコンパクトな表現が可能になります。次に課題は、正しいビット操作演算子を使用して (クロージャを計算するために) 行列乗算を実装することです。

于 2013-01-02T21:42:21.997 に答える