17

パスの「長さ」は、パス内のエッジの数です。

ソースとデスティネーションの頂点が与えられた場合、ソースの頂点から与えられた長さkのデスティネーションの頂点までのパスの数を見つけたいと思います。

  • 各頂点には何度でもアクセスできるため、からaへのパスbが次のようになっている場合、a -> c -> b -> c -> bそれは有効であると見なされます。これは、サイクルが存在する可能性があり、目的地を複数回通過できることを意味します。

  • 2つの頂点を複数のエッジで接続できます。したがって、頂点aと頂点が2つのエッジで接続されている場合、エッジ1とエッジ2を経由bするパスは異なると見なされます。a -> ba -> b

  • 頂点の数Nは<=70であり、パスの長さであるKは<= 10^9です。

  • 答えは非常に大きくなる可能性があるため、いくつかの数値を法として報告されます。

これが私がこれまでに考えたことです：

頂点を訪問済みとしてマークせずに幅優先探索を使用できます。各反復で、そのパスに必要なエッジの数「n_e」と、各エッジの各エッジの重複エッジの数の積「p」を追跡します。パスがあります。

n_eがkより大きい場合、検索検索は終了する必要があります。kn_eに等しい宛先に到達した場合は、検索を終了し、pパス数を追加します。

最短経路は必要なく、幅優先探索で使用されるQのサイズが十分でない可能性があるため、幅優先探索の代わりに深さ優先探索を使用できると思います。

私が考えている2番目のアルゴリズムは、このアプローチを使用したFloydWarshallのアルゴリズムに似ています。最短経路は必要ないので、これが正しいかどうかはわかりません。

私が最初のアルゴリズムで抱えている問題は、「K」が最大1000000000になる可能性があることです。つまり、検索は10 ^ 9のエッジがあり、各レベルでエッジ数が1ずつ増えるまで検索が実行されます。遅く、大きな入力で終了するかどうかはわかりません。

したがって、この問題を解決するには別のアプローチが必要です。どんな助けでも大歓迎です。

4

3 に答える 3

42

だから、これは私がこれのために覚えている気の利いたグラフ理論のトリックです。

隣接行列を作成しAます。ここで、との間にA[i][j]エッジがある場合は1、それ以外の場合は0です。ij

次に、とのk間の長さのパスの数は、A^kのエントリにすぎません。ij[i][j]

したがって、問題を解決するには、A行列の乗算を使用してA ^ kを構築および構築します（べき乗を行うための通常のトリックがここに適用されます）。次に、必要なエントリを検索します。

編集：オーバーフローの問題を回避するために、行列の乗算内でモジュラー演算を実行する必要がありますが、それははるかに詳細ではありません。

于 2013-01-11T05:51:25.377 に答える
5

実際、A ^kの[i][j]エントリは、各単純なグラフで、「パス」ではなく、まったく異なる「ウォーク」を示しています。「数学的帰納法」で簡単に証明できます。ただし、主要な問題は、特定のグラフでまったく異なる「パス」を見つけることです。解決すべきアルゴリズムはかなり異なりますが、上限は次のとおりです。

（n-2）（n-3） ...（nk）ここで、「k」はパスの長さを示す指定されたパラメーターです。

于 2013-04-26T12:33:28.300 に答える
2

上記の回答にさらにいくつかのコンテンツを追加しましょう（これは私が直面した拡張された問題であるため）。拡張された問題は

k指定された無向ツリー内の長さのパスの数を見つけます。

Aグラフの与えられた隣接行列の解は簡単です。Ak - 1とAkGを見つけて、対角線の上（または下）の要素のsの数を数えます。1

Pythonコードも追加しましょう。

import numpy as np

def count_paths(v, n, a):
    # v: number of vertices, n: expected path length
    paths = 0    
    b = np.array(a, copy=True)

    for i in range(n-2):
        b = np.dot(b, a)

    c = np.dot(b, a)
    x = c - b

    for i in range(v):
        for j in range(i+1, v):
            if x[i][j] == 1:
                paths = paths + 1

    return paths

print count_paths(5, 2, np.array([
                np.array([0, 1, 0, 0, 0]),
                np.array([1, 0, 1, 0, 1]),
                np.array([0, 1, 0, 1, 0]),
                np.array([0, 0, 1, 0, 0]),
                np.array([0, 1, 0, 0, 0])
            ])
于 2017-10-10T12:30:26.117 に答える