---
tags: 演算法, 110-2
---
# 演算法作業 HW9
- 本週進入到第5章：Tree Searching，會介紹許多困難的問題轉化為樹搜尋。
- 本週觀念題都要畫圖(樹)，建議以手繪+拍照較省時，用軟體畫要花不少時間。
- 本週程式題與樹有關，可以發現DFS固定模式：使用遞廻左右分支。
# 觀念題 :book:
## 第1題: 最短路徑
- 請使用Branch-and-Bound找出下圖中，S到T的最短路徑。請畫出Branch-and-Bound圖，並標示各點的cost，以及被bound住的地方。(可參考ppt20頁)

## 第2題: Personnel Assignment Problem
- 已知5個工作(j1,...,j5)，其先後關係為：j1 :arrow_right: j3 , j3 :arrow_right: j4 , j2 :arrow_right: j5，分配給5個人員(p1,...,p5)
- 其cost matrix如下：
$\begin{bmatrix}
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{bmatrix}$
- 例如：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。

# 程式題: :computer:
- 主題：[Depth-First Search](https://leetcode.com/tag/depth-first-search/)
## 第4題: 左右反轉二元樹
- [Invert Binary Tree - LeetCode](https://leetcode.com/problems/invert-binary-tree/)
- 題目：給定一個二元樹，請建立一個左右反轉的二元樹
## 第5題:
- [Kth Smallest Element in a BST - LeetCode](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
- 題目：給定一個二元搜尋樹，請在其中找出第k小的節點。
## 第6題:
- [Deepest Leaves Sum - LeetCode](https://leetcode.com/problems/deepest-leaves-sum/description/)
- 題目：給定一個二元搜尋樹，求該樹最深的葉子之和。
## 第7題 : 心得
- 請在以下表單填寫對本週(hw9)影片教學和程式作業的問題/收穫/適應程度/心得。
- [https://forms.gle/3FqW22n3ViN98jbZ9](https://forms.gle/3FqW22n3ViN98jbZ9)