4

文字が繰り返されないさまざまな量のセットでサブシーケンスを見つけることについて質問しました。解決策は、文字の各ペアの行列を作成し、各セットで発生しないものを破棄してから、有向非巡回グラフで最長パスを見つけることでした。ただし、最長パスだけが必要なわけではなく、いくつかの最長パスが必要です (たとえば、長さが 10、10、9、8、8、3、3、2、および 1 のサブシーケンスを生成する場合、最初の 5 つのサブシーケンスのみを表示します)。

したがって、最長パスだけを探しているわけではないため、ウィキペディアの記事で説明されている最長パス アルゴリズムを使用するのではなく、結果のサブシーケンスを生成するために、単純にすべてのリストを生成する単純なアルゴリズムを使用しています。可能なサブシーケンス。これにより、前の質問に対する回答の結果と同様のセットが生成されます。

問題は、生成されるサブシーケンスの量を減らしたいということです。

たとえば、次のセットがあるとします。

A = AB12034
B = BA01234
C = AB01234

...私のアルゴリズムは現在、各セットで発生する次のペアを考え出します:

A - 1     B - 1     1 - 2     2 - 3     0 - 3     3 - 4
    2         2         3         4         4
    3         3         4
    4         4
    0         0

これは技術的には正しいですが、これらのペアのいくつかを削除したいと思います。たとえば、2常に の後に来ることに注意して1ください。A2したがって、 andのB2ペアを削除したいと思います (つまりA、andBに直接ジャンプするべきではありません2...常に最初に通過する必要があります1)。また、は常にその直後に発生するため、1以外の番号に決してジャンプしないでください。さらに、との間で常に発生することに注意してください。そのため、ペアを削除したいと思います(ここでも、にジャンプする前に常に通過する必要があります。これは、すべてのセットがこれらの 3 文字の位置を : として持っているためです)。220B3B3B03B < 0 < 3

明確にするために、現在のアルゴリズムは次のサブシーケンスを考え出します: (A簡潔にするために で始まるものだけを含めました):

A1234
A124  *
A134  *
A14   *
A234  *
A24   *
A34   *
A4    *
A034
A04   *

...そして、 でマークされたものはすべて*排除する必要があります。

目的のサブシーケンスを生成する (正しい) ペアは次のようになります。

A - 1     B - 1     1 - 2     2 - 3     0 - 3     3 - 4
    0         0

...そして、サブシーケンスの完全なリストは次のようになります:

A1234
A034
B1234
B034
1234
234
034
34

言い換えれば、私はこの有向非巡回グラフから行こうとしています:

ここに画像の説明を入力

これに：

ここに画像の説明を入力

これらの不要なペア (つまり、グラフのエッジ) を取り除くには、どのようなアルゴリズム/ロジックを使用すればよいですか? それとも、そもそもペアを生成する私のロジックを変更する必要があると思いますか?

4

3 に答える 3

2

さらに、B と 3 の間で常に 0 が発生することに注意してください。そのため、B3 のペアを削除したいと思います (繰り返しますが、B は 3 にジャンプする前に常に 0 を通過する必要があります。すべてのセットには、これらの 3 文字の位置があるため: B < 0 < 3)。

うーん、n0 < n1 < n2すべてのセットを保持する場合は、すべての(n0, n2)ペアを削除しますか? これはこれで達成できます（pseudoPythonで）：

for(edge in node):
    if(len(LongestPath(node, edge.Node)) > 1):
        RemovePair(node, edge.Node)
于 2012-01-01T04:53:51.067 に答える
1

簡単は簡単です。グラフが大きすぎなければ、おそらく十分に効率的です。

  • 各ノード (着信エッジのないノードから開始) について、すべてのパスをたどり、距離をマークし、すべての直接の子に 1 のマークを付けて、それらをキューに入れます。キューが空でない間、ノードを引き出します。最初からの距離を考えてnみましょう。d直接のすべての子を調べ、1 のマークが付いているものがある場合は、最初からその辺までのエッジを削除し、すべての子nを distance でマークされたキューに入れますd+1。キューから次のノードを引き出します。

JSPerfUnkn0wn が言ったことを、もう少し詳しく説明します。

于 2012-01-01T04:59:02.387 に答える
0

グラフは非循環であるため、考えられる解決策は、好みの最短経路アルゴリズム (Bellman-frod、Floyd-Warshal など) を適用することですが、比較条件を反転させます (長い経路が短い経路よりも優先されるようにするため)。

于 2012-01-01T04:59:09.780 に答える