0

推移性を見つけるためにCプログラムを書いています。2D配列では、との場合 adj[0][1] = 1 、もとしてマークをadj[1][2] = 1付けたいと思います。これは、マトリックス内の推移的な関係にも当てはまります。adj[0][2]1

このためのコードを手伝ってください。

    adj_matrix[j1][j2]=1;

    for(i=0;i<26;i++)
    {
        if (adj_matrix[i][j1])
        adj_matrix[i][j2]=1;

    }
    for(i=0;i<26;i++)
    {
        if(adj_matrix[j2][i])
        {
        adj_matrix[j1][i]=1;
        }
    }
4

3 に答える 3

1

私はこれがうまくいくと信じています：

reachable_matrix = adj_matrix
length_of_path = 1

while(length_of_path < (N - 1)) {
    for(i = 0; i < N; ++i) {
        for(j = 0; j < N; ++j) {
            tmp_matrix[i][j] = 0;
            for(k = 0; k < N; ++k) {
                tmp_matrix[i][j] ||= reachable_matrix[i][k] && reachable_matrix[k][j]; // Can I reach from i to j through k?
            }
        }
    }
    reachable_matrix = tmp_matrix;
    length_of_path *= 2;
}

リチャードがコメントしたように、これはグラフの横断可能性を計算することと同等です。

長さ1のパスがからにadj_matrix[i][j]いくつあるかを示す数と考えることができます。次に（その補助行列はの累乗）は、任意の2つのノードの間に少なくとも長さのパスがいくつあるかを示します。ijadj_matrix ** lll

私のコードの内側のループ（変数i、j、kでのループ）は基本的にreachable_matrixbyの乗算でreachable_matrixあり、それをに格納しますtmp_matrix。加算と乗算の代わりに、論理和とandを使用します。正確な数には関心がないため、その真理値でのみ。

外側のループはreachable_matrix、それが発生するパワー（チェックしたパスの長さ）が。よりも小さい間、二乗を続けますN - 1。N - 1この長さのパスがある場合は、グラフ内のすべてのノードにアクセスしていることを意味するため、で停止するだけで十分です。より多くのステップを持つパスには、必然的にサイクルが含まれている必要があります。一方、私は物事を単純にするために正確に2乗べき乗を実行しません（少し効率が悪いと思いますが、それについてはわかりません）。長いパスを試しても害はないためです。

全体として、このアルゴリズムの複雑さはO（log（N）* N ** 3）です。

于 2012-12-08T12:05:16.570 に答える
1

必要なのは「推移閉包アルゴリズム」です

Floyd-Warshallアルゴリズムは、これらの1つの良い例ですが、 Johnsonのアルゴリズムのような他の多くの（多くの）アルゴリズムがあります。Google Scholarですばやく検索すると、他のいくつかの情報源とより技術的な説明が表示されます。

元の形式のFloyd-Warshallアルゴリズムのコード（接続されているすべてのポイント間の最短経路を見つける）は次のとおりです。

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );

使用シナリオに合わせてこのコードを変更すると、次のようになります。

int dist[N][N];  // For some N
int i, j, k;
// Input data into dist, where dist[i][j] is the distance from i to j.
// If the nodes are unconnected, dist[i][j] should be infinity

for ( k = 0; k < N; k++ )
for ( i = 0; i < N; i++ )
for ( j = 0; j < N; j++ )
   if(dist[i][k] && dist[k][j])
      dist[i][j] = 1;

ここで下付き文字の順序に注意してください。この順序で添え字を付けると、動的計画法の基準が満たされ、パスが段階的に改善され、常に最適になります。

時間計算量はO（N ^ 3）です。

于 2012-12-08T12:42:06.870 に答える
0

これが正しいかどうか教えてください。

for(i=0;i<26;i++) 
for(j=0;j<26;j++)
for(k=0;k<26;k++)
if(adj_matrix[i][j] && adj_matrix[j][k])
adj_matrix[i][k]=1;
于 2012-12-08T06:47:11.360 に答える