math - 概率分布

Question

我正在阅读这篇文章（http://www.ams.org/publicoutreach/feature-column/fc-2018-12），我很难理解其中的一部分：

“在这组路径上，我们引入了一个概率分布，其中每条路径的概率与某个正幂 n 的 l−ni 成正比”

这就是我的理解：给定一组具有 m 条路径的路径，每条路径 i 具有以下概率

path_{i} = l^(-n)_{i} ，从 1.....m

旁注：我不知道如何添加公式:)

非常感谢。

Answer 1

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

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

本文中这两个挑战的答案是使用一些非常基本的目标函数（距离）构建一些“足够好”的解决方案，以便人们可以使用其他一些考虑因素在它们之间做出决定。为了使其发挥作用，我们希望解决方案能够合理地接近最佳且合理地多才多艺。他们所做的是有效地使用“概率贪心算法”（我现在才编造这个术语，不确定是否有官方名称）。

这个想法是我们希望通过一次添加一条道路来构建每组最佳道路。在每一步的真正贪心算法中，我们将在连接一些新块的所有道路中添加最短的道路。不幸的是，这样我们只能得到一个解决方案，而且贪心算法在如此复杂的问题中通常效果不佳（有时您现在需要选择一条更长的道路才能通过在最后添加许多较短的道路来获胜）。所以他们做的是：

1. 为下一条道路生成一组潜在的好候选：为每个尚未连接的块生成一些最短的道路。

2. 从那组候选人中随机选择一条道路。但仍然很明显，并非每个候选人都是相同的，我们希望更喜欢较短的候选人（即更频繁地选择他们）。考虑到这一点，让我们为每条道路添加与其长度成反比的权重，然后取加权平均值。在实践中，他们使用权重Wi = Li^(-n)。n = 8这是一个很难选择较短路径的过滤器（如果道路长 20%，则被选中的可能性会降低 4 倍以上）。所以给定道路的概率是

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

添加道路后，您会遇到一个新的小问题，因此您可以再次重复所有步骤。