[演算法 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)