問題タブ [longest-path]

ここでいくつかの問題に遭遇します。すべてのディレクトリを検索して印刷できますが、最長のパスが見つかりません。これが私の端末統計です。

14102 1 1 /ホーム/ボブ/デスクトップ

ここで最長パスを出力できない理由がわかりません。私はPythonの初心者であり、英語の学習者でもあります。誤解がある場合はお知らせください。

更新: 現在、最長のパスを見つけることができますが、「~/」を使用してディレクトリを見つけることはできません。

これはエラーメッセージです。

最も広いパスと最長パスの質問の違いは何ですか? より具体的には、なぜ前者は最大スパニング ツリーを見つけることで解決できるのに、後者は解決できないのでしょうか。最大スパニング ツリーを描画すると、必ずしも最長パスが含まれているとは限らないことはすぐにわかりますが、この事実を真にする 2 つの質問の違いが何であるかについて頭を悩ますことはできません。

ありがとう。

有向グラフ (具体的には制御フロー グラフ) があり、各頂点には一連のプロパティがあります。

Vプロパティ を持つ頂点が与えられた場合、可能なパスに沿ったすべての頂点がプロパティを含むようPに、頂点への最長パスを見つけるアルゴリズムを見つけたい (または書きたい) と思います。EallVEP

例 1

次のグラフがあるとします。(アスキーでの描画が下手なのはご容赦ください。)

から始まり、可能なすべてのパスで常に保持されるV1最長パスは->です。他のパス、たとえば->は、常に有効であるという点で「有効」ですが、 ->が最も長いことに注意してください。PV1V7V1V6PV1V7

例 2

Pこの例は、が保持されないことを除いて、上記と同じV3です。

この場合、 から始まり、すべての可能なパスで常に保持されるV1最長パスは->です。パス->は有効ではありません。と の間にが保持されないパスがあるためです。PV1V6V1V7V1V7P

私の状況に関する追加メモ

• グラフは周期的である可能性があります。
• グラフは「小から中」のサイズで、おそらく 1000 個以下の頂点になります。
• 上記の例のように、グラフには必ずしも 1 つのルートと 1 つのリーフがあるとは限りません。

質問

そのようなパスを計算するための標準アルゴリズムはありますか?

ここ数日、Sling Blade Runner として知られるアーカイブされたITA Softwareのパズルを解こうとしています。パズルの要点は次のとおりです。

「スリング ブレード ランナーのように、重複する一連の映画のタイトルをどのくらい見つけられますか?」

次の映画タイトルのリストを使用します: MOVIES.TXT。「モッキンバードを殺すライセンス」のように、複数の単語が重複することは許されます。ソリューション内で同じタイトルを複数回使用することはできません。常に最大数のタイトルを生成するとは限らないヒューリスティックなソリューションが受け入れられます。効率と最適性の合理的なトレードオフを求めてください。

ファイルMOVIES.TXTには、6561 の映画タイトルがアルファベット順に含まれています。

私の解決策の試みには、いくつかの部分があります。

グラフの構築:

私がしたことは、すべての映画のタイトルを、チェーンできる他のすべての映画のタイトルにマップすることでした (右側にあります)。私のグラフはMap[String, List[String]]. このプロセスを使用して作成されたグラフは、こちら で確認できます。

グラフ トラバーサル:

すべてのノード (マップ内のすべてのキー) を検索の開始ノードとして使用して、深さ優先検索を実行しました。検索中に各ノードが訪問された深さを追跡し、これは DFS によって返されたノードでタグ付けされました。私が最終的に得たのは、リスト内のList[List[Node]]すべてList[Node]が特定の検索からの DFS ツリーであるということでした。

最長のチェーンを見つける:

前のステップですべてのグラフ トラバーサルの結果を取得し、すべてについて、List[Node]以前にノードにタグ付けした深さの値でリストを降順で並べ替えました。次に、リストの先頭 (これにより、DFS でアクセスされた最も深いノードが得られます) から始めて、ノードをバックトラックしてチェーンを構築します。これにより、リスト内のList[List[String]]すべてList[String]がその特定の DFS の最長のチェーンであることがわかりました。List[List[String]]それぞれのサイズで並べ替えてList[String]頭をつかむと、最大のチェーンが得られました。

結果：

私のアルゴリズムで見つかった最長のチェーンは、217 タイトルの長さでした。出力はここで見ることができます。

私はグーグルで他のいくつかの試みしか見つけることができませんでした.他のすべての試みは、私が達成できたものよりも長いチェーンを生み出したようです. たとえば、この投稿では、Eric Burke が 245 タイトルの長さのチェーンを見つけ、 Reddit の icefox という名前のユーザーが 312 タイトルの長さのチェーンを見つけたと述べています。

他の人がより長いチェーンを見つけたことを考えると、私のアルゴリズムがどこで最長のチェーンを見つけられなかったのか考えられません。ヘルプ/ガイダンスは大歓迎です。私のコードを確認したい場合は、ここで見つけることができます(これは Scala で書かれており、Scala の学習を始めたばかりなので、初歩的な間違いを犯した場合はご容赦ください)。

アップデート：

アルゴリズムにいくつかの変更を加えたところ、長さが 240 以上のチェーンが検出されるようになりました。こちらをご覧ください

R igraph を使用して、加重 DAG の最長パス計算を実装しました。

私の実装 (以下に示す) は、大きなグラフでは遅いです。高速化するためのヒントをいただければ幸いです。私の実装が最もよく知られている/典型的なアルゴリズムからどれだけ離れているかについての考えも大歓迎です.

ありがとう！

ここで、有向巡回グラフで最長の単純なパスを見つける方法 (パスが無限になるのを避けるために、各ノードが 1 回だけ訪問されるという単純な意味) を検索し、このようなソリューションに出くわしました。ただし、私が見つけたそのようなソリューションはすべて、そのパスに含まれる実際のノードではなく、最長パスの長さを計算する方法のみを示しています。

したがって、私の質問は、最長パスに含まれるノードを抽出するように、そのようなアルゴリズムをどのように変更できるでしょうか? Floyd-Warshall の全ペア最短パス アルゴリズムを変更して、パスの再構築を可能にする方法と同様です。

問題: 加重有向非巡回グラフ (DAG) とその中のソース頂点 s が与えられた場合、与えられたグラフ内の s から他のすべての頂点までの最長距離を見つけます。

参照グラフを見つけてください:リンク

なぜトポロジカルソートが必要なのですか? ソース頂点から変更された BFS を単純に使用できないでしょうか。なぜ私たちは線形順序付けをそれほど気にするのでしょうか。

これが繰り返しの場合は、親切に関連する回答にリダイレクトしてください。

ありがとう

I have an un-directed graph that weight of each edge is 1. The graph may have cycles. I need to find a longest path in the graph (each node appear once). The length of the path is number of nodes. Any simple/effective solution? Thanks!

わかりましたプログラマーとして、私たちは論理構築に関与するのが大好きですが、以下に述べるようなある種のパズルで空白になることがあります. これは宿題や仕事のようなものではなく、単にロジックとパフォーマンスの練習パズルであることを宣言させてください。

ここで重要なのは、単語の最後の文字が次の単語の最初の文字である必要があるなど、単語の最長チェーンの長さを調べて、可能な限り長いチェーンを作成し、最終的にそのチェーンの長さを計算することです。

今、私はある種の解決策を見つけようとしました

1. コンマstringで区切る
2. それらを追加しますlist
3. 並べ替えlist など

しかし、今、さらにロジックを開発する方法私はロジックの開発が少し苦手なので、助けていただければ幸いです.半分以上のロジックが本来あるべきように適切でない場合は、単語の最長チェーンの長さを取得するための単純な並べ替えと完璧な方法が必要です. .

要約
入力: String S= peas,sugar,rice,soup.
出力: 4 つの単語の長さ (エンドウ豆 -> 砂糖 -> 米 -> スープ) または (スープ -> エンドウ豆 -> 砂糖 -> 米) など

特定のルートリストに接続されている都市の最大数を見つける必要があるプログラムを解決しようとしています。

例：指定されたルートが[['1', '2'], ['2', '4'], ['1', '11'], ['4', '11']] 接続されている最大都市の場合、4 すでに訪れた都市を訪れることができないという制約があります。

どのように進歩するかなど、アイデアが必要です。

今のところ、私が考えているのは、都市をキーとして、その値として接続されている他の都市の数を含む辞書を作成できれば、解決策に近づくことができるということです (願っています)。例：私の辞書は{'1': ['2', '11'], '4': ['11'], '2': ['4']} 上記の入力用です。先に進むための支援と、何か不足している場合のガイダンスが必要です。