11

すべての行が単語を形成し（左から右）、すべての列が単語を形成する（上から下）ように、可能な限り最大の文字の長方形を見つけるプログラムを作成します。

この興味深い質問を見つけました。宿題ではありませんが、そのように聞こえるかもしれません。（私は学校にいません）。私は楽しみのためにこれをやっています。

例

cat、car、ape、api、rep、tipから、次の長方形（正方形）が得られます。

c a r
a p e
t i p

私の最初のアイデアは、特定の文字列で始まるすべての単語を取得できるように、ある種のプレフィックスツリーを構築することです。これは、すでに2つ以上の単語（上から下または左から右のいずれかを読んでいる）があり、追加する次の単語を見つける必要がある場合に役立ちます。

他のアイデアはありますか？

編集

これは直方体（3D長方形）で行うことができますか？

対角線上に有効な単語が必要な場合はどうなりますか（アイデアクレジット：user645466）。そのためのアルゴはどのように最適化されますか？

4

3 に答える 3

12

Dを辞書とします。mとnを修正します。m×nの長方形を見つける問題を制約充足問題（CSP）として定式化できます。

x i、1 … xi、 n∈D∀i∈ {1、…、m}
x 1、j …x m、 j∈D∀j∈{1、…、n}
x i、 j∈ {A、 …、z}∀i∈{1、…、m}、∀j∈{1、…、n}

CSPを解決するための非常に一般的なアプローチは、バックトラッキングと制約伝播を組み合わせることです。大まかに言えば、バックトラッキングとは、変数を選択してその値を推測し、1つ少ない変数でサブ問題を再帰的に解決することを意味し、制約伝播とは、各変数の可能性の数を減らすことを意味します（おそらくゼロに、つまり解決策がないことを意味します）。

例として、x 1,1 =を選択して、3×3グリッドを開始できQます。

Q??
???
???

英語の辞書では、x1,2とx2,1の唯一の可能性は（スクラブルのU「単語」の前に）あります。

CSPを解決する技術は、バックトラッキングと制約の伝播の間でバランスを取ることです。制約をまったく伝播しない場合は、力ずくで使用しているだけです。制約を完全に伝播する場合、バックトラックする必要はありませんが、NP困難な問題をそれ自体で解決する伝播アルゴリズムは、実行するのにかなり費用がかかる可能性があります。

この問題では、適切なデータ構造のサポートがない限り、各バックトラッキングノードで大きな辞書を操作するとコストがかかります。トライまたはDAWGをすばやく使用して、接頭辞が完全な単語に拡張される文字のセットを計算するアプローチの概要を説明します。

各バックトラッキングノードで、割り当てた変数のセットはヤング図形です。つまり、その上と左の変数が割り当てられるまで、変数は割り当てられません。次の図で、.は割り当てられた変数を示し、*は?割り当てられていない変数を示します。

.....*
...*??
...*??
..*???
*?????

マークされた変数は*、次に値が割り当てられる候補です。毎回固定変数を選択するのではなく、複数の選択肢があることの利点は、一部の変数の順序が他の変数よりもはるかに優れている可能性があることです。

それぞれについて*、trie / DAWGを2回ルックアップします。1つは水平方向、もう1つは垂直方向で、次に来る可能性のある文字のセットの共通部分を計算します。古典的な戦略の1つは、矛盾に早く到達することを期待して、可能性が最も少ない変数を選択することです。この戦略が好きなのは、可能性がゼロの変数があると自然に剪定され、可能性が1つの変数があると自然に伝播するからです。結果をキャッシュすることで、各ノードの評価を非常に高速にすることができます。

于 2011-12-15T04:22:12.413 に答える
1

指定された長さの単語の辞書を指定して、2つの新しい辞書を作成します。1つ目は単語のすべての1文字のプレフィックス（指定された長さの単語の最初の文字になる可能性のあるすべての文字）を含み、2つ目はすべての2文字のプレフィックスを含みます単語の（指定された長さの単語の最初の2文字になることができる2文字のすべてのシーケンス）。トリプルプレフィックスも実行できますが、おそらくそれを超える必要はありません。

  1. 辞書から単語を選択し、それを呼び出しますX。これがマトリックスの最初の行になります。

  2. X[1], X[2], ..., X[N]作成した便利なリストを使用して、すべて有効な1文字のプレフィックスであることを確認してください。そうである場合は、ステップ3に進みます。それ以外の場合は、手順1に戻ります。

  3. 辞書から単語を選択し、それを呼び出しますY。これは、マトリックスの2番目の行になります。

  4. X[1] Y[1]作成した便利なリストを使用して、、、X[2] Y[2]...X[N] Y[N]がすべて有効な2文字のプレフィックスであることを確認してください。そうである場合は、ステップ5に進みます。それ以外の場合は、手順3に戻ります。これが辞書の最後の単語である場合は、手順1に戻ります。

    ..。

    2（N-1）。辞書から単語を選択し、それを呼び出しますZ。これは、行列のN番目の行になります。

    2N。X[1] Y[1] ... Z[1]、、X[2] Y[2] ... Z[2]...X[N] Y[N] ... Z[N]がすべて辞書内の単語であることを確認してください。もしそうなら、おめでとう、あなたはそれをしました！それ以外の場合は、手順2（N-1）に戻ります。これが辞書の最後の単語である場合は、手順2（n-3）に戻ります。

論理は、一度に1行ずつ単語の長方形を作成し、行の単語を選択してから、列が単語に完成できることを確認することです。これは、一度に1文字を追加するよりもはるかに速く進行します。

于 2011-12-14T23:26:13.740 に答える
1

同じ長さの単語のBag[]= indexを作成してから、試行の配列を作成します。各長さのwordListに対して1つの試行を作成します。

   Rectangle makeRectangle(length, height, rectangle)
    {
        if ( length == rectangle.length()) check if complete and return;
        checkIfPartialComplete - check columns for valid prefixes
        for ( i from 1 to grouplist[i-1])
        {
            newRectangle = append word[i] to rectangle 
            return makeRectangle(l,h, rectangle with appended word) if not equal to null
        }
    }


boolean checkPartial(int l, Trie trie)
{
    for ( int i =0 ; i < l; i++)
    {
        String col = getColumn(i);
        if (!trie.contains(col))
        {
            return false;
        }
    }
    return true;
}
boolean checkComplete(int l, Bag<String> lengthGroup)
{
    for ( int i=0; i < l ; i++)
    {
        String col = getColumn(i);
        if (!lengthGroup.contains(col))
        {
            return false;
        }
    }
    return true;
}
于 2014-06-10T19:19:18.090 に答える