1

私はすでにこれに関するフォーラムとさまざまな質問を見てきました。

しかし、私は別のことを聞きたいです。異なる単語の 2 つの単語リストと、0 と 1 で指定された 1 つのグリッドがあります。行の単語リスト 1 と列の単語リスト 2 から単語を選択する必要があります。

主な問題は、与えられた時間の制約内で複数の解決策を見つけなければならないことです。誰かが私にそのための良いアルゴリズムを提案できますか? どのようなアルゴリズムアプローチをとるべきかわかりません。

もう 1 つ、2 つの言語オプションがあります。実装する方が良いC ++またはJavaのいずれか。

ありがとうございました

4

3 に答える 3

2

私はあなたが望むことをする解決策を見つけました。悲しいことに、私はそれを信用することができません:)

これが例です。次のようなパターンファイルをフィードしますpattern1。

    ##   ##    
    #     #    
    #     #    
           #   
###   ###    ##
#      #      #
   #     #     
    #     #    
     #     #   
#      #      #
##    ###   ###
   #           
    #     #    
    #     #    
    ##   ##

たとえば、次のように、プログラムを呼び出します。

./cword pattern1 /etc/dictionaries-common/words

出力は

SODS##HOG##AMPS
APIA#RADON#LAUE
TESS#ALONE#ERNA
ENCHANTRESS#GYM
###ADS###TUTU##
#PAYDAY#ESPIES#
REV#SCALD#SCRIP
ARON#KNOWS#SITE
MCCOY#KNITS#TET
#HARASS#NAPPED#
##TACT###DIE###
MCI#COORDINATES
ELOY#AMARU#ROLL
SINE#TARIM#LIMA
SOSA##REP##SLOT

または、別の時間を実行します。

PAWN##HOT##BEST
OLEO#SURYA#OMAR
LOAN#AGAPE#ABLE
SELFISHNESS#RTE
###ASH###OKAY##
#KATMAI#EPILOG#
INN#SYNOD#MULES
SETH#SCHWA#MONA
MEIER#AMIDS#GEM
#SPLATS#NOWAYS#
##APSE###RAY###
WIS#PATRONYMICS
ALTA#CHOKE#AREA
SLOP#HEARD#ROBS
PSST##ERA##ANUS

もちろん、パターンが大きい場合やワードリストが小さい場合は、マイレージが（大幅に）変わる可能性があります。Q9550プロセッサで26.5秒で1000世代を実行できました。

time for a in $(seq 1 200)
do 
    for a in 1 2 3 4 5
    do 
        ./cword pattern1 /etc/dictionaries-common/words | md5sum&
    done
    wait
done | sort | uniq -c | sort -n | tee >(wc -l)

出力は、これらが実際に1000のユニークなソリューションであることを確認しました。あなたが私に尋ねれば、悪くはない。（タイミングには、ソリューションごとのmd5sumsを計算する時間が含まれていました）

于 2011-04-27T22:58:36.603 に答える
1

Dancing Links または DLXアルゴリズムと呼ばれるものを使用できる場合があります。これは、正確なカバーの問題を解決するための非常に効率的なアルゴリズムです。

これを使用して数独パズルを解くプログラムがいくつかあります。

正直なところ、正確なカバーの問題については、これがあなたのニーズに確実に役立つとは言えませんが、一見の価値があります.

于 2011-04-27T21:12:36.087 に答える
1

クロスワードを行うと、通常、特定の文字が特定の位置にある、特定の長さの単語を探していることに気づきます。したがって、おそらく次のような関数が必要になるでしょう。

List<String> findWord(int ofLength, char withLetter, int atIndex) {/*implementation*/}

これはおそらく、事前に構築された HashMaps のセットを使用して、候補のセットを迅速に生成できます。(おそらく、その単語が現在クロスワードで既に使用されているかどうかを追跡できるようにしたいでしょう...重複が許可されていないと仮定します)

人々が行うもう 1 つのことは、ヒントを使用して推測することです。おそらく強力な AI を探しているわけではないので、力ずくのアルゴリズムが残されていると思います...その場合、最初に最大の単語から始めてクロスワードを入力してみてください。

スケルトン アルゴリズム:

private void checkPuzzleOn(Row row, SolutionSet s) {

    List<Row> crossingRows = row.getCrossingRows();

    if(allAlreadyFilled(crossingRows)) {
        //This part of the crossword works; store info in solution set.
        return;
    }

    crossingRows.sortBiggestToSmallest();

    foreach(Row crossing in crossingRows) {

        int index = row.getIndexOfIntersectionWith(crossing);
        char c = row.charAt(index);

        List<String> candidates = findWords(crossing.length, c, index);
        foreach(String candidate in candidates) {
            verifyAgainstPresentWords(crossing, candidate); //check that using this word won't collide with others; important because of cycles.
        }

        if(candidates.isEmpty()) {
            //This part of the crossword won't match! store info in solution set.
            return;
        }

        foreach(String candidate in candidates) {
            crossing.setWord(candidate);
            checkPuzzleOn(crossing, s);
        }
    }
}
于 2011-04-27T21:20:48.380 に答える