2

Jacobson と Vo による論文「重い増加/一般的な部分列の問題」で、完全な最長増加部分列 (lis) の計算のためのノード構造を理解するのに問題があります。

論文の疑似コードは次のとおりです。

アルゴリズム[1]

とはどういう意味ですか

node は補助配列で、L の各要素について、昇順のサブシーケンスでこの要素の前にある要素のレコードを含みます。関数 newnode() は、そのようなレコードを構築し、それらを有向グラフにリンクします。アルゴリズムの最後に、L の最大要素から検索して、シグマの LIS を復元できます。

? この構造をどのように実装しますか?

シーケンスのすべての要素を頂点 (および nil-vertex) とエッジ "\sigma_i -> s" として有向グラフを作成し、L の最大要素 (および終了) で始まる最長パスを検索する必要がありますか?ゼロで）？完全なリスを取得するためのより効果的な方法はありませんか?

2 番目の質問: このアルゴリズムは、ウィキペディアで説明されているアルゴリズムと同じくらい高速ですか? そうでない場合: ウィキペディアのアルゴリズムを変更して、論文に記載されているように最も重い一般的なサブシーケンスを計算できますか?

4

1 に答える 1