3

4 桁の数字 1234 を考えると、6 つの可能な 2 桁のサブシーケンス (12、13、14、23、24、34) があります。いくつかのサブシーケンスが与えられた場合、元の数を回復することは可能ですか?

ここにいくつかの例のデータがあります。各行には、異なる 6 桁の数字の 3 桁のサブシーケンスがいくつかリストされています (検索対象)。

528, 508, 028, 502, 058, 528, 028, 528, 552, 050
163, 635, 635, 130, 163, 633, 130, 330, 635, 135
445, 444, 444, 444, 454, 444, 445, 
011, 350, 601, 651, 601, 511, 511, 360, 601, 351
102, 021, 102, 221, 102, 100, 002, 021, 021, 121
332, 111, 313, 311, 132, 113, 132, 111, 112
362, 650, 230, 172, 120, 165, 372, 202, 702
103, 038, 138, 150, 110, 518, 510, 538, 108
343, 231, 431, 341, 203, 203, 401, 303, 031, 233

編集: 解決策が一意でない場合があります (複数の数値がサブシーケンスを与えている可能性があります)。その場合、それらの 1 つまたはリストを返すとよいでしょう。

4

3 に答える 3

3

あなたがしたいことは、すべてのサブシーケンスの最短共通スーパーシーケンスを見つけることです。元の番号を含むすべてのサブシーケンスがある場合は、明らかに、SCS が探しているものになります。それ以外の場合は保証できませんが、可能性は十分にあります。

残念ながら、この問題に対する適切な多項式アルゴリズムはありませんが、Google で検索すると、多くの近似アルゴリズムが利用可能であることがわかります。たとえば、Shortest Common Supersequene Problem の ACO アルゴリズムでは、 3 つの全体的なアプローチについて言及されています。

  1. 動的プログラミングまたは分岐結合。これらは、非常に少数の文字列または小さなアルファベットを除いて、通常は遅くなります。

  2. 動的計画法を使用してペアごとに文字列の SCS を見つけ、ヒューリスティックを使用して「マージ」する文字列を選択します。

  3. あなたの場合に最も良いかもしれないマジョリティマージヒューリスティック。

  4. 論文で説明されているアプローチ。

この問題に関する別の素晴らしい記事があります: http://www.update.uu.se/~shikaree/Westling/

于 2013-08-13T14:04:49.550 に答える
2

ロジック プログラミングに任せましょう。

これはclojureの経由です。

サブシーケンスであるとはどういう意味かを定義する

(defne subseqo [s1 s2] 
  ([(h . t1) (h . t2)] (subseqo t1 t2)) 
  ([(h1 . t1) (h2 . t2)] (!= h1 h2) (subseqo s1 t2)) 
  ([() _]))

ソルバーを介して制約を実行します。

(defn recover6 [input-string] 
  (run* [q] 
    (fresh [a b c d e f] 
      (== q [a b c d e f]) 
      (everyg (fn [s] (subseqo (seq s) q)) 
              (re-seq #"\d+" input-string)))))

例 (結果は REPL で知覚的に瞬間的です):

(recover6 "528, 508, 028, 502, 058, 528, 028, 528, 552, 050")
;=> ([\5 \0 \5 \2 \8 \0]
     [\5 \0 \5 \2 \0 \8]
     [\5 \0 \5 \0 \2 \8]
     [\0 \5 \0 \5 \2 \8]
     [\0 \5 \5 \0 \2 \8])

(recover6 "163, 635, 635, 130, 163, 633, 130, 330, 635, 135")
;=> ([\1 \6 \3 \5 \3 \0] 
     [\1 \6 \3 \3 \5 \0] 
     [\1 \6 \3 \3 \0 \5])

(recover6 "445, 444, 444, 444, 454, 444, 445")
;=> ([\4 \4 \5 \4 _0 _1] 
     ... and many more

最後の例では、下線は_0と_1が自由変数であることを示しています。それらは制約されていません。自由変数を数字のセットに制約するのは簡単です。

于 2013-08-13T18:11:29.497 に答える