我正在阅读关于"贪婪"算法的教程,但我很难发现它们解决了真正的"顶级编码器"问题.
如果我知道某个问题可以通过"贪婪"算法解决,那么对解决方案进行编码就非常容易了.但是,如果我没有被告知这个问题是"贪婪的"我无法发现它.
使用"贪婪"算法解决问题的常见属性和模式是什么？我可以将它们减少到已知的"贪婪"问题之一(例如MST)吗？
Fra*_*ank 14
在形式上,你必须证明matroid属性.但是,我认为就topcoder而言,你更愿意快速找到问题是否可以贪婪地接近.
在这种情况下,最重要的一点是最佳的子结构属性.为此,您必须能够发现问题可以分解为子问题,并且他们的最优解决方案是整个问题的最佳解决方案的一部分.
当然,贪婪的问题种类繁多,几乎不可能为你的问题提供一般的正确答案.因此,我最好的建议就是沿着这些方向思考:
加上负载和经验(也不得不说),这应该可以帮助您快速发现贪婪的问题.当然,您最终可能会将问题归类为贪婪,而不是.在这种情况下,您只能希望在处理代码太长时间之前实现它.
(再次,作为参考,我假设一个topcoder上下文...对于任何更现实和实际的结果我强烈建议在选择贪婪算法之前实际验证拟阵结构.)
你的问题的一部分可能是由于思考"贪婪的问题"引起的.存在贪婪算法和问题,其中存在贪婪算法,这导致最佳解决方案.还有其他难题也可以通过贪心算法解决,但结果不一定是最优的.
例如,对于bin打包问题,有几种贪婪算法都比指数算法具有更好的复杂性,但是你只能确定与最优解相比,你会得到一个低于某个阈值的解决方案. .
只考虑贪婪算法将导致最佳解决方案的问题,我的猜测是归纳正确性证明感觉完全自然和容易.对于每一个贪婪的步骤,很明显这是最好的事情.
通常,最佳,贪婪解决方案的问题很容易,而其他问题会因为复杂性的限制而迫使您提出贪婪的启发式算法.通常一个有意义的减少将表明你的问题实际上至少是NP难度,因此你知道你必须找到一个启发式.对于那些问题,我是尝试的忠实粉丝.实现你的算法并尝试找出解决方案是否"相当不错"(理想情况下,如果你也有一个缓慢但正确的算法,你可以比较结果,否则你可能需要手动创建的基础事实).只有你有一些运作良好的东西,试着思考为什么,甚至可能尝试提出界限证明.也许它有效,也许你会发现它不起作用并需要改进的边界情况.