旅行销售员-为什么不能保证贪婪的算法能提供最佳解决方案?

问题描述 投票:0回答:1

为什么没有贪婪算法可以保证为旅行商问题提供最佳解决方案?有一个例子吗?

optimization greedy
1个回答
0
投票

简短的答案是,旅行商问题不满足证明贪婪算法正确性所必需的属性。为了使贪心算法正确,它必须同时满足贪婪选择属性(算法中的第一选择始终可以处于最优解中)和最优子结构属性(问题的最优解包含最优解)每个子问题)。

虽然旅行推销员确实满足最佳子结构属性,但没有任何算法可以满足贪婪的选择属性。贪婪的算法要求丢弃每个子问题的其他可能解决方案,而旅行推销员实在太复杂了。

旅行商的一般算法是选择一个起点,生成所有(n-1)个!参观城市的排列,计算每个人的费用,然后返回最便宜的排列。该算法的运行时间为Θ(n!)。

旅行营业员问题的决策版本是NP完全问题(在此版本中,给定长度X,给定的城市列表的距离是否小于或等于X)。 NP是“非确定性多项式”的缩写,NP中的问题表示给定问题的答案,您可以验证证书在多项式时间内是否正确。 NP-Complete是NP中最难的问题,在多项式时间内无法解决NP-complete问题。

© www.soinside.com 2019 - 2024. All rights reserved.