约简算法-将任何SGI问题重塑为子集和
约简算法-将任何SGI问题重塑为子集和
提问于 2011-05-02 23:54:13
是否可以将任何子图同构问题转换为子集和问题，以便可以使用可用于解决子集和问题的动态编程技术来解决SGI问题？
回答 2
Stack Overflow用户
发布于 2011-05-03 02:38:19
是的，你可以这样做，但每一个已知的约简都会产生一个具有指数级大数字的子集和问题。
(顺便说一句，你的作业检测器坏了。)
Stack Overflow用户
发布于 2011-05-03 01:22:08
我看不出这是怎么做的。在子集求和问题的权重和图的结构之间没有立即明确的映射。这两个问题之间的唯一关系是图的子集和子集和问题中的集合的子集。子集和的伪多时间(动态编程)算法在一组数字和一个有界的和上操作-我严重怀疑是否有任何方法以这种格式编码图的结构。但是，考虑到这是一个家庭作业问题，我可能错了:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5859303
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号