未加权无向图中在同一顶点开始和结束的最长路径
Longest path in unweighted undirected graph starting and finishing in the same vertex
我有一个问题，我需要找到最长的路径。给定一个未加权的无向图。从一个给定的顶点开始，我需要访问尽可能多的顶点并在同一个顶点结束而不访问每个顶点一次。
我发现的大多数算法都是针对特殊情况的（非循环的、有向的等）。一个想法可以是为顶点的每个子集找到哈密顿循环（可以使用回溯生成子集）。但我想一定有更好的算法。
正如您所发现的，找到最大的循环涉及找到其子图的 Hamiltonian cycles，因此是 NP 完全的 - 除非您正在处理一些特殊的 class 图， 任何 解决方案的复杂性都将呈指数级增长。
聪明的蛮力方法（例如 bitmask）是解决此类问题的最佳效率。
我有一个问题，我需要找到最长的路径。给定一个未加权的无向图。从一个给定的顶点开始，我需要访问尽可能多的顶点并在同一个顶点结束而不访问每个顶点一次。
我发现的大多数算法都是针对特殊情况的（非循环的、有向的等）。一个想法可以是为顶点的每个子集找到哈密顿循环（可以使用回溯生成子集）。但我想一定有更好的算法。
正如您所发现的，找到最大的循环涉及找到其子图的 Hamiltonian cycles，因此是 NP 完全的 - 除非您正在处理一些特殊的 class 图， 任何 解决方案的复杂性都将呈指数级增长。
聪明的蛮力方法（例如 bitmask）是解决此类问题的最佳效率。