algorithm - 这个拼字游戏算法中的 "anchors"到底是什么？

Question

我正在尝试实现这个算法:http://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf但我无法弄清楚这些 anchor 方 block 到底是什么(首先在 3.1.2 中提到，然后在 3.3 中提到)。

我知道他们的候选者都是与板上已有的那些相邻的空方 block ，但不知道我应该选择哪个。

此外，我不知道为什么左侧部分的所有方 block 都有平凡的交叉检查(意味着每个字母都可以放在那里)而 anchor 总是有不平凡的交叉检查。这种情况呢:

_._._._
_._.x.A
_._._._

_ 是空方 block ，x 是 anchor ，A 是板上已有的字母 - 为什么在这种情况下我需要检查 x 以进行交叉检查，而它显然不需要它？

Answer 1

根据 Scrabble 的规则，您的单词必须连接到 - 或者 锚定 在 - 板上的现有单词。现在，当我们一次查看一行时，会发现三种类型的 anchor :

• 同一行中字母左侧的平铺，
• 平铺在同一行字母的右侧，
• 以及与当前行上方或下方行中的字母相邻的图 block 。

如果我们将一个字母放在与上方或下方一行中的字母相邻的 anchor 上，我们也必须使用这些字母形成一个有效的单词，从而对该 anchor 允许的字母施加额外的限制。当在当前行中使用与字母相邻的 anchor 时(仅那些)，我们可以放置在该图 block 上的字母仅受我们将在当前行中形成的单词的约束，所以除了实际的词形成算法之外不需要检查。

这意味着，在您的示例中，实际上不会对图 block x 上的字母有额外的限制。只需找到从 x 向左延伸的前缀，与字母 A 形成一个有效单词(或更长的前缀)。

您可能还想查看 Udacity 类(class)“Design of Computer Programs”，他们在第 6 单元中讨论了拼字游戏解决算法。