# [演算法 Day2]

# 本次的課程內容：重要的五大問題

解決問題簡單，定義問題困難

Stable matching

開頭：男生與女生各100名，並配對成男女朋友。

Input表格呈現出每個男女對於異性的排序。

**Perfect matching**: 數學上每個人都有配對到對象就是完美了

**Stability**: 但是如果有unstable matching，則原配對的組合就會很不穩定，容易分開。

符合前面條件容易，但是後面的條件難，要如何解決？

- Simple-But-Invalid: 不穩定的配對就會持續交換，但問題是可能會成為無限循環的迴圈。
- Status of each person:

>> free (unmarried) ~engaged（訂婚但可毀約）~married [**Shapley**]

實作 — Gale-Shapley Procedure

看起來很荒謬的問題，但是他應用在很多的地方，包含：大學放榜分發、醫師入院實習等等的問題。

**第一個問題：Interval Scheduling (nlogn greedy algorithm)**

**Given: **Set of jobs with start times and finish times

**Goal: **Find maximum cardinality subset of mutually **compatible jobs** (jobs don’t overlap)

**第二個問題：Weighted Interval Scheduling (nlogn dynamic programming algorithm)**

**Given: **Set of jobs with start times, finish times, and weights

**Goal: **Find maximum weight subset of mutually compatible jobs

**第三個問題：Bipartite Matching (n^k max-flow based algorithm)**

**Given: **Bipartite graph

**Goal:** Find maximum cardinality matching

**第四個問題：Independent Set (NP-complete)**

**Given:** Graph

**Goal: **Find maximum cardinality **independent set** (subset of nodes s.t. no two joined by an edge)

**第五個問題：Competitive Facility Location (PSPACE-complete)**

**Given:** Graph with weight on each node

**Game: **

• Two competing players alternate in selecting nodes

• Do not allow to select a node if any of its neighbors have been selected

**Goal: **Select a maximum weight subset of nodes

前三個問題是屬於較簡單的問題 (Efficiently solvable)，但是後面兩個問題屬於較困難的範疇 (Hard)。

**回到婚姻配對故事**

將問題簡化簡化成數學形式：

**Given: **

• M: n men

• W: n women

• M x W: Each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference

**Goal:**

• Marry the men and women off such that

• There are no two people of opposite sex who would both rather have each other than their current partners.

`1. initialize each person to be free`

2. **while** (some man m is free and hasn't proposed to every woman)**do**

3. *w* = highest ranked woman in *m's* list to whom *m* has not yet proposed

4. **if** (w is free) **then**

5. (*m,w*) become engaged

6. **else** **if** (w prefers m to her fiance *m'*) **then**

7. (*m,w*) become engaged

8. *m'* become free

9. return the set S of engaged pairs

1:23:20

原課程連結：Lec02 演算法 第一週課程(2/2)