0

解決する必要のある問題がありますが、簡単でより重要な問題、つまり迅速な解決策は考えられません。これは、複数の巡回セールスマン問題の一部に少し似ています。

まず、X行とN列の行列があります。Nこれはアルゴリズムの静的変数であり、X変化する可能性があります。それが（ここで）のように見えると仮定しましょうN = 5：

matrix = [1 2 4 3 5; 4 3 1 2 5; 1 2 4 3 5; ]
matrix =
 1     2     4     3     5
 4     3     1     2     5
 1     2     4     3     5

すべての行は「ルート」と見なされ、1からN各ルート（=行）までのすべての一意の番号が含まれ、部分的なルートに分割されます。つまり、X行とM（M < N）列を含むブレークポイントマトリックスがあります。例えば：

breakpoints = [2 3 4; 1 2 4; 1 3 4]
breakpoints =
 2     3     4
 1     2     4
 1     3     4

の各行のインデックスは、ルートが部分的なルートに分割されるAFTERbreakpointsの対応する行の要素を示します。matrix明確にするために、最初の行を例として考えてみましょう。breakpoints(1, :) = 2 3 4つまり、ルートmatrix(1, :) = 1 2 4 3 5は部分的なルートに分割されます[1 2], [4], [3] and [5]。2番目の行には、2番目のルートを部分的なルートにbreakpoints(2, :) = 1 2 4分割するブレークポイントがあります。matrix(2, :) = 4 3 1 2 5[4], [3], [1 2] and [5]

今の私の目的は、からすべての行を削除することですがmatrix、部分的なルートは冗長な重複であり、順序が異なります。この例では、行2は行1の複製です。行3は、部分的なルートにつながる異なるブレークポイントがあるため、行1と同じルートであっても重複しません[1], [2 4], [3] and [5]。

どうすればこれをきれいにそして速く行うことができますか？行列には、X = 5e4行やN = 10、などの多くの要素を含めることができますM = 6。

4

1 に答える 1

1

定数M、Nの場合、これは、複合レコードを順番に並べ替えてから、隣接するエントリの同等性をテストすることにより、時間O（X log X）で解決できます。

「複合レコード」とは、行の機能とそのブレークポイントを1つのレコードに結合したレコードを意味します。この関数は、特定の行について、次の方法で取得されます。

  1. 行にブレークポイントを適用して、部分的なルートのリストを取得します。
  2. 各ルートの最初の要素で、部分的なルートを昇順で並べ替えます。 たとえば、{[4]、[3]、[1 2]、[5]}を{[1 2]、[3]、[4]、[5]}として並べ替えます。
  3. ソートされた部分ルートを連結して、新しい複合レコードを作成します。効果的なブレークポイント; インデックスからソース行へ。 たとえば、前の手順の行の例が行2 =（4 3 1 2 5）の場合、（1 2 3 4 5; 2 3 4; 2）を保存します。これは（ソートされた部分ルート、有効なブレークポイント、インデックス）です。

複合レコードを並べ替えた後、ソースインデックスまで、隣接するエントリの同等性を探してそれらを調べます。たとえば、（1 2 3 4 5; 2 3 4; 2）および（1 2 3 4 5; 2 3 4; 7）は、行7からの部分ルートが行2のルートと重複していることを示します。重複が見つかるたびに、対応する元の最初の行のエントリを無効なポイント番号、たとえばN+1に設定します。

したがって、O（X log X）のコストがかかるソート後、O（X）時間を使用して重複を検出します。次に、O（X）時間を使用して、元の行を調べ、無効な最初の要素を持つ行を削除して、重複を絞り出します。

わずかに正確な全体的なコストはO（（M + N）* X * log X）であり、これは理論上の最小O（（M + N）* X）をlogX係数だけ上回っています。複合レコードを並べ替える代わりにハッシュテーブルに格納し、重複するハッシュエントリが発生した場合にレコードを削除対象としてマークすると、ログX係数を取り除くことができます。

于 2011-12-11T13:28:37.900 に答える