求助图论问题

学术版

ningago @ 2022-05-30 15:20:38

求助：给定一个 n 点 m 边的连通的带权无向图，找到一条简单路径使得路径经过所有 n 个点（一个点只能经过一次），求路径的最小权值（路径权值为经过的边权和）

by dehsirehC @ 2022-05-30 15:23:12

不是这是哈密尔顿路径啊

by zhy137036 @ 2022-05-30 15:23:53

看起来很 NPC

by dehsirehC @ 2022-05-30 15:24:43

NPC问题，目前不存在多项式解法，可以用状压DP做到 2^n ，大概就是设当前经过的点集为 S ，当前点为 i 这么DP。

by dehsirehC @ 2022-05-30 15:26:04

说错了，上述状压DP是 O(n^22^n) ，不确定能不能优化。

by ningago @ 2022-05-30 15:26:48

@liqingyang @zhy137036

感谢大佬们Orz

by Graygoo @ 2022-05-30 15:55:09

分支限界法似乎可以优化到O(2^n*n),但因为这个蒟蒻也不知道怎么写，所以不确定

by 已注销Ggr7dn8s @ 2022-05-30 19:18:31

蓝书上的第一章的一道例题，用二进制状压 DP 可以优化到 O(n^2 * 2^n)。

我之前写过，代码在这里，不知道能不能帮到你。