本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
贪心算法是一种在每一步都做出最佳选择以达到总体目标的算法。例如,如果目标是找到从 A 点到 B 点的最短路径,贪婪算法会在每一步选择最短的路径,而不考虑总路径长度。
贪心算法最著名的例子之一是旅行商问题。这个问题的目标是找到访问每个城市恰好一次并返回起点的最短路径。解决这个问题的一种天真的方法是尝试每条可能的路径并比较每条路径的长度。然而,这是非常低效的并且需要很长时间才能运行。
另一方面,贪心算法将执行以下步骤:
1.从起点开始。
2.找到最近的城市并访问它。
3.找到距离当前城市最近的未访问过的城市并访问。
4. 重复步骤 3,直到访问完所有城市。
5.回到起点。
上面的步骤总会找到一条路径,但它可能不是最短的路径。在某些情况下,可以使用贪心算法找到最优解。在其他情况下,它不是。
假设我们有以下城市和它们之间的距离:
City 1: 0km
City 2: 100km
City 3: 200km
City 4: 300km
City 5: 400km
如果我们使用上面描述的贪心算法,所采用的路径将是:
City 1 -> City 2 -> City 3 -> City 4 -> City 5 -> City 1
总距离为:
0 + 100 + 200 + 300 + 400 + 0 = 1000km
但是,最佳路径是:
City 1 -> City 5 -> City 4 -> City 3 -> City 2 -> City 1
总距离为:
0 + 400 + 300 + 200 + 100 + 0 = 1000km
如您所见,贪心算法并不总能找到最优解。但是,它通常比其他算法(例如蛮力方法)快得多,因此在实践中经常使用。
City 1: 0km
City 2: 10km
City 3: 15km
City 4: 20km
City 5: 25km
所走的路径和总距离是多少?这是最优路径吗?
City 1: 0km
City 2: 100km
City 3: 200km
City 4: 300km
City 5: 400km
所走的路径和总距离是多少?这是最优路径吗?
尝试其他的城市和距离集合,看看算法走的是什么路径。你能找到一个算法没有找到最优路径的集合吗?
尝试改进算法,让它总能找到最优路径。