1

次のような文字の 4x4 2D 配列があります。

A B C D
U A L E
T S U G
N E Y I

ここで、3 文字、4 文字などのすべての順列を 10 まで見つける必要があります。

したがって、これから「見つける」ことができるいくつかの単語はTEN、、、、BALDです。BLUEGUYS

SOでこれを検索してGoogleで検索しましたが、具体的な助けにはなりませんでした。どのアルゴリズムを学ぶべきか正しい方向に私を押してくれませんか (A* かな?)。私はアルゴリズムの専門家ではないので、優しくしてください (私たち全員ではありません (まあ、少なくとも多数派です :)) が、正確にどこから始めればよいかわかりませんが、喜んで学びたいと思っています。

4

3 に答える 3

2

ああ、それはゲームBoggleではありません...あなたは順列を必要とせず、グラフを必要とし、グラフ内の単語を見つけたいと思っています。

さて、私はキャラクターをグラフノードとして配置することから始めて、それらをそれらのすぐ隣と斜めの隣人に結合します。

今、あなたはただグラフを検索したいだけです。16個の開始ノードのそれぞれについて、再帰を実行します。新しいノードに移動するときは、再度移動できないように、使用済みとしてフラグを立てる必要があります。ノードを離れる（完全に検索した）場合は、フラグを解除します。

これがどこに向かっているのか見ていただければ幸いです...

ノードごとに、その隣接ノードのそれぞれにアクセスし、その文字を文字列に追加します。この検索を念頭に置いて辞書を作成した場合、これまでに使用した文字が単語の先頭であるかどうかをすぐに確認できます。これにより、検索が適切に絞り込まれます。

私が話している辞書の種類は、アルファベットの文字ごとに1つの子を持つノードを持つツリーがある場合です。これらの利点は、検索で現在使用しているツリーノードを保存するだけでよいことです。単語を見つけたと判断した場合は、親ノードを経由してバックトラックし、それがどの単語であるかを判断します。

このツリースタイルと深さ優先グラフ検索を使用すると、考えられるすべての単語の長さを同時に検索できます。それは私が考えることができる最も効率的な方法についてです。

グラフ検索用の疑似コディッシュ関数を書いてみましょう。

function FindWords( graphNode, dictNode, wordsList )
    # can't use a letter twice
    if graphNode.used then return

    # don't continue if the letter not part of any word
    if not dictNode.hasChild(graphNode.letter) then return
    nextDictNode = dictNode.getChild(graphNode.letter)

    # if this dictionary node is flagged as a word, add it to our list
    nextDictNode.isWord()
        wordsList.addWord( nextDictNode .getWord() )
    end

    # Now do a recursion on all our neighbours
    graphNode.used = true
    foreach nextGraphNode in graphNode.neighbours do
        FindWords( nextGraphNode, nextDictNode, wordsList )
    end
    graphNode.used = false
end

そしてもちろん、すべてを開始するには：

foreach graphNode in graph do
    FindWords( graphNode, dictionary, wordsList )
end

残っているのは、グラフと辞書を作成することだけです。そして、その辞書のデータ構造が何と呼ばれているのかを思い出しました。トライです。よりスペース効率の高いストレージが必要な場合は、基数ツリーなどに圧縮できますが、最も簡単な（そして最速の）方法は、ストレートトライを使用することです。

于 2013-01-16T15:24:16.617 に答える
2

あなたが優先言語を定義していないので、私はC#に実装しました:

private static readonly int[] dx = new int[] { 1, 1, 1, 0, 0, -1, -1, -1 };
private static readonly int[] dy = new int[] { -1, 0, 1, 1, -1, -1, 0, 1 };

private static List<string> words;
private static List<string> GetAllWords(char[,] matrix ,int d)
{
    words = new List<string>();
    bool[,] visited = new bool[4, 4];
    char[] result = new char[d];

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            Go(matrix, result, visited, d, i, j);

    return words;
}

private static void Go(char[,] matrix, char[] result, bool[,] visited, int d, int x, int y)
{
    if (x < 0 || x >= 4 || y < 0 || y >= 4 || visited[x, y])
        return;

    if (d == 0)
    {
        words.Add(new String(result));
        return;
    }

    visited[x, y] = true;
    result[d - 1] = matrix[x, y];

    for (int i = 0; i < 8; i++)
    {
        Go(matrix, result, visited, d - 1, x + dx[i], y + dy[i]);
    }

    visited[x, y] = false;
}

結果を取得するコード:

    char[,] matrix = new char[,] { { 'A', 'B', 'C', 'D' }, { 'U', 'A', 'L', 'E' }, { 'T', 'S', 'U', 'G' }, { 'N', 'E', 'Y', 'I' } };
    List<string> list = GetAllWords(matrix, 3);

パラメータ 3 を必要なテキスト長に変更します。

于 2013-01-16T15:43:05.517 に答える
0

長さ16の配列として4x4行列を使用しているようです。その場合は、再帰的アプローチを試して、k次のように長さまでの順列を生成できます。

findPermutations(chars, i, highLim, downLim, candidate):
    if (i > downLim):
         print candidate
    if (i == highLim): //stop clause
         return
    for j in range(i,length(chars)):
         curr <- chars[i]
         candidate.append(curr)
         swap(chars,i,j) // make it unavailable for repicking
         findPermutations(chars,i+1,highLim,downLim,candidate)
         //clean up environment after recursive call:
         candidate.removeLast()
         swap(chars ,i, j)

アイデアは、より多くの文字（あなたの場合は3）を持つ各「候補」を印刷しdownLim、上限（highLim）-10に達したときに終了することです。

毎回、次に配置する文字を「推測」し、それを候補に追加し、再帰的に呼び出して次の候補を見つけます。
考えられるすべての推測について、このプロセスを繰り返します。

Choose（10,16）* 10があることに注意してください！+選択（9,16）* 9！+ ... + Choose（3,16）* 3！そのような順列が異なるため、時間がかかる可能性があります...

意味のある単語が必要な場合は、候補を「実際の単語」と照合するために、ある種の辞書が必要になります（または、あるコンテキストから統計的に辞書を抽出します）。

于 2013-01-16T15:21:19.820 に答える