给出起始节点的所有边缘的算法

Question

我正在与一位朋友一起开发游戏算法,但我们陷入了困境.目前,我们有一个循环无向图,我们试图从起始节点S找到覆盖每个边缘的最快路径.我们不是在寻找旅游,而且可能会有重复的边缘.

关于算法或近似的任何想法？我确定这个问题是NP难的,但我不相信它是TSP.

Answer 1

路线检查

这称为路线检查问题，并且确实有多项式解。

基本思想（有关更多详细信息，请参阅链接）是很容易求解欧拉路径（我们访问每个边一次），但欧拉路径仅适用于某些图。

特别是，图必须是连通的并且具有 0 或 2 个奇数度的顶点。

然而，可以通过以最便宜的方式添加额外的边来将其推广到其他图，从而生成具有欧拉路径的图。（请注意，我们添加了更多边，因此我们可能会在原始图中的边上多次移动。）

选择添加附加边的最佳方式是一个可以在 O(n^3) 内解决的最大匹配问题。

聚苯乙烯

顺便说一句，我今天早些时候为平面最大切割问题编写了一个简单的演示（游戏链接）。事实证明，这个问题的解决方案是基于完全相同的路线检查问题:)

编辑

我刚刚从评论中发现，在您的特定情况下，您的图表可能是一棵树。

如果是这样，那么我相信答案要简单得多，因为您只需要对树进行 DFS，确保首先访问最浅的子树。

例如，假设您有一棵树，其边 S->A 和 S->A->B。S 有两棵子树，你应该先访问 A，因为它更浅。

访问的总边数将等于完整 DFS 中访问的边数减去最后访问的叶子的深度，这就是为什么要最小化总边数要最大化最后一个叶子的深度，从而访问最浅的子树第一的。