学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来.两台计算机被连接是指它们时间有数据线连接.由于计算机所处

学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来.两台计算机被连接是指它们时间有数据线连接.由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的.当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的.为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接.现在由你负责连接这些计算机,你的任务是使任意两台计算机都连通(不管是直接的或间接的).请写出模型求解算法的主要步骤.和说明采用了哪一部分的数学知识
一丝余温 2021-01-18 悬赏5金币 已收到1个回答

missyou

共回答了101个问题采纳率:86.4%

这是图论中典型的最小支撑树的问题,可以查看图论的相关知识,由于你没有给具体的数据,我在这里只简要地说明一下步骤:1.在任意两台计算机之间画一条线(计算机当然是用数字编号或其他符号代替).2.求出任意两台计算机之间相联的费用,作为这它们连线之间的权值.3.用最小支撑树算法(如:Kruskal算法)求出这n台计算机之间的最小支撑树.4.最小支撑树中的连线就是计算机之间连线的方式.
16
可能相似的问题
Copyright © 2018 - 2024 XGT8.CN - 西瓜解题吧
西瓜单词 | 建筑试题 | 会计师试题
闽ICP备14005894号-7