
提出问题:寻找路径是一定要去“抢对象”么?是否应该先考虑无匹配的点?
尝试解答:正常思路是a1连b1,a2连b2,a3发现可用的b1b2都占用了,所以回溯
到了b2,b2向a2,a2向b3,此时a1b1没动,也可以像上图一样a3向b1,b1向a1
,a1向b2,b2向a2,a2向b3。但是无论哪种都没有解决“当有可用点和已匹配点同时
存在时选择哪个”的问题。
首先我们可知任意点在匹配上都是等价的,点的下标只是记号而已,b2只是个代号而已,你也可以叫b2我也可以叫b2,把这个代号拿掉之后呢?你又是谁?(是我杀了我回答正确动手吧)
回到正题,所以一个点先去匹配哪个点都是有意义的,没有一个先后。
所以在上图我们可以先让a1匹配b2,此时a2应该匹配的点有b2和b3,其中b2已占用,b3未占用,如果匹配b3,好了,那a3去匹配b1或者b2,选择b1,这就已经成为了图三,当然也可以让a4走一遍增广让a4配b3,a2配b2,a1或a3配b1。你会发现在第二步,我们让a2匹配的b2和b3
中选择了“没有对象”的那一个,最终我们得到的结果仍然没有问题。但是我们并没有证明哪一种是最优的。因此当存在已匹配点和未匹配点的时候,是否需要优先选择未匹配点?这样是不是可以让匹配过程少走几步?亦或者因为此时选择了未匹配点,导致后期其他点匹配的时候匹配到现在这个点,反而使他走了更多的路径?上述问题是否有一个严格的数学证明?