匈牙利算法举例,匈牙利算法优缺点

首页 > 教育 > 作者:YD1662024-05-15 18:43:06

图4-3

第3步 选择空匹配点Bob,建立第2条增广路径Bob-->Carol, 并进行置换,创建第2个匹配:红色标记Bob--->Carol。如图4-4所示。

匈牙利算法举例,匈牙利算法优缺点(9)

图4-4

第4步,选择空匹配点Christ,建立增广路径Christ--->Alice--->Al--->Beatrice

(增广路径满足:头部Christ、尾部Beatrice都是非匹配点, 中间Alice、Al都是匹配点;蓝色标记Christ--->Alice是非匹配边,红色标记Alice--->Al是匹配边,蓝色标记Al--->Beatrice是非匹配边)。如图4-5所示。

匈牙利算法举例,匈牙利算法优缺点(10)

图4-5

第5步,置换增广路径中的匹配边和非匹配边。建立新的匹配:Christ--->Alice--->Al--->Beatrice

(红色标记Christ--->Alice是匹配边,Alice--->Al是非匹配边,红色标记Al--->Beatrice是匹配边)。如图4-6所示。

匈牙利算法举例,匈牙利算法优缺点(11)

图4-6

第6步,选择空匹配点Dan,建立增广路径Dan--->Carol--->Bob--->Danielle

(增广路径满足:头部Dan、尾部Danielle都是非匹配点, 中间Carol、Bob都是匹配点;蓝色标记Dan--->Carol是非匹配边,红色标记Carol--->Bob是匹配边,蓝色标记Bob--->Danielle是非匹配边)。如图4-7所示。

匈牙利算法举例,匈牙利算法优缺点(12)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.