贪心算法的证明（拟阵）
贪心算法的证明（拟阵）
根据算法导论（引理16.8和16.9)：
--
16.8 令M={S,I)是一个拟阵。如果x是S中一个元素，而且是S的某个独立子集A的一个扩展，则x是ф的一个扩展。
16.9 令M={S,I)是一个拟阵。如果x是S中一个元素，而且它不是ф的一个扩展， 那么它也不是S的任何独立子集A的扩展。
--
可是我们根据拟阵的“遗传特性”，可以知道这样的x是不存在。那么这个引理的意义在哪？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论