
用最小成本流算法破解词语接龙游戏
来源标题:Winning the Categories Game with Min-Cost Flow
一位作者使用最小成本流算法分析WordNet名词层级中的Categories Game,寻找必胜策略。游戏规则是每人说出一个以上一单词末字母开头的类别词,重复即输。作者基于WordNet中40,117个常用单词构建层级树,研究如何利用死胡同词快速终结游戏。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
我最近和一群朋友玩了 Categories Game。就是那个游戏:圈子里每个人说一个属于某类别的词,且必须以前一个词的最后一个字母开头。cat 引出 tarantula,再引出 anteater,依此类推。当然,重复一个词就输了。这里的每个类别都是一个上位词:一个词所属的类别。狗是一种动物,与鸽子和豹同属此类。与真菌和植物一样,动物同样是一种生物。暂且假设一个词只属于一个类别,我们就可以为所有词构建一棵层级树。
WordNet 名词层级结构的交互式圆盘需要 JavaScript。
嗯,几乎所有的词。这里我只限于 WordNet 数据集中的名词。它们有唯一的根节点 entity,分为 45,905 个物理实体和 36,200 个抽象概念。这些计数的是含义,WordNet 称之为 synset。只保留日常使用中命名它们的单个词,就剩下 40,117 个词可供游戏。
如果你对乐趣过敏,想尽可能快地破坏气氛,怎样才能确保获胜?许多类别都有死胡同词,会立即迫使游戏结束。以 vegetables 类别中的 plantain 为例。没有蔬菜以 n 开头¹,所以打出它就会迫使下一个人输。这下可让他们好看了。
交互式单词圆盘需要 JavaScript。
上面的小部件会在一个类别中找到最长的链,并在每个词之后显示完美操作还能到达多少个词。大多数词都会给下一位玩家留下一个回应,所以要想稳赢,就意味着要前瞻每一个回应以及对这些回应的每一个回应。想象我们把每个词视为图中的一个节点,并有一条边指向所有能跟在它后面的词。玩家轮流沿边移动到一个未访问的节点,无法移动者输。这个游戏是广义地理游戏(generalised geography),1978 年由 Thomas Schaefer² 证明为 PSPACE 完全。PSPACE(多项式空间)被认为比 NP(非确定性多项式时间)更难,所以我放弃了获胜的念头。
假设相反,你是一个更愿意合作的群体,想让游戏尽可能长久地进行下去。最长的游戏就是穿过单词图的最长路径。在理想情况下,这条路径会恰好经过每个词一次,形成一条哈密顿路径。但这极不可能,因为词与词之间的连接通常太有限,无法允许这种情况。所以我们想求解的是最长路径问题,它是哈密顿路径问题的推广。这被证明是 NP 难的,因此最著名的算法在最坏情况下需要指数时间。有 40,117 个词参与游戏,这不可行。
我们可以重新表述这个问题。与其为每个词设一个节点,为什么不利用拉丁字母表中只有 26 个字母这一事实呢?考虑一个多图,有 26 个节点,每个字母一个,每个词对应一条边。例如,octopus 创建一条从 o 到 s 的有向边。首尾字母相同的两个词可以互换,因为在链中的任何位置,任何一个都可以代替另一个。所以,在两个字母之间,我们只关心边的数量。
这也改变了问题。一条链中每个词只出现一次,所以在字母图上它是一条迹(trail):一条每条有向边最多使用一次的路由。使用每条边的迹就是欧拉迹。欧拉对这种迹的条件有两部分。第一,除了迹的两端之外,每个字母必须有相同数量的词流入和流出。第二,所有词必须连通。第一部分可以在多项式时间内求解,也是本文的主要内容。第二部分放在最后,在那里它把一些答案变成上界。
在下面的小部件中,每个字母位于圆环上。两个字母之间的词越多,它们之间的边就越宽。选择一个字母会显示有多少词以它开头和结尾。
交互式字母图需要 JavaScript。
单词图远未满足欧拉条件的第一部分。许多字母的流入词远多于流出词,或者相反——想想看,以 y 结尾的词比以 y 开头的词多得多。流出词更多的字母有盈余,流入词更多的字母有赤字。解决这些差异意味着要丢弃一些词。为了在链中保留最多的词,我们必须丢弃最少的词以使每个字母平衡。这是一个关于流的问题。
如果每个字母都平衡,那么链必须是一个环,结束于它开始的字母。我们的策略是先求解最长的环,然后放宽条件,允许两端不同。为了找到它,我们构建一个网络。每一对字母,如果有词从第一个字母流向第二个字母,就得到一条词边,其容量是从第一个字母到第二个字母的词数,成本为 1。另外两个节点补全网络:一个超级源点 sss,向每个有盈余的字母供流;一个超级汇点 ttt,从每个有赤字的字母排流。它们每条边的容量等于该字母的盈余或赤字,成本为 0。
从 uuu 到 vvv 丢弃一个词会使 uuu 的盈余减少 1,v 的赤字减少 1。因此,将一个单位的流从盈余字母推到赤字字母,恰好丢弃其路径上的词。路径中间的每个字母保持其原有的平衡。因此,将所有盈余从 sss 推到 ttt 的最便宜方式,就是保留最多词的那组丢弃。这使得整个问题成为一个最小成本转运问题,是最小成本流的一个特例。下图展示了 plant 类别中的四个词:aloe、erica、vine 和 almond,盈余字母(a 和 v)画在左侧,赤字字母(e 和 d)画在右侧。
成本 0 成本 0 aloe erica almond vine sss 超级源点 ttt 超级汇点 a v e d 盈余 1 盈余 1 赤字 1 赤字 1
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。