NP-hard

百度搜索 PONDER 天涯 或 PONDER 天涯在线书库 即可找到本书最新章节.

NP是指非确定性多项式（non-deterministic polynomial）。非确定性指可用一定数量的运算去解决多项式时间内可解决的问题。
推销员旅行问题（Travel Saleman Problem or TSP）：从**经过n 个城市， 最后返回**。 任意两市都有飞机直达，票价不等。公司只报销 C 元，是否存在行程安排，使得遍历所有城市且总路费小于 C？如果你任意给出一个行程安排，很容易算出旅行总开销。要知道总路费小于 C 的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排。
“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。对其中一个问题存在有效算法时，每个问题都会有有效算法。
倾向于接受NP完全问题（NP-Complete或NPC）和NP难题（NP-Hard或NPH）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求近似算法。

百度搜索 PONDER 天涯 或 PONDER 天涯在线书库 即可找到本书最新章节.