时间戳

首页 > 解决方案 > 在 Word Snake 游戏问题中找到最长的单词序列

algorithm - 在 Word Snake 游戏问题中找到最长的单词序列

问题描述

我正在玩 Word Snake 游戏，如果可以使用算法解决这个游戏，我正在徘徊。

以下是游戏的描述：

给定一个短语包（一组可能的重复值）：S = {短语1 , 短语2 , 短语3 , ..., 短语N }

蛇是 S 中短语的有序列表，除了第一个短语外，短语中的第一个单词与前一个短语中的最后一个单词匹配。此外，短语i（其中 1 ≤ i ≤ N）只能出现一次。

如何找到所有可能的蛇的最大长度？

示例：对于S = { 'A B' , 'B C' , 'B D' , 'C B' , 'C D'}，最大长度是4因为['A B', 'B C', 'C B', 'B D']是最长的蛇。

标签： algorithmoptimizationdynamic-programminggraph-algorithm

解决方案

这可能可以通过欧拉路径问题的优化问题的一些变化来解决。

将问题简化为图：

G = (V, E) where:
V = { all words }
E = {(word1, word2) | ​If there is a phrase word1, word2 }

在您的示例中：

V = {A, B, C, D }
E = {(A,B), (B,C) (B,D), (C, B), (C, D) }

现在，不幸的是，这个问题的实例不是欧拉路径，但如果存在欧拉路径 - 找到它会给你带来最佳解决方案。例如，如果添加短语'D C'，则图形变为欧拉图，并且确实可以找到欧拉路径：

A -> B -> C -> B -> D -> C -> D, 代表'A B', 'B C', 'C B', 'B D', 'D C', C D'

关于欧拉路径的好消息 - 这个问题可以有效地解决并且不是 NP 完全的（除非 P=NP）。

注意：此解决方案开箱即用，可查找是否存在包含所有短语的序列（并让您轻松找到它）。我不熟悉，也没有研究过这个问题，如果优化问题要困难得多。

推荐阅读