演算法作業 HW9

• 本週進入到第5章：Tree Searching，會介紹許多困難的問題轉化為樹搜尋。
• 本週觀念題都要畫圖(樹)，建議以手繪+拍照較省時，用軟體畫要花不少時間。
• 本週程式題與樹有關，可以發現DFS固定模式：使用遞廻左右分支。

觀念題

第1題: 最短路徑

• 請使用Branch-and-Bound找出下圖中，S到T的最短路徑。請畫出Branch-and-Bound圖，並標示各點的cost，以及被bound住的地方。(可參考ppt20頁)
  

第2題: Personnel Assignment Problem

• 已知5個工作(j1,…,j5)，其先後關係為：j1 j3 , j3 j4 , j2 j5，分配給5個人員(p1,…,p5)
• 其cost matrix如下：
  $\left[\begin{array}{ccccc}17& 13& 4& 23& 12\\ 32& 30& 45& 19& 31\\ 7& 11& 12& 3& 15\\ 10& 17& 13& 9& 11\\ 8& 19& 9& 6& 7\end{array}\right]$
• 例如：p1作j1到j5的工資分別為17,13,4,23,12
• 每人分配一個工作，且當ja < jb ，須要 pa < pb。
• 請使用Branch-and-Bound找出最少費用的人員工作分配。

第3題: Traveling Salesperson Optimization Problem

• 在ppt34頁中，該例首先以4-6將所有feasible solution分為兩集合。
• 現在，將原例的4-6改以6-7來作區分，接著再以3-5作區分，如下圖所示：
  
• 請計算出圖中每個紅框的lower bound，並列出reduced matrix。

程式題:

• 主題：Depth-First Search

第4題: 左右反轉二元樹

• Invert Binary Tree - LeetCode
• 題目：給定一個二元樹，請建立一個左右反轉的二元樹

第5題:

• Kth Smallest Element in a BST - LeetCode
• 題目：給定一個二元搜尋樹，請在其中找出第k小的節點。

第6題:

• Deepest Leaves Sum - LeetCode
• 題目：給定一個二元搜尋樹，求該樹最深的葉子之和。

第7題 : 心得

• 請在以下表單填寫對本週(hw9)影片教學和程式作業的問題/收穫/適應程度/心得。
• https://forms.gle/3FqW22n3ViN98jbZ9