腦洞大開的神奇算法
生活中你有沒有遇到過類似這樣的問題呢？！
A,B,C,D,E代表五個客人，
1,2,3,4,5代表五個房間。
一個房間只能住一個人，
每個客人對房間的喜好如下圖
然後目前初步安排好的房間如下圖
那麼如何安排，才能滿足每個客人需要呢？
如果你一個個地試，也許可以找到最終的答案，但是肯定會比較慢。
數學上有一種算法就是針對這類問題的。
“Maximum Matching Algorithm”
具體步驟如下：
1.start with any (non-trival) initial matching.
2.search for an alternating path.
3.if an alternating path can be found, use it to create an improved matching by changing the status of the arcs. If an alternating path cannot be found, stop.
4.list the new matching, which consists of the result of applying the alternating path together with any unchanged elements of the initial matching.
5.if the matching is now complete, stop. Otherwise retune to step 2.
可能不是很懂吧，還是以具體例子幫助大家理解。
那我們就來實際操作一下吧！
1
從圖二給定的initial matching開始
（這個其實不是唯一的情況，其實有很多可能的initial matching）
2
從沒有配對的D開始配對
直到找到沒有安排客人的5號房間為止
所以得到的應該是一下的流程圖
D-3=C-1=B-4=E-5
是不是又開始有點迷惑不解了。。。
請看以下說明！
NOTE：
比如前面這個D-3=C是怎麼寫出來的呢？
首先D-3
“-”代表目前initial matching中D沒有通往3號房間的路，
但是在最原始的圖中D是可以選擇3號房間的，
而且D只有3號房間可以選
然後3=C
“=”代表目前initial matching中3號房間是安排給C住的
下面同理，C在initial matching沒有通往1號的房間，所以用“-”號，但是1號房間在initial matching中已經安排給了B。
以此類推，直到之前沒有安排好的5號房間，就可以停止了。
3
改變符號change status
即 “-”變成“=”，“=”變成“-”
之前的：D-3=C-1=B-4=E-5
改變符號以後的：D=3-C=1-B=4-E=5
4
Alternating path D-3=C-1=B-4=E-5
Change status D=3-C=1-B=4-E=5
Improved matching D=3 C=1 B=4 E=5 A=2
任務完美完成啦！
其實，還有很多複雜的情況，
以後有機會可以再給同學們說哈，
今天能看懂這個方法就很好啦！
如果沒看懂的，希望認真得再重讀一遍，
你會發現學會了一種很有意思的方法！
你可以試試看下面的題目
閱讀更多 MathsAlgorithm 的文章
