为了更准确地表述问题，让我将其重新表述为“城市”游戏。扮演两名球员。玩家 1 说出某个城市名称，比如Moscow。玩家 2 现在必须说出某个城市名称，从之前称为城市的最后一个字母开始。这封信是W，所以第二个玩家说了类似的话Washington。玩家 1 接下来呼叫某个城市，以Nas开头Norilsk，玩家 2 现在必须说出某个城市名称，以K等等开头。一、谁不能说城市名就输了。
现在假设我们将字母a..z作为图形顶点，将（比如 10000 个）城市名称列表作为边。moscow每条边连接两个顶点（如connectm和w）并且是有方向的m -> w。
所以我们现在有面向多图。
任务是从给定的列表中找到可能的最长城市序列。每个城市只能按顺序出现一次。所以任务非常接近欧拉路径，但是在给定的图中可能有很多欧拉子图。
我的问题是如何在合理的时间内找到最大路径？
我知道，最大欧拉子图问题是 NP 难的。但是在我的问题中，图是非常紧密连接的，并且它具有少量且固定数量的顶点（就像上面描述的“城市”游戏中一样）。是否可以使用它来构建一些好的启发式方法？
我还在stackoverflow上发现了一些单词序列问题，但没有合理的答案，因为很明显，单词图中的汉密尔顿子图比字母图中的欧拉子图更难找到，如果单词是边，所有这些问题都是关于汉密尔顿的，不是欧拉子图。
将欣赏任何编程语言或伪代码中的任何有用的链接、想法、算法描述和方法。
最好的问候，康斯坦丁