11

この問題について何かを書く前に、お知らせしておく必要があります。

  1. この問題は私の宿題です (作業プログラムを返すのに約 1 週間かかりました)
  2. 私はこの問題に毎日約1週間取り組み、自分の解決策を見つけようとしていました
  3. 完全なプログラムを求めているわけではありません。アルゴリズムについての一般的な考え方が必要です

問題：

与えられたもの: 単語リストと「グリッド」。例:

グリッド (X は任意の文字を意味します):

X X 
XXXX
X X
XXXX

単語リスト：

ccaa
baca
baaa
bbbb

「解決策」の例を見つける必要があります-単語リストから特定のグリッドに単語を適合させることは可能ですか? 解決策が少なくとも 1 つある場合は、1 つ (正しい方) を出力します。いいえ - メッセージを出力して、可能な解決策がないことを示します。与えられた例では、解決策があります：

b c 
baca
b a 
baaa

私がすでに試したことをすべて書くのは難しいです (英語は私の母国語ではなく、間違った考えの論文もたくさん持っているため)。

私の単純なアルゴリズムは次のように機能します。

  1. 最初の単語には適切な長さが必要なので、適切な長さの (最初の?) 単語を見つけます (与えられた例のグリッドと単語リストを使用して、私が考えていることを示します):

    c X 
cXXX
a X
aXXX

  2. 最初の一般的な文字 (2 つの単語の交差部分) については、グリッドに適合する (最初の) 単語を見つけます (つまり、適切な長さと適切な位置に共通の文字があります)。そのような単語がない場合は、(1) に戻って、別の最初の単語を取得します。元の例では、"c" で始まる単語がないため、(1) に戻って次の単語を選択します (最初の単語が "bbbb" になるまで、この手順を数回繰り返します)。これで、次のようになりました。

    b X 
bXXX
b X
bXXX

    そして、「b」で始まる単語を探しています。たとえば、次のようになります。

    b X 
baca
b X
bXXX

  3. 一般的なプロセス:与えられたグリッドに適合する単語のペアを見つけようとします。そのような単語がない場合は、前のステップに戻って別の組み合わせを使用します。そのような単語がない場合、解決策はありません。

上記のすべてが混沌としています。少なくとも問題の説明を理解していただければ幸いです。アルゴリズムのドラフトを書きましたが、それが機能するかどうか、これを適切にコーディングする方法がわかりません (私の場合: c++)。さらに、(上記の例でも) 2 つ以上の他の単語に依存する単語を見つける必要がある場合があります。

たぶん私は何か明白なことが見えないだけかもしれません、多分私は愚かすぎるのかもしれません... まあ、私は本当にこの問題を解決しようとしました. 私はこの問題について自分の考えを正確に説明できるほど十分に英語を知らないので、ここにすべてのメモを載せることはできません (1 つの考えを説明しようとしましたが、難しかったです)。信じられないかもしれませんが、私は解決策を見つけるのに何時間も費やしましたが、ほとんど何もありません...

解決策を説明したり、この問題を解決する方法のヒントを提供したりできれば、本当に感謝しています。

4

2 に答える 2

6

コルソード問題はNP-Completeであるため、ベスト ショットはブルート フォースです。すべての可能性を試し、可能性が有効になったら停止します。考えられる解決策をすべて使い果たしたら、失敗を返します。

この問題が NP-Complete であることを証明する削減は、この記事のセクション 3.3にあります。

バックトラッキングを使用したブルート フォース ソリューションは次のようになります: [疑似コード]:

solve(words,grid):
   if words is empty:
       if grid.isValudSol():
          return grid
       else:
          return None
   for each word in words:
       possibleSol <- grid.fillFirst(word)
       ret <- solve(words\{word},possibleSol)
       if (ret != None):
          return ret
   return None

ここでfillFirst()は、まだ埋められていない最初のスペースを埋める関数であると仮定します [最初は、実際には空のスペースの一貫した順序にすることができますが、一貫している必要があります!] でありisValid()、指定されたグリッドが有効なソリューション。

于 2011-12-21T06:54:24.843 に答える
3

今朝、プログラムを書きました。疑似コードでもう少し効率的なバージョンを次に示します。

#pseudo-code
solve ( words , grid ) : solve ( words , grid , None ) 

solve ( words , grid , filledPositions ) :
    if words is empty :
        if grid is solved :
            return grid
        else :
            raise ( no solution )
    for ( current position ) as the first possible word position in grid 
            that is not of filledPositions :
        # note : a word position must have no letters before the word
            # 'before the word' means, eg, to the left of a horizontal word
            # no letters may be placed over a ' ' 
            # no letters may be placed off the grid
        # note : a location may have two 'positions' : one across , one down
        for each word in words :
            make a copy of grid
            try :
                fill grid copy, with the current word, at the current position
            except ( cannot fill position ) :
                break
            try :
                return solve ( words\{word} , grid copy , 
                        filledPositions+{current position} )
            except ( no solution ) :
                break
        raise ( no solution )

グリッド内で単語を水平方向にフィッティングするための私のコードは次のとおりです: http://codepad.org/4UXoLcjR

以下は、STL から使用したものです。

http://www.cplusplus.com/reference/algorithm/remove_copy/

http://www.cplusplus.com/reference/stl/vector/

于 2011-12-21T21:26:05.600 に答える