为了更精确地表述问题，让我将其重新表述为“城市”游戏。扮演两名球员。玩家 1 说出一些城市名称，比如 Moscow 。玩家 2 现在必须说出一些城市名称，从之前被称为城市的最后一个字母开始。这封信是 W ，所以第二个玩家说的是 Washington 。玩家 1 接下来调用某个城市，以 N 开头为 Norilsk ，玩家 2 现在必须说出一些城市名称，以 K 开头等等。一、谁也不能说城名输一场。
现在假设我们有字母 a..z 作为图形顶点和(比如 10000)个城市名称列表作为边。每条边连接两个顶点(如 moscow 连接 m 和 w )并且是定向的 m -> w 。
所以我们现在有了面向多重图。
任务是从列表中找到最长可能的城市序列。每个城市只能依次出现一次。所以任务非常接近欧拉路径，但在给定的图中可能有很多欧拉子图。
我的问题是如何在合理的时间内找到最大路径？
我知道，maximum euler subgraph 问题是 NP 难题。但是在我的问题图中，连接非常紧密，并且它的顶点数量很少且固定(就像在上面描述的“城市”游戏中一样)。也许可以用它来构建一些好的启发式方法？
我还发现了一些关于 stackoverflow 的 word sequences 问题，但没有合理的答案，因为很明显，如果单词是边，单词图中的哈密顿子图比字母图中的欧拉子图更难找到，而且所有这些问题都是关于哈密顿的，而不是欧拉子图。
将欣赏任何编程语言或伪代码中的任何有用链接、想法、算法描述和方法。
最好的问候，康斯坦丁
最佳答案
我认为您会发现更多资源将其表示为有向图中最长路径问题。问题的最长路径公式似乎比欧拉公式更受关注。另请注意，最长路径与汉密尔顿路径不同，因为前者不需要跨越图形。
将每个城市视为一个顶点，并在表示可行序列的顶点对之间放置一条弧线。
值得一提的是，最长路径很难近似，并且在非常简单的图中仍然是 NP 完全的:http://en.wikipedia.org/wiki/Longest_path_problem
以下是一些相关论文的链接:
http://link.springer.com/article/10.1007/BF02579454
http://lup.lub.lu.se/luur/download?func=downloadFile&recordOId=957757&fileOId=9\
65291
关于algorithm - 任意定向多重图的最大欧拉子图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19290783/