---
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。

## 第4題: 01背包問題
- 已知有六個物品，其價值和重量如下，背包重量限制為34。
- 仿照課本以tree search來解。
- 請將下圖中的框框中，填入其upper bound與lower bound

## 第5題: A* 解multi-stage shortest path problem
- 請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了。

## 第6題: Channel Routing Problem
- 請使用A* 解Channel Routing Problem。
- 本題將原本題目的net 7移除，只剩下7個nets，請找出最少track的安排方式。

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