申論題

試卷：107年 - 107 一般警察特種考試_二等_刑事警察人員犯罪分析組：計算機概論（包括計算機結構、資料結構、程式設計）#69515
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：107年
排序：0

申論題資訊

試卷：107年 - 107 一般警察特種考試_二等_刑事警察人員犯罪分析組：計算機概論（包括計算機結構、資料結構、程式設計）#69515
科目：計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)
年份：107年
排序：0

題組內容

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

申論題內容

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

詳解 (共 1 筆)

詳解提供者：hchungw

不，Travelling Salesperson Problem（TSP）不屬於 polynomial-time solvable 類別。TSP 是一個著名的 NP-complete 問題，意味著目前沒有已知的多項式時間算法可以解決所有實例。對於 NP-complete 問題，我們可以在多項式時間內驗證一個解的正確性，但尚未找到一個能在多項式時間內解決所有情況的算法。因此，TSP 並不被認為是多項式時間可解的問題。