- 記入中
- 参照元
- 答え
最長増加部分列(LIS)
数のリストから、順序を保ったまま、どれも前の数より大きくなるように選ぶと、いくつ選べるでしょうか? その答えが最長増加部分列です。リストを入力して、動的計画法が各位置について、そこで終わる最長の並びを求める様子を見てみましょう。 「再生」で表が埋まっていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。数の列を入力してください。表には各位置について、そこで終わる最長の増加する値の並びの長さと、その並びが続いている前の位置が記録されます。決して減らない並びを求めるには「等しい値を許可」にチェックを入れます。最後に、並びを最後の値からさかのぼって読み取ります。「新しい例」で別の列を作ります。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- 数の列をカンマかスペースで区切って入力します。決して減らない並びを求めるには「等しい値を許可」にチェックを入れます。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
- 各位置が前のすべての位置と比較される様子を見て、最後に最長の並びがオレンジ色でさかのぼって読み取られるのを確認します。
表のしくみ
表には3つの行があります。値、各位置で終わる最長増加部分列の長さ、そしてその部分列が続いている位置です。値1つだけでも長さ 1 の並びです。次に前の位置をすべて調べます。その値の方が小さければ、そこで終わる並びをこの値で延ばせるので、長さはその並びより1つ長くなります。そのような延長のうち最長のものが選ばれ、その位置が3行目に入ります。
並びのさかのぼり
最長増加部分列は、長さが最大の位置で終わります。そこから、3行目はその前にどの位置が来るかを示し、その位置の3行目はさらにその前にどの位置が来るかを示します。これを、前に何もない位置にたどり着くまで続けます。それらの値を順に読むと答えになります。「等しい値を許可」にチェックを入れると、値は等しい値の後にも続けられるので、決して減らない最長の並びが得られます。
よくある質問
部分列と部分配列の違いは何ですか?
部分配列は隣り合う値のまとまりです。部分列は順序を保ちますが値を飛ばしてもよいので、3, 10, 2, 1, 20 では、間に 2 と 1 があっても、3, 10 と 20 は増加部分列になります。
LIS アルゴリズムはどのくらい速いですか?
表を使う方法は、位置のすべての組を比較します。n 個の値なら n·(n − 1)/2 回の比較です。ペイシェンスソートは O(n log n) でできます。各長さについて、その長さの並びを終える最小の値を保持し、新しい値をそれぞれ二分探索で置いていきます。
最長増加部分列は一つに決まりますか?
いつもではありません。1, 3, 2, 4 では、1, 3, 4 と 1, 2, 4 のどちらも長さ 3 です。表は長さを求め、さかのぼりでそのうちの1つが見つかります。
最長増加部分列はどこで使われますか?
ファイルやゲノムの比較に使われます。一部の手法では、まず一致する行を見つけ、次にそれらの位置の増加部分列を取ります。スケジューリングや箱を積み重ねるパズルにも使われます。数学では、ランダムにシャッフルしたリストの LIS の長さが有名な研究対象です。
データはどこかに送信されますか?
いいえ。すべての計算はお使いのブラウザー内で行われ、最後の設定はこのブラウザーのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ