为了更准确地表述问题，让我将其重新表述为“城市”游戏。玩两个玩家。玩家 1 说出一些城市名称，比如 Moscow。玩家 2 现在必须说出一些城市名称，从之前称为城市的最后一个字母开始。这个字母是W，所以第二个玩家说的是Washington。玩家 1 接下来调用某个城市，以 N 开头为 Norilsk，玩家 2 现在必须说出一些城市名称，以 K 开头，依此类推。一、谁不能说城市名就输了。
现在假设我们将字母 a..z 作为图的顶点，并将(比如 10000)个城市名称列表作为边。每条边都连接两个顶点(如 moscow 连接 m 和 w)并且面向 m -> w。
所以我们现在有了定向多重图。
任务是从给定的列表中找到可能最长的城市序列。每个城市只能按顺序出现一次。所以任务非常接近欧拉路径，但是在给定的图中可能有很多欧拉子图。
我的问题是如何在合理的时间内找到最大路径？
我知道，maximum euler subgraph问题是NP难的。但是在我的问题中，图的连接非常紧密，并且它的顶点数量很少且固定(就像上面描述的“城市”游戏一样)。是否可以使用它来构建一些好的启发式方法？
我还发现了一些 word sequences关于 stackoverflow 的问题，但没有合理的答案，因为很明显，如果单词是边，则单词图中的汉密尔顿子图比字母图中的欧拉子图更难找到，而且所有这些问题都是关于哈密尔顿的，而不是欧拉子图。
将欣赏任何有用的链接、想法、算法描述和任何编程语言或伪代码的方法。
谨致问候，康斯坦丁
最佳答案
我认为您会发现更多资源将此表示为有向图中的最长路径问题。问题的最长路径公式似乎比欧拉公式受到更多关注。另请注意，最长路径不同于汉密尔顿路径，因为前者不需要跨越图形。
将每个城市视为一个顶点，并在表示可行序列的成对顶点之间放置一条弧。
值得一提的是，最长路径很难近似，并且在非常简单的图中仍然是 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/