2022年9月23日-秋招机考-第三题-最省出游方案

1000ms

Difficulty: 8

算法标签>

动态规划

No testdata at current.

简化版本:经典TSP问题

给你一张完全图(任意两个点之间有边）。求解一条起点是0的路径使得其访问过所有点恰好一次并且最终要回到0点。 $n \leq 15$

这是经典的TSP问题，可以用dfs求解，但是 $O(n!)$ 的复杂度无法满分通过该题。可以使用状态压缩dp来优化这个过程。这类经典问题网上学习资料很多，可以自行学习。这里推荐一个:https://blog.csdn.net/LarsGyonX/article/details/122843238

In following contests: