11

在我写一些关于这个问题的东西之前，我需要让你知道：

  1. 这个问题是我的作业（我有大约 1 周的时间返回工作计划）
  2. 我每天都在解决这个问题大约一周，试图找出自己的解决方案
  3. 我不是要完整的程序；我需要对算法有一个大致的了解

问题：

给定：一个单词表和一个“网格”，例如：

网格（X 表示任何字母）：

X X 
XXXX
X X
XXXX

词汇表：

ccaa
baca
baaa
bbbb

您必须找到示例“解决方案” - 是否可以将单词列表中的单词放入给定的网格中？如果至少有一种解决方案，请打印一个（以正确者为准）。如果没有 - 打印消息，则表示没有可能的解决方案。例如，有一个解决方案：

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 个或更多其他单词的单词。

也许我只是看不到明显的东西，也许我太愚蠢了，也许......好吧，我真的很努力解决这个问题。我的英语水平不足以准确描述我对这个问题的看法，所以我不能把我所有的笔记都放在这里（我试图描述一个想法，这很难）。信不信由你，我花了很长时间试图找出解决方案，但我几乎一无所获......

如果你能描述一个解决方案，或者给出如何解决这个问题的提示，我将非常感激。

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()一个函数填充了第一个尚未填充的空间 [first 实际上可以是空白空间的任何一致顺序，但它应该是一致的！]，并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 回答