私はシンプルで方向性のないツリーを持っていますT。名前の付いたパスとその名前Aの別のパスを見つける必要があり、共通の頂点はありません。説得力は、 を最大化することです。BABLen(A)*Len(B)
この問題は分割問題に似ていると思いましたが、分割問題ではセットがありますが、ここでは等価セットがあります。解決策は、交差していない 2 つのパスを見つけることLen(A) ~ Len(B) ~ [n-1/2]です。これは正しいですか？そのようなアルゴリズムを実装するにはどうすればよいですか?
パスの長さがパス内のリンクの数だけである場合（リンクに重みがない場合）、ほぼ扱いやすい動的プログラミングソリューションがあると思います。
葉から作業します。各ノードで、そのノードにルートを持つサブツリーに限定されたソリューションの最良のペアを追跡する必要があります。また、kごとに、そのノードで終了する長さkのパスと最大長の2番目のパスを持つ最良のソリューションを追跡する必要があります。そのノードの下のどこかで、パスに触れていません。
ノードのすべての子孫についてこの情報が与えられると、そのノードについて同様の情報を生成できるため、ルートまで進みます。
実際には単なるノードの行であるツリーを検討する場合、この量の情報が必要であることがわかります。ノードのラインの最良の解決策は、それを2つに分割することです。したがって、ラインの長さが2n + 1の場合にのみ最良のソリューションを考え出した場合、長さ2nのラインに必要なビルディングブロックはありません。 +3。
初めに。この問題を間違った方法で見ていると思います。私が理解しているように、グラフ関連の問題があります。あなたがすることは
- 最大全域木を構築し、長さ L を求めます。
- ここで、2 つのパスが共通の頂点を持つことはできないと言うので、これを実現するにはエッジを削除する必要があります。グラフのすべてのエッジの重みは 1 であると仮定します。したがって、エッジを削除した後、2 つのパス A と B の合計は L-1 になります。問題は、len(a) と len(b) の積が最大になるようにエッジを削除する必要があることです。これは、L の et most 'middel' のエッジを削除することによって行います。問題は、周囲が固定された長方形の面積を最適化するのと同じです。この件に関する短い YouTube ビデオは、こちらでご覧いただけます。
エッジの重みが 1 に等しくない場合は、複数の最大スパニング ツリーが存在する可能性があるため、より困難な問題が発生することに注意してください。しかし、それらをさまざまな方法で分割できる場合があります。その場合は、返信してください。解決策を考えますが、手元にありません。
幸運を祈ります。