3

このステートメントは、「アルゴリズムへのヒッチハイク ガイド」で読みました。しかし、LIS の問題では数列しかないので、視覚化することはできません。グラフの問題としてどのように調整できますか?

4

2 に答える 2

7

2D グリッドの問題を想像してください。あなたは左下の四角にいて、右上の四角にたどり着く必要があります。このスキームから非環式 DAG を想像できますか?

ここで、いくつかの正方形が禁止されていると想像してください。正方形を禁止すると、「ロック」につながる可能性があり (閉じ込められていることに気付く場合があります)、どのパスをたどるかを選択することが実際に重要です。グラフに関して言えば、正方形を禁止することは頂点を削除することと考えることができ、目標はルートから 1 つの特定のノード (シンク) に移動することです。

では、LIS に戻りましょう。LIS を解くとき、実際に行う必要があるのは、どの数字を選択し、どれを選択しないかを決定することです。制限は、1 つの数字を選ぶときはいつでも、この数字よりも小さい数字を選ぶことはできないということです (順番に数字を選びます)。

これで、両方を混在させることができます。数列からグラフを作成すると想像してください。

  • すべての番号がノードになります。
  • 数値ノード A は数値ノード B に対してエッジを持っています。
    • B はシーケンス内で A の後に来る
    • B の値は A より大きい
  • 特別なノードエンドがあります
  • すべてのノードには端から端まであります

このグラフのすべてのパスは、有効な増加サブシーケンスです。LIS を見つける問題は、このグラフで最長のパスを見つける問題になりました。

于 2012-10-16T03:46:59.637 に答える
3

数値の配列がある場合、たとえば 1、5、4、8 とします。次のような DAG を構築できます。

  • 各数値を頂点として追加します。
  • 番号頂点ごとに、重み 1 の出力エッジをそれ以降のすべての大きい番号に追加します。
  • 重み 0 の出力エッジを持つノード S をすべての番号の頂点に追加します。
  • すべての数値頂点からの重み 0 の着信エッジを持つノード E を追加します。

したがって、最長増加部分列問題は、S から E への最長経路問題に変わります。

LICとDAG

于 2013-07-16T15:43:08.917 に答える