推 FRAXIS:Travelling Salesman Problem明明就可以解 這題目在問啥 06/22 07:15
→ FRAXIS:3的話 增加一個sencondary key value就可以了 06/22 07:17
→ HiltonCool:樓上的方法也是一個好方法！ 06/22 19:25
※ 引述《APE36 (PT鄉民)》之銘言：
: 1.
: 敘述並說明你的理由，旅行推銷員問題（Travelling Salesman Problem，）
: 是一個NP-complete 問題，而且至今尚未找到演算法可以解出此問題。
Ans：因為還沒唸阿狗，所以此題無解XD
: 2.
: 證明每一棵二元樹可由它的前序和中序順序來決定其唯一的結果。
Ans：(1)利用數學歸納法對點數做歸納
當點數=0時，前序與中序皆為空
∴可唯一決定此二元樹為空樹
∴初值成立
(2)令點數≦(n-1)時，此定理成立
(3)當點數=n時，從前序順序中找出第1個點，令此點為D，則此點必為樹根
再從中序順序中找出D之位置，令D左邊的子字串為TL*，D右邊的子字串為TR*
則TL*與TR*必為左、右子樹的中序順序 (中序：【 TL* 】D【 TR* 】)
令TL*長度為NL，TR*長度為NR，則NL與NR分別代表左、右子樹的點數
再回到前序順序中，從第2個點開始，取出NL長度的子字串，令為TL'
後面接著剩餘NR長度的子字串，令為TR'
則TL'與TR'分別代表左、右子樹的前序順序 (前序：D【 TL'】【 TR'】)
＼NL／ ＼NR／
∵NL與NR均≦(n-1)
∴由(2)之假設知：
給予TL*與TL'可決定唯一的左子樹
給予TR*與TR'可決定唯一的右子樹
∴左、右子樹皆唯一
∴整顆二元樹唯一
因此，由(1)(2)(3)及數學歸納法得證
[補充](1)給予前序(後序)與中序可決定唯一的二元樹
(2)給予前序與後序無法決定唯一的二元樹
: 3.heap sort 如何變成穩定的排序呢?
: (關於這個小題，有什麼思考的方向呢??)
Ans：若給予的資料值皆相異，則Heap Sort會變成穩定排序
(因為是否為穩定排序主要是決定於是否有相同的資料(即是否有不必要的swap)
若給予的資料值皆相異，則所有排序方法皆為穩定排序
若給予的資料值存在至少兩筆相同，則是否為穩定排序同原排序方法的定義)
-----------------------------------------------------------------------------
以上解答如有錯誤之處再麻煩大家批評指教，小弟是明年的考生
在此版獲益良多，首次PO文幫助有問題的同學，很怕有地方解錯
希望能與版友互相切磋，增進彼此的實力，感謝大家！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.183.98
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1403373124.A.E57.html