基本信息

---

下载

文档摘要

---

离散优化2021-2022学年期末考试

回忆：Rye,Evan

1.名词解释（每道10分，共40分）

l最短路问题

l最小生成树问题

l中国邮递员问题

l旅行售货商问题

2.求下图的最小生成树及其权重（15分）

3.请叙述贪婪算法的策略，并举出两个用贪婪算法求解的例子，其中至少

一个得到的是最优解（20分）

4.叙述现实生活中的一个离散优化问题，介绍本问题涉及的离散优化知识，

并举例进行求解（25分）

注：

离散优化是组合数学中心的史永堂老师今年第二年开的课，老师自己

编写的讲义还在待出版阶段，显然期末考试真的没有为难大家+1。

这门课的十一章内容分别为：离散优化简介，最小生成树问题，贪婪

算法与拟阵，最短路问题，最大流最小割，匹配，中国邮递员问题，染色，

随机算法与在线算法，计算复杂性理论，近似算法。

如果学过图论，离散优化的难度不会很大，而且会收效更多。

史老师人非常nice,非常非常用心，邀请很多校内外老师来授课。所学

内容和生活实际联系十分紧密，不会很难，但是真的很实用，开拓视野，

内容丰富，值得选修！