1

我目前正在做一项任务，我坚持使用这种方法。

我有一个填字游戏问题，它由一个空网格组成（没有像传统填字游戏那样的实心正方形），宽度和高度在 4 到 400（含）之间变化。

规则：

  1. 单词是输入的一部分——包含 10 到 1000 个（含）长度不等的英语单词的列表。
  2. 水平词只能与垂直词相交。
  3. 垂直词只能与水平词相交。
  4. 一个词只能与其他 1 或 2 个词相交。
  5. 每封信值一分。
  6. 单词周围必须有 1 个网格空间间隙，除非它是相交单词的一部分。

例子： 

X X X X X X  
X B O S S X  
X X X X X X

目标：
在 5 分钟的时间内获得最高分。

到目前为止：
经过一些研究，我知道这是一个 NP-Hard 问题。因此，无法计算出最优解，因为无法检查每个组合。

最简单的解决方案似乎是根据长度对单词进行排序并插入得分最高的单词以获得最高分数（贪婪算法）。

我还被告知一个递归树，其节点由替代的等分词插入组成，背包算法适用于这个问题（不确定实现会是什么样子）。

问题：

  1. 是什么让我可以在 5 分钟的时间跨度内检查最大组合数，并根据最大可能的单词列表和网格大小进行缩放？
  2. 插入单词时可以应用哪些启发式方法？

顺便说一句，这里的目标是在 5 分钟内获得最佳解决方案。澄清一个有效单词的每个字母得 1 分，因此一个 5 个字母的单词得 5 分。

在此先感谢我整天都在阅读很多关于填字游戏研究论文的数学符号，这似乎让我绕了一圈。

4

2 回答 2

0

我将从具有以下特征的单词开始：

  • 它应该有最大可能的交叉点。
  • 它的长度应该使得该长度的单词在列表中的数量最少。

即，字长应该是最不频繁和最多的交叉点。
这种选择的原因是它将进一步减少可以选择的单词的可能性。例如。选择一个大小为 9 且有 2 个其他交叉点的单词。这些相交的词的长度为 6 和 5（比如说）。现在，您已经消除了所有长度为 6 和 5 的单词的可能性，这些单词的第 3 个字符是 'a' 而第 2 个字符是 's'（比如，'a' 和 's' 是相交的字母）。

如果有许多地方具有相同的配置，请运行此选择过程一或两个步骤，以便更好地选择首先填充网格的哪个部分（单词）。

现在，尝试在第一个选择的位置填写所有单词（因为它有最小频率，应该很好用），然后在填字游戏中更深入地填写它。在达到死胡同之前，无论哪个词导致最多分，都应该是您的解决方案。当你走到死胡同时，你可以用一个新词重新开始。

于 2015-09-10T14:14:24.833 回答
0

这似乎是离散优化中一个非常有趣的问题。你当然是对的；由于单词的数量和可能的位置数量，您无法探索空间的一小部分。

同样考虑到 5 分钟的时间限制（很短），我认为你将很难使用任何可靠的启发式方法。我认为你最好的选择可能是某种随机排列/模拟退火算法。

如果我这样做，我会首先计算单词簇，完全忽略填字游戏结构本身。取一个词，找到与之相交的第二个词。然后找到另一个适合这个结构的单词（每个单词最多 2 个交叉点），依此类推。您应该最终得到许多这样的集群，您可以按密度（使用的点/面积）对其进行排名。我认为你应该能够相对快速地做到这一点。

然后对于随机排列/模拟退火部分，对于我的移动，我会将一个簇或未使用的单词放在填字游戏本身上，或者移动一个现有的簇/单词。只需随时保存当前得分最高的配置，然后在 5 分钟后返回。

如果 5 分钟太短而无法使用随机排列找到任何有意义的东西，另一种方法可能是使用约束传播理念来处理这些集群。

于 2015-09-10T17:36:39.417 回答