4

そのような問題は私の大学で私に与えられました。おそらく、誰かが問題を解決するための興味深いアルゴリズムを持っているでしょう。スタックオーバーフローにはいくつかの解決策がありますが、どれも問題ありません (すべての可能性をループしているため)。

問題: 与えられた単語を与えられたテーブル、グリッド (四角形、以下の入力を参照) に割り当てるためのすべての可能な組み合わせを見つけます。フリー セルがあってはならず、単語は左から右または上から下に配置できます。行 (列) 内の単語の後に単語を配置することはできません。

入力: 長方形の領域、例:

+-----+
|  *  | 
|     |
+-----+

また

+-----+
|   * |
|     |
|    *|
|   * |
+-----+

その後、さまざまな単語が入力され (次の入力データ)、次のようなグリッドが埋められます。

cdi
zobxzst
tdxic
r
sc
zro
and etc ...

番号は最初は不明ですが、標準入力 (アクティブな EOF) の終わりまで入力します。

出力: 1 つの解が存在する場合、塗りつぶされたグリッド内にその可能な解を出力します。解または解の数がない場合は、0 またはその正確な数を出力します。

例：

(テーブル入力)

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

それから言葉cdi zobxzst tdxic r sc zro rgfvacd oikf df x c r xvf ogish za sh fc hh h bfkh

(それぞれ入力としてですが、ここではスペースで区切られています。)

出力 (1 ソリューションのみ):

+-----+
|zro*h|
|ogish|
|bfkh*|
|xvf*r|
|za*c*|
|sc*df|
|tdxic|
+-----+

重要な注意: 入力されたグリッドは 16 (!) セルのみに制限されており、単語数は 60 未満です。すべての可能な組み合わせを検索するアルゴリズムを作成しましたが、実行時間が制限されているため (10この問題は大まかなアルゴリズムでは解決できませんでした (たとえば、15 グリッドで 15、約 60! 通常の 2GHz PC で約 1 日で処理できる可能性のある順列またはそれ以上の可能性があります)。

別のユニークなソリューションが存在する可能性があります。おそらく、この問題はプログラミングよりも数学的なものであり、上下と比較して左右のコンボを使用することは可能でしょうか? それとも加重セルですか？

PS その問題を解決するのに 3 週間かかります。そうでない場合は、3 週間後にここに解決策を投稿できます (朗報) ;)

4

2 に答える 2

2

stackoverflowにはいくつかの解決策がありますが、どれも問題ありません（すべての可能性についてループしているため）。

私の考えもおそらく間違っています：しかし、これが私の頭のてっぺんからの考えです。

考えられるすべての組み合わせを検索するアルゴリズムを作成しました

数が多すぎる場合、問題はおそらく、不可能な組み合わせや可能な組み合わせも検索/ループしていることです。

たとえば、左上隅に「zro」のような単語を配置する場合、その下の垂直方向の単語に配置できる「可能な」組み合わせはほとんどありません。

  1. 最初の垂直方向の単語は「z」で始まる必要があります
  2. 2番目の垂直方向の単語は「r」で始まる必要があります
  3. 3番目の垂直方向の単語は「o」で始まる必要があります
  4. 2行目の文字の組み合わせ（縦の単語を配置した結果）自体が有効な単語である必要があります
  5. 等

したがって：

  1. 任意の単語を選択して、左上隅に配置します
  2. 上記の制約を満たす既存の単語を検索します
  3. そのような単語が1つ以上見つかった場合は、この方法で続行して、すべてを解決できるかどうかを確認してください。または失敗した場合は、別の最初の単語を使用して再試行してください

概要：

  • すべての完全なグリッドを生成してから、それをテストして、すべての制約を満たしているかどうかを確認しないでください
  • 代わりに、グリッドを構築するときに制約を使用して、テストする可能性の数を減らします

最初の単語から始めて、グリッドを解決することをお勧めします。

左上隅の各単語をテストする代わりに、開始位置を生成するためのより良い方法（たとえば、萌えがすぐに不可能性を排除するため）は次のとおりです。

  • 最長の単語を検索します（例rgfvacd）
  • 交差/結合する単語の可能なすべての組み合わせを検索します
  • それらの有効な組み合わせのそれぞれをグリッドに配置してみてください
于 2012-11-13T00:49:54.800 に答える
1

あなたの例では、最初に入力する必要がある単語の長さを確認することをお勧めします。

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

2 つの 7 文字の単語、3 つの 1 文字の単語などがあります。

このリストをカウントに従って並べ替え、最初に単語の長さが最小のカウントで試す必要があります。次の反復では、検索する必要がある単語のリストを作成する必要があります。たとえば、「a」で始まる 3 つの 4 文字の単語です。 - 単語リストに残っているこれらの単語の数を数えてから、単語数が最も少ないものを選択する必要があります。0 の場合は戻ります。

それが理にかなっていることを願っています。

于 2012-11-13T10:48:31.980 に答える