像TSP,cpp问题属于优化问题。能够用是或者否回答的，是判定问题。
优化问题可以转换为判定问题的，是（不可判定的问题，比NP更难，因为它无解
）可求解。
比如：tsp转化为判定问题：是否存在***的路线,使得***?
NPC问题属于判定问题中的一种。如果一个优化问题,转化为判定问题,判定问题是
NPC问题,那么这个优化问题就是NPhard问题.
整数规划,线性规划是NPhard问题.
所以,对于如cpp这样不属于nphard问题的问题,如果用整数规划来求解,则反而成
为nphard问题的时间复杂度了.
参考资料：网络优化
阅读(11465) | 评论(0) | 转发(0) |
