脑洞大开的神奇算法
生活中你有没有遇到过类似这样的问题呢？！
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 的文章
