凌晨 筒二节最小支撑树问题 实例 计算机中心欲使五家新用户与中心联机 电话公司负责排线,由于价格昂贵,要寻求最小支撑树 由于计算机网络的可联通性能,得到: 40 5 20 50 30 40 3 40 10 30 30 中 4 20 40 6
Ling Xueling 二、实例 计算机中心欲使五家新用户与中心联机 电话公司负责排线，由于价格昂贵，要寻求最小支撑树 由于计算机网络的可联通性能，得到： 第二节 最小支撑树问题 凌晨: 凌晨: 中心 1 2 3 4 5 6 2 0 4 0 5 0 4 0 3 0 4 0 1 0 3 0 3 0 2 0 4 0
凌晨: 筒二节最小支撑树问题 算法一( Greedy algorithm) 1、因为问题很特殊,就有:若每一步追求最优,最 后也能得到问题的最优的解法一一贪心解法 2、作法 )对弧的长短按照升序排序 2)任意结点开始,在保证不构成圈的前提下 3)重复进行:将最近的不联通结点并入网络的联通段(可以 双线表示联通) 3、说明:最小支撑树不唯一,但分枝总长度唯 4、例子的计算一一略。o.f=110
Ling Xueling 三、算法一 ( Greedy algorithm ) 1、因为问题很特殊，就有：若每一步追求最优，最 后也能得到问题的最优的解法－－贪心解法 2、作法 1) 对弧的长短按照升序排序 2)任意结点开始，在保证不构成圈的前提下 3) 重复进行：将最近的不联通结点并入网络的联通段（可以 双线表示联通） 3、说明：最小支撑树不唯一，但分枝总长度唯一 4、例子的计算－－略。o.f.=110。 第二节 最小支撑树问题 凌晨: 凌晨: