原谅我的智商 题目也看不懂 谁能解惑下

元气满满

解惑 看也看不懂

sh329000

路线上有费用，把所有相较更贵的路线去除。这是哪里的题目。

元气满满

sh329000 发表于 2018-4-15 10:18
路线上有费用，把所有相较更贵的路线去除。这是哪里的题目。

能做下吗 看看思路

Silverluna

每个城市只要两条路即可，除了a和f一条路即可，从最贵的开始看凡事有三条路的把最贵那条路去掉

乖墩檬乖

邮路问题
我记得好像有结论，但是似乎结论的证明并不完美

毛毛妈caca

a到I直线成本25。 但是从A-B-I成本20。所以砍掉成本25的

patrik

意思是，研究一个可以无脑操作的套路，所有这样的问题，都可以套路一下得到答案。比如，查看整个平面图像有几个三角形，几个四边形，几个五边形，如果是三角形，去掉最贵的一条边，如果是四边形，去掉最贵的两条边。如果是五边形，去掉最贵的三条边。如果去掉一条边会导致有些点，不再相连，就不去掉。

糊涂爸爸

可以用暴力解法

myshadow

无向图，最优路径

Manddy

这是计算机科学的经典问题——求解图的最小（各边的费用和最小）生成（包含原图全部顶点， 边全部来自原图的边）树（任意两个顶点之间都有路径可到达且无回路）。一个易于理解的算法：
step1. 初始状态：图G=原图的边集合。T=生成树的边集合，初始为空集
step2. 从图G中取出一条费用最小的边，如果该边不与T中现有的边构成回路（比如T中已经有了AB和BI，再将AI放入就构成ABI回路），则放入T中；如果构成回路，丢弃。
step3. 如果T中的边还没有包含原图所有顶点，回到step2；否则结束，生成树T就构造好了。

以本题为例：
首先费用最小的是BI=8，放入T，T={BI}，剩下边中费用最小的是BC=10，BC与T中各边不构成回路，可以放入，T={BC，BI}。剩下边中费用最小的是AB=12，与T中各边不构成回路，可以放入，T={BC，BI，AB}。剩下边中费用最小的是AI=25，但与T中的边AB和BI构成ABI回路，丢弃AI……以此类推

初始的种子

楼上都好牛

元气满满

满爸 发表于 2018-4-15 19:06
这是计算机科学的经典问题——求解图的最小（各边的费用和最小）生成（包含原图全部顶点， 边全部来自原图 ...

                                        .

元气满满

满爸 发表于 2018-4-15 19:06
这是计算机科学的经典问题——求解图的最小（各边的费用和最小）生成（包含原图全部顶点， 边全部来自原图 ...

所以按照方法最后一路舍弃，就是从左边的图（  舍弃的是 AI  BH CG DE  ）变成了 右边的图。所有城市都能相通了，没有回路。所以右边的图其实就是答案？题目只是叫我们思考左图变成右边图的方法是怎么得到的？为自己的智商捉急~~~

Manddy

zorrollt 发表于 2018-4-16 11:11
.

6年级不敢保证，试试吧。可以完全不提“最小生成树”的概念，直接说解题思路，其实是贪心算法。贪心算法思想简单粗暴，不管三七二十一，每一步都选当前的最优（每次都从没选过的边中取一条费用最小的）。但注意不要出现回路（回路意味着多余。比如AB和BI已经连接，那么ABI三点两两之间都可以到达，如果再引入AI就是多余，导致不必要的费用增加，与费用和最小的目标矛盾）。

Manddy

zorrollt 发表于 2018-4-16 11:29
所以按照方法最后一路舍弃，就是从左边的图（  舍弃的是 AI  BH CG DE  ）变成了 右边的图。所有城市都 ...

对的，其实这题不是让你给出某个具体图的解法，而是要你对这一类问题给出通用的算法。话说你这是哪来的题目啊，对6年级学生来说要求太高了

元气满满

满爸 发表于 2018-4-16 12:29
对的，其实这题不是让你给出某个具体图的解法，而是要你对这一类问题给出通用的算法。话说你这是哪来的 ...

今年朋友学校参加夏令营的闯关题，（通不过可能就没资格参加了吧）这年头真不容易，贪心法看懂额， 简单明了，谢谢~~~

神未曾应许

这是不是把环路变成支干路的做法，昨天xrs统筹规划中好像提过一题。