There are some Np hard problems we know, although we can not get a exactly answer, there are still polynomial time approximation algorithms.
Go back to Main page Notes for Complexity theory
Introducing some good algorithms for Vertex covering and compare it with Greedy algorithm.
最近剛好看了 clay 千禧年數學難題 有個 NP=P? 之前每次想大概了解在幹啥 都看無 最近看了一些演算法介紹 漸漸覺得很帥 這問題難怪很難~~ P :就是那些可在多項式時間解出的問題的集合 NP:就是 給你一個解 你可以帶進去驗證 只需要多項式時間的問題的集合
比方給你一個高次方程 你要解 一定很難 但要你驗證一個數字是不是解 就簡單多了 這問題抽象上是說 是不是 這兩個問題的難度相等...
感覺就不相等...但目前沒有證明 NP=P?集合上的相等
比方銷售員問題 一個銷售員 跑20城市 每個城市彼此連接 他要跑完 每個都只跑一次 繞回原點 求最短路徑 這個計算量要算20! 全部路徑加起來比較 就算一秒跑一百萬次 應該也要幾千年 但有辦法驗證你的路徑是不是最短 不用太長時間 指數時間 是否可透過某些CLEVER方法簡化到多項式時間?
頗有趣 而且很難 銷售員問題是個NPC問題 意思是如果誰可以證明銷售員問題是個P 那就P=NP!! 所有NP問題都可以用P解 世界是很美好的 在多項式時間可以解出 不過我猜應該不是這樣 想到近年很紅 量子電腦 只要三千個位元 就是可以超過 地球上所有電腦的總和 但目前量子電腦只能-273K運行 而且只能16位元 XD 假設量子電腦問世 銷售員問題應該只要一秒而已
千禧年的數學難題 光是敘述和看他們的介紹就可以學到許多有趣DER 統計 我到現在 大概可以敘述內中四個題目(共七個)了
No comments:
Post a Comment