• 转载：关于NP-Hard问题

    日期：2010-03-13 | 分类：math

    NP 是 Non-deterministic Polynomial 的缩写，NP 问题通俗来说是其解的正确性能够被很容易检查的问题，这里"很容易检查"指的是存在一个多项式检查算法。
    例如，著名的推销员旅行问题（Travel Saleman Problem or TSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，…，等 n 个城市， 最后返回香港。 任意两个城市之间都有飞机直达，但票价不等。现在假设公司只给报销 $C 块钱，问是否存在一个行程安排，使得他能遍历所有城...

    Tags：NP NPC NP-hard
    victor0396 发表于14:26:00 | 阅读全文 | 评论0 | 编辑 | 分享 0
共1页 1