将最优装载问题的贪心算法推广到2艘船的情形，贪心算法仍能产生最优解吗？
1个回答
展开全部
贪心算法不能产生最优解。
两艘船的装载问题，是先装完第一艘，再装第二艘，所以就必须把第一艘尽可能的装满，才能使总的装载量更多。
对于一个具体问题，要确定它是否具有贪心选择的性质，必须证明每一步所作的贪心选择最终能得到问题的最优解，通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。
扩展资料：
两艘船的装载问题需要用的是回溯法，有了问题的解空间后，还需要将解空间有效地组织起来，使得回溯法能方便地搜索整个解空间，通常将解空间组织成树或图的形式。
如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处，并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
此外，贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。
参考资料来源：百度百科-贪心算法
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
云创
2023-07-25 广告
不同公司提供的服务不一样，价格也都不一样。如果想了解更多详细信息,可以咨询下北京磐安公司。北京磐安公司是一家专业从事高新软件的技术公司，公司致力于向企业客户提供一站式企业级软件采购、企业信息化基础架构、信息安全、数字化设计和信息技术教育培训...
点击进入详情页
本回答由云创提供
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
