最長経路問題は、一般的なグラフでは NP 困難であることを知っています。しかし、私は特定の種類のグラフを検討しています。これは、1 つのサイクルと、サイクルの各頂点に追加された 1 つのエッジ インシデントで構成されています。たとえば、長さ 7 のサイクルの場合、グラフは次のようになります。
すべてのエッジに重みが付けられます (重みは実数であり、正または負にすることができます)。パスのサイズがパス上のエッジの重みの合計である、このグラフで最大の単純なパスを見つけたいと思います。
アルゴリズムは、サイクルのサイズにおいて線形である必要があります。しかし、どんなアイデアでも大歓迎です。
最長パスは、ほぼ確実に外側の 2 つの頂点の間です。また、ほぼ確実に、サイクル内のすべての頂点をカバーする必要があります。
したがって、DFS を使用して、O(N) のサイクルをマップします。次に、現在のサイクル配置の長さを計算します。その長さに、サイクルの最初のポイントから外側までの距離と、最後のポイントから外側までの距離を追加します。これにより、サイクルの長さとは別に保存する実際のパスの長さが得られます。
最初のポイントと最後のポイントのインデックスを増やし (O(1) で実行できます)、最初のポイントから最後のポイントに向かうエッジの長さを削除します。次に、外側の長さを再度追加します。すべての頂点をカバーするまで繰り返します。パスの長さを実際に毎回再計算するのではなく、保存して更新するため ((O(N^2)) が必要になるため、O(N) で実行できます。
これにより、O(N) でサイクルをたどることができます。ただし、正確なアルゴリズムではありません。そのためには、代わりに一部の i,j に対して first+i や last-j を使用してはならないことを確認する必要があります。それを完全にチェックするには、本質的にO(N^2)が必要です。
ただし、これらのエッジケースが可能な場所を巧みに判断することにより、約 O(N log N) でそれを実行しようとしている可能性があります。正確な線形アルゴリズムが可能であるとは思えません。
サイクル上のリンクを選択します。最長パスはそのリンクを通過するか通過しないかのどちらかなので、どちらの場合でも最良の答えを見つけ出し、それらの中で最良のものを選択しましょう.
最長パスがサイクル リンクを通過しない場合は、リンクを削除してツリーを生成します。葉から、各ノードで、そのノードの下の最長パスと、そのノードから任意の子孫への最長パスが計算されます。各ノードで、その子の答えを見て答えを導き出すことができます。ルートの答えは、最長のパスを提供します。
最長パスが選択したリンクを通過する場合、リンクの一方の端から時計回りに進む部分と、リンクのもう一方の端から反時計回りに進む部分で構成されている必要があります。これら 2 つの長さの合計は、サイクルを構成するリンクの数に 1 を加えたものを超えません。i = 1 の場合、リンクの両側から時計回りと反時計回りのパスのコストを制限し、実行中の最大値を維持します。リンクを通過する最長パスの長さは、k リンクまでの時計回りの最長パスと、最大 Nk リンクまでの反時計回りの最長パスの合計 (いくつかの k について) になります (おそらく同様のコストのいくつかのいじりを伴う - ve リンク コストが存在します)。したがって、選択したリンクを通過する最長パスをコストも O(n) で見つけることができます。
それぞれのコスト O(n) の 2 つのケースを計算し、最適なものを選択すると、総コスト O(n) が得られます