[理工] 資料結構思考問題

[APE36 (PT鄉民)]

1.
敘述並說明你的理由，旅行推銷員問題（Travelling Salesman Problem，）
是一個NP-complete 問題，而且至今尚未找到演算法可以解出此問題。

2.
證明每一棵二元樹可由它的前序和中序順序來決定其唯一的結果。

3.heap sort 如何變成穩定的排序呢?
(關於這個小題，有什麼思考的方向呢??)

thanks!!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.27.116.19
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1403282816.A.684.html
推 A4P8T6X9:2.可以用數學歸納法證明。
→ APE36:用中序   前序結果  可以證明??
推 A4P8T6X9:假設n-1之前都可以，從前序看出root之後再去中序分出左
→ A4P8T6X9:子跟右子，之後分別套歸納回來。
推 gocgle:第一題的題目根本出就錯了 TSP是NPC只是沒發現有效率的algo
→ gocgle:但是NPC仍舊可以解 只是不保證效率如何而已