对于大规模TSP问题,为什么遍历算法不可行而贪心算法可行

2025-04-07 00:22:33
推荐回答(1个)
回答1:

TSP属于NPC问题,一般只能靠近似算法求出近似解,问题规模小的时候,可以直接穷举问题空间,得出最优解,不过问题规模一大就不行了,问题空间是指数暴涨的,这时候只能退而求其次,求近似最优解,而对应的近似算法中会大量使用贪心策略,所以其实不是可不可行的问题,贪心牺牲了 解的精度(求得的不一定是最优解),但换来了时间上可观的节约(直接降到多项式)。