3

問題を解決するためにあなたの助けが必要です。これはコーディング演習の一部であり、完全には解決できませんでした。

次のグラフがあるとします。

ここに画像の説明を入力

パスの最大長を計算するクラスを作成する必要があります。ルートがなく、各頂点を開始点として使用する必要があります。メソッドには最大繰り返し回数のパラメーターがあるため、この 1 の場合は各エッジを 1 回だけ通過でき、2 の場合は各エッジで最大 2 回。

この場合、repeats=1 の場合、最大パスは (B,A,C) になります。= 2 を繰り返すと、最大パスは (B、A、B、A、C、C) になります。

繰り返さずに問題を解決するために、隣接リストを作成し、DFS を実行してグラフ内のすべてのパスを検索し、最大のものを抽出することを考えました。これは、より単純なケースで機能するはずだと思います。

しかし、エッジを繰り返すことができる場合の方法がわかりません。この問題を解決するためにどのようなアルゴリズムを使用できますか? また、この問題に対するより効率的なアプローチを考えることができますか?

ありがとう

4

3 に答える 3

1

深さ優先検索の修正版を使用できます。

この場合、ノードを訪問済みとしてマークするだけでなく、ノードにいくつかの衛星データを追加します:訪問した回数と到達したときに訪問repeats済みとしてマークします。

ウィキペディアからの修正された疑似コード:

procedure DFS(G,v):
    increment v.timesVisited
    for all edges e in G.adjacentEdges(v) do
        if edge e.timesVisited < repeats then
            w ← G.adjacentVertex(v,e)
            if vertex w.timesVisited < repeats then
                e.timesVisited++
                recursively call DFS(G,w)
            else
                label e as a back edge

変更をテストしなかったので、うまくいくことを願っています。

于 2013-05-29T08:58:29.320 に答える
0

私は単純なアプローチを見ることができます.それは効率的ではありませんが、機能します.

2 つの要素:

  • 各エッジのエントリが 0 に設定されたハッシュマップ
  • DFS を使用してグラフをフェッチします (ハッシュマップをインクリメントおよびデクリメントしてフェッチを認識します)

ルートがないため、ノードごとにこのフェッチを行う必要があると思います。

すべての解決策を見つける必要がありますか、それとも近い解決策を探していますか?

この種の問題については、ウィキペディアでこれ以上の説明を見つけることができません: http://en.wikipedia.org/wiki/Longest_path_problem

于 2013-05-29T09:03:01.790 に答える
0

私の理解が正しければ、解決策はどちらの場合も似ています。

繰り返しのないソリューションの場合: 各ノードを root として取得し、その子で DFS を開始します。ノードの有効な子は、まだアクセスされていないノードです。

N-repeat 問題の場合: 有効な子ノードは、N 回未満のアクセスしかないノードです。DFS の各訪問で、そのノードの訪問カウンターを更新する必要があります。さらに、特定のノードのサブノードの探索が終了したら、その訪問カウンターをゼロにする必要があります。

于 2013-05-29T09:00:54.503 に答える