題組內容

四、我們有各式各樣的問題想使用電腦來解決。而問題依計算的複雜度可分類為 polynomial-time solvable、NP-complete、unsolvable 等類別。

⑵請問 travelling salesperson problem 是否屬於 polynomial-time solvable？（4 分）

詳解 (共 3 筆)

摩友(100006036608904)
摩友(100006036608904)
詳解 #3256001
2019/03/21
TSP 屬於 NP-Complete最壞...
(共 36 字，隱藏中）
前往觀看
hchungw
hchungw
詳解 #6045850
2024/03/14
不，Travelling Salesperson Problem（TSP）不屬於 polynomial-time solvable 類別。TSP 是一個著名的 NP-complete 問題，意味著目前沒有已知的多項式時間算法可以解決所有實例。對於 NP-complete 問題，我們可以在多項式時間內驗證一個解的正確性，但尚未找到一個能在多項式時間內解決所有情況的算法。因此，TSP 並不被認為是多項式時間可解的問題。
吾要考上中油
吾要考上中油
詳解 #3600326
2019/10/01
不知道
(共 5 字，隱藏中）
前往觀看