问概率分布

EN

让我们从一个更高阶的想法开始:我们不能有效地找到问题的最佳解决方案，原因有两个：

1. 我们不能将所有现实生活中的考虑因素都编码到我们的目标函数中
2. 即使我们可以，这个问题在计算上也会非常困难。

本文对这两个挑战的答案是使用一些非常基本的目标函数(距离)构建一些“足够好”的解决方案，以便人们可以使用其他一些考虑因素在它们之间做出决定。为了让它工作，我们希望解决方案合理地接近最好的，并具有合理的通用性。他们所做的是有效地使用“概率greedy algorithm”(我现在才创造了这个术语，不确定是否有一个正式的名称)。

我们的想法是，我们希望通过一次添加一条道路来构建每一组最好的道路。在真正的贪婪算法中，在每一步，我们只添加连接一些新块的所有道路中的最短道路。不幸的是，通过这种方式，我们只能得到一种解决方案，而且贪婪算法在如此复杂的问题中往往效果不是很好(有时你需要现在选择一条更长的路，通过在结束时添加许多较短的路来获胜)。所以他们要做的是：

1. 为下一条道路生成一组潜在的很好的候选道路:对于每个尚未连接的区块，生成几条最短的道路。
2. 从这组候选道路中随机获得一条道路。但很明显，并不是每个候选人都是一样的，我们希望更喜欢较短的候选人(即更多地选择他们)。为了说明这一点，让我们向每条道路添加与其长度成反比的权重，然后取加权平均值。在实践中，他们对n = 8使用权重Wi = Li^(-n)。这是一个很难选择较短路径的过滤器(如果道路长20%，则被挑选的可能性是4+倍)。所以给定道路被选择的概率是

，

Pi = Wi/Sum(Wj) = Li^(-n)/Sum[Lj^(-n)]

当添加道路时，您有一个新的较小的问题，因此您可以再次重复所有步骤。