問題タブ [longest-path]

N個のノード（各ノードの最大次数は3）から1つのエッジを削除して、結果として得られる2つのツリーがN / 2にできるだけ近くなるように、ツリーを分割するアルゴリズムを探しています。 。「最も中心にある」エッジを見つけるにはどうすればよいですか？

ツリーは、アルゴリズムの前の段階からの入力として提供され、グラフとして入力されます。したがって、バランスが取れておらず、どのノードがルートであるかが明確ではありません。

私の考えは、ツリー内で最長のパスを見つけてから、最長のパスの中央にあるエッジを選択することです。それは機能しますか？

最適には、どちらのツリーにも2N/3ノードを超えないようにすることができるソリューションを探しています。

回答ありがとうございます。

これは[CLRSから]の質問です：

最適化問題LONGEST-PATH-LENGTHを、無向グラフと2つの頂点の各インスタンスを、2つの頂点間の最長の単純なパスのエッジの数に関連付ける関係として定義します。決定問題を定義するLONGEST-PATH={：G =（V、E）は無向グラフ、u、vはVに含まれ、k> = 0は整数であり、Gにはuからvへの単純なパスが存在します。少なくともk個のエッジの}。LONGEST-PATHがPに含まれている場合にのみ、最適化問題LONGEST-PATH-LENGTHを多項式時間で解くことができることを示します。

私の解決策：ポリタイムでG（u、v）を解くことができるアルゴリズムAが与えられたので、「YES」とk'が返され、k'がG（u、v）、今やらなければならないことは、

その場合、最長のパス長が解決されます。「NO」またはk>=k'を受け取った場合、解決策はありません。

したがって、比較のためにA +定数を実行するためのポリタイム、次にポリタイムを要する最長のパス長を見つけるために。また、これは、G（u、v）がポリタイム（P）で実行されるためにのみ可能です。したがって、G（u、v、k）はポリタイム（P）でも実行されるため、最長パスを最長パスに減らすことができます。長さの場合、最長パス長はP単位です。

反対の方法でそれを解くことができます。私たちが行うことは、k'= 0からnに対してG（u、v、k'）を実行し、k == k'であるかどうかをチェックするたびに、それを解きました。このための実行時分析：n * polytime + n *（定数比較）= polytime

私の答えが妥当かどうか誰かに教えてもらえますか？そうでない場合は、どこが間違っているのか教えてください

また、アルゴリズムを研究する方法、およびアルゴリズムの質問（またはグラフの質問）を解決するためにどのようなアプローチを取るべきかについて、いくつかアドバイスをいただけますか？

どうぞよろしくお願いします

国のリストがあり、選択した各国が前の要素を終了したのと同じ文字で始まる必要がある国の最長パスが必要です

私はこの方法を試しましたが、うまくいきません

なにか提案を？

ノード0（最小ノード）から始まるDAGの最長パスを取得する方法を知りたい

wiki を検索したところ、次のアルゴリズムが得られました。

しかし、私はそれを実装する方法がわかりません。もちろん、私が書いた次のコードは機能しません:(トポはトポロジカルにソートされたノードです)

どうすればいいですか？ありがとう！

また、0 から n-1 までの異なるパスの数を計算するアルゴリズムを教えてください。

非巡回グラフで、長さ L のパスが 2 つのノード間に存在するかどうかを調べようとしています。私の質問は、この場合に使用するのに最適で最も単純なアルゴリズムは何かということです。

グラフには最大 50 個のノードと 100 個のエッジがあることに注意してください。

DFS を使用してすべてのパスを検索し、そのパスが 2 つのノード間に存在するかどうかを確認しようとしましたが、オンライン ジャッジから「Time Limit Exceeded」という回答が得られました。

均一コスト検索アルゴリズムも使用しましたが、否定的な応答もありました。

このような問題を解決するためのより効率的な方法が必要です。ありがとうございました。

私は現在、画像内のカラーブロブの「方向」を決定する必要があるコンピュータビジョンプログラムに取り組んでいます。カラーブロブは一般に楕円形に従うため、時間の経過とともに方向を追跡するために使用できます（最初に定義された/決定された方向に関して）。

方向の変化を計算するための手段は次のとおりです。

1. 可能な方向（360度）をN方向に量子化します（45度の角度増分の場合は8になる可能性があります）。
2. カラーブロブの初期状態（t0）を表す保存された行列が与えられた場合、ブロブの現在の状態（tn）を表す行列も取得します。
3. これらのN方向を反復処理し、その指定された方向のカラー値の最長ストレッチを検索します。（たとえば、楕円が45度回転し、0が垂直である場合、最長の長さは45度のマーク/または225度に起因する必要があります）。

コンセプト自体は複雑ではありませんが、次の問題が発生しています。

• 画像内の任意の角度での値の最長ストレッチを計算します。これは、0、45、90などの角度では単純ですが、中間の角度ではより困難です。角度を「量子化」することは、私には思ったほど簡単ではありません。

0と90などの角度を区別する際の潜在的な問題について心配する必要はありません。慣性を使用して、カラーブロブの最も可能性の高い方向を決定できます（つまり、過去の方向の状態に基づいて）。

私の主な関心事は、マトリックス内の「最長ストレッチ」を特定することです。

ご協力ありがとうございました！

私はOGDFライブラリを初めて使用し、非巡回有向グラフで最長のパスを見つける必要があります（OGDF組み込み関数を使用したい）。エッジに負の重みを持つ最短経路アルゴリズムを使用して最長経路を見つけることは可能ですが、適切な関数を見つけることもできませんでした。OGDFにはそれを行うための特定の機能がありますか？はいの場合、どうすれば使用できますか？

会社の組織図を作成するプログラムに取り組んでいます。私は頂点を階層化するための最長パスアルゴリズムについて読んでいますが、1つのことが私を悩ませています。私が行った読みは、グラフを下から上に階層化する必要があることを示唆しています。最初に、子のないノードを最下層に配置してから、上に向かっていきます。ただし、最長パスアルゴリズムでは、底が非常に広いグラフが作成されることも読みました。

親のいないノードから始めて、上から下に向かってグラフを作成してみようと思っていました。たぶんこれは一般的で、私はそれが使われているのを見たことがありませんが、私が見ない理由がこのアプローチを非現実的にしているのではないかと心配しています。足りないものはありますか？

私はこの問題を概念化してから、そのためのJavaコードを作成しようとしています。ここでいくつかの議論があったことは知っていますが、回答者があまりいないので、私の考えを書き留めて質問を繰り返したいと思います。皆さんからのフィードバックを期待しています。ありがとう！

私の考え：各リーフノードについてルートノードからそのノードまでの最長パスを見つけるすべてのパスについて最大パス長を見つける

しかし、これは単なるブルートフォースではありませんか？これに対するよりエレガントな解決策はありますか？

負の重みでダイクストラのアルゴリズムを使用していると聞きましたが、一部の場所では、これは特定のケースでのみ機能すると言われていますか？ベルマンフォードアルゴリズムの提案も見ましたが、それは最短経路を見つけるために使用されていませんか？

ありがとう！！

最近、プログラミングの質問に出くわしました。

ツリーが与えられた場合、非バイナリにすることも、N個のノードを持つ単一のチェーン（または線形）にすることもできます。

入力は、a1、a2....akで示されるKノードのセットになります。それらのKノードの1つから始まり、それらのKノードの1つ（開始ノードとは異なる）で終わる最長の単純なパスを見つけたいと思います。NまたはKに依存する対数アルゴリズムは、必要に応じて実行時間の要件（KlogK、KlogNなど）を満たす必要があります。これは、希望する制限時間内である必要があります。

ありがとうございました