3

2 文字の列でスクランブルされたテキストの段落があります。私の課題の目的は、それを解読することです。

|de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on|
|ry|  |is|th|is| b|eo|as|  |  |f |wh| o|ic| t|, |  |he|h |
|ab|  |la|pr|od|ge|ob| m|an|  |s |is|el|ti|ng|il|d |ua|c |
|he|  |ea|of|ho| m| t|et|ha|  | t|od|ds|e |ki| c|t |ng|br|
|wo|m,|to|yo|hi|ve|u | t|ob|  |pr|d |s |us| s|ul|le|ol|e |
| t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er|
|ry|d |un|Th|" |io|eo|n,|is|  |bl|f |pu|Co|ic| o|he|at|mm|
|hi|  |  |in|  |  | t|  |  |  |  |ye|  |ar|  |s |  |  |. |

列の正しい順序を見つけるための現在のアプローチは、単語の出現回数の基準に従って、各列の最適な位置を再帰的に見つけようとしています。

私が念頭に置いているアルゴリズムのコアの擬似コードは次のようになります。

function unscramble(scrambledMatrix,indexOfColumnIveJustMoved)
    for each column on scrambledMatrix as currentIndex=>currentColumn
       if (currentIndex!=indexOfColumnIveJustMoved)
           maxRepeatedWords=0;maxIndex=0;
           for (i=0;i<numberOfColumnsOfScrambledMatrix;i++)
              repWordsCount=countRepWords(moveFromToOn(currentIndex,i,scrambledMatrix))
              if (maxRepeatedWords<repWordsCount)
                  maxRepeatedWords=repWordsCount;
                  maxIndex=i;
              endif
           endfor
           if (maxIndex!=currentIndex)
               return unscramble(moveFromToOn(currentIndex,maxIndex,scrambledMatrix),maxIndex); //recursive call
           endif
       endif
    endfor
    return(scrambledMatrix); //returns the unscrambled matrix;
endfunction

各列を反復した後、移動する列がなくなると、アルゴリズムは停止します。文章が文字で形成された単語に基づいており、サンプルが十分に大きい限り、どの言語でも機能するはずです（ただし、英語のソリューションにのみ興味があります）。

他のアプローチや改善に関する提案はありますか? この問題の最善の解決策を知りたいです (おそらく、代わりに一般的な単語の出現を探す辞書ベースのものですか? 再帰を避けるためにアルゴリズムを再構築するのはどうですか? はるかに高速でしょうか?)。

4

1 に答える 1

1

さらにいくつかのアイデア：

  • 引用符、各開始引用符の後に終了引用符が必要です。
  • 大文字、通常は文頭または名詞など (適用される追加の文法規則
  • すべてをメモリに収めるのに十分な小さな辞書を使用し、特定の配置で有効な単語の数を数えます。

一般に、このアプローチは最も時間がかかりますが、1 つの方法は、遺伝的アルゴリズムを使用することです。

列の現在のデフォルトの配置が

|de|  | f|Cl|nf|ed|au| i|ti|  |ma|ha|or|nn|ou| S|on|nd|on|
[0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18] <--- define this to be a chromosome

ランダムに割り当てられた染色体から始まる 100, 1000 の集団を作成できます (「ランダムな」割り当ては重複した番号を持つことができず、有効でなければならないことに注意してください)

次に、課題ごとにフィットネス関数を実行するか、複数のフィットネス関数をそのように分割したい場合は実行します。各課題にフィットネス値を割り当てる 1 つのスーパー フィットネス関数から始めます。

染色体の上位 50% のみを取得し、それらを次の世代に移動します。そこでは、クロスオーバー関数の選択と突然変異の確率に基づいて「子」染色体を作成します。このタイプの問題には、非常に軽いクロスオーバー関数をお勧めします (またはなし...）とまともな突然変異率。単語/フィットネス関数にあまり貢献していない列を見つけることができれば、それらをひっくり返すことができます。

これを何世代にもわたって繰り返し、最高評価の割り当てが各世代のように見えることを確認してください。ある時点で有効性が横ばいになることが予想され、それが正しい割り当てになります。

このアプローチは、フィットネス関数を使用したブルート フォースよりもわずかに優れているだけですが、かなり優れていることも判明する可能性があります。

最後のアイデア: 「最初の列、2 番目の列」から抽象化し、単語を形成するチャンクに列を割り当ててみてください。[1,4,6....] が「彼」を形成することが判明したからです。 「彼女」などは、最初から属しているという意味ではありません。

私には別のアプローチがありますが、これには動的アルゴリズムの方が適していると思います。

編集：別のアプローチ

再び辞書のアプローチに基づいていますが、残りの前に最初の数列を選択することに集中します。それがバラバラになり、特定の行に単語が表示されない場合は、以前の選択が間違っていたことを意味し、バックトラックする必要があります.

行 1 を選択します。ここには単語があまり多くない可能性がありますが、辞書のサブセット (最初の列の文字で始まる単語を含むサブセット) に絞り込むことができます。

機能する行ができたので、右側に隣接する行を選択します。完全な単語を形成するか、有効な単語が可能な場合 (単語の終わりを示すスペースが存在しない場合)。繰り返す。

以前の選択で隣接する行が不可能な場合は、1 行左に戻り、同じものを再度選択しないでください。

ここでの弱点は、単語のすべてのバリアントだけでなく、文内のすべての単語を辞書に含める必要があることです。「単語の 90% が一致するため、これはまだ有効な試みです...」またはその種の何かを示すフィットネス関数に似たヒューリスティックを考え出す必要があるかもしれません。

于 2012-02-22T23:30:08.343 に答える