申論題

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

申論題資訊

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

題組內容

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

申論題內容

⑴請問 travelling salesperson problem 是否屬於 NP-complete？（4 分）

詳解 (共 1 筆)

詳解提供者：hchungw

是的，Travelling Salesperson Problem（TSP）屬於 NP-complete 類別的問題。在計算機科學中，NP-complete 問題是一類特別的問題，它們既屬於 NP（Nondeterministic Polynomial time，非確定性多項式時間）類別，又滿足以下條件：任何 NP 中的問題都可以在多項式時間內歸約到它們。這意味著，如果我們找到了某個 NP-complete 問題的多項式時間算法，那麼理論上我們就能解決所有 NP 問題。

Travelling Salesperson Problem 要求找到一條最短的路徑，使得銷售員能夠訪問每個城市恰好一次並返回起點。這個問題是典型的 NP-complete 問題，因為雖然我們可以相對較容易地驗證一個給定的解決方案（路徑）是否為最短路徑（屬於 NP），但找到這樣的最短路徑的過程被認為沒有已知的多項式時間算法來解決。