Re: [問題] sorting problem轉decision problem
看板Prob_Solve (計算數學 Problem Solving)作者hcsoso (索索)時間13年前 (2011/09/10 12:58)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《mqazz1 (無法顯示)》之銘言：
: 我在看NP-complete的時候
: 講義上說凡是NP-complete領域所討論的problem一定是以decision形式出現
: 然後他有問一個問題
: sorting problem: 將a1, a2, ..., an由小排到大
: 請問這種問題要怎麼把它轉成decision的形式?
: 謝謝
這題有不同可能的答案. (最近家教才教到, 提供一些想法!)
當然最直接的 "給定 input A[1..n], 請問是否 A[1] <= ... <= A[n]?" 是一個可能.
我覺得底下這個方法比較有趣:
考慮問題 SORT', 給定 input A[1..n], 求一 A 的重排 B[1..n]
使得 |A[n] - A[n-1]| + |A[n-1] - A[n-2]| + ... + |A[2] - A[1]| 最小.
不難證明 SORT' 跟 SORT 等價. 這個問題可以很輕易改成 decision 形式:
考慮問題 SORT(D), 給定 input A[1..n] 與常數 c, 是否存在 A 的重排 B[1..n]
使得 |A[n] - A[n-1]| + |A[n-1] - A[n-2]| + ... + |A[2] - A[1]| <= c ?
很類似 TSP 改成 TSP(D) 的方式!
--
Chicken's Finite Playground http://finiteplayground.wordpress.com/
Algorithms, Computational Complexity, Graph Theory, and Anything... FINITE!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.37.158
推
09/10 23:13, , 1F
09/10 23:13, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
