哪些算法类别可以用于解决这个问题？

Question

EDIT: 只是为了确保有人不会在问题上破头...我不是在寻找最优算法。任何有意义的启发式方法都可以。

我之前尝试过表达这个问题，但意识到自己做得不够好，所以我删除了那个问题。我又试着表述了一下我的问题。请随意提供任何有助于改进的建设性批评。

输入：

- N个人 - 我可以发布的k个公告 - 我的声音可以传播的距离（比如5米），即我可以根据这5米内的人数决定是否发布公告

目标：

- 最大化听到我发布的k个公告的人数，并（可选）最小化完成所有k个公告所需的时间

约束条件：

- 一旦一个人听到了我的公告，他就从总数中被移除，即使他听到了我的第二个公告，我也不会再计算他 - 我可以看到与我接近的同一组人

例如：

假设有10个人，编号从1到10，按以下顺序到达：

- 时间段1：1（收益=1） - 时间段2：2 3 4 5（收益=4） - 时间段3：5 6 7 8（如果之前没有在时间段2中发布公告，则收益为4；如果在时间段2中发布了公告，则为3） - 时间段4：9 10（收益=2）

我需要发布2个公告。如果我是一个神谕，我会选择时间段2和时间段3，因为这样7个人会听到我的公告（因为5已经在时间段2中听到了我的公告，我不再考虑他）。我正在寻找一种在线算法，可以帮助我决定是否发布公告，如果发布的话，则基于哪些因素。是否有人对解决这个问题或更简单版本的问题有什么想法？

- Legend

---

有趣的问题。我认为任何启发式方法都需要知道、估计或假设每个时间段内加入或离开的人员概率。你有这方面的任何信息吗？例如，如果你确切地知道所有人都会在一个时间段后离开，那么你的公告就会与你知道大多数人倾向于逗留几个时间段时不同。 - bdk

@bdk：实际上，你提出了一个重要的观点。我认为当有人进入我的接近范围时，我可以大概估计他们能在我的接近范围内停留多少时间段。但我对这两种方法都很感兴趣，如果只基于这个假设就能完成某些事情，那也可以。 - Legend

我认为这个链接对于一般类的问题看起来很有前途：http://en.wikipedia.org/wiki/Markov_decision_process。它似乎考虑了在特定状态（时间段）宣布所获得的价值，以及一种折扣未来潜在收益的方式，这些收益可能基于保留公告而发生或不发生。我将其发布为评论而不是答案，因为如果没有将您的问题映射到考虑有限公告的价值函数，这并不能真正帮助您，但我认为这可能是有价值的。 - bdk

@bdk：+1 感谢您在此事上花费的时间。我会开始阅读相关资料，看看能否将我的问题简化以利用这个概念。由于我没有太多经验，所以我会先寻找更简单的例子来理解它。 - Legend

你能分享一下你想要应用这个的真实世界应用场景吗？或者给出一些提示？ - Aaron Anodide

Answer 1

需要一种依靠最大流算法的方法。本质上，您正在尝试从起点->终点推送最大数量的消息。虽然它是多维的，但您可以拥有一个超级汇点，该点连接到t的每个值，然后将每个t值连接到此时可到达的人，然后再连接一个超级汇点。这样，您只需计算最大流量（加上不能超过k个喊叫的限制，这应该可以用一些动态规划来解决）。这是一种非常不干净的解决方案，但它应该能够以确定性的方式完成工作，而不使用启发式方法。

- Ben Stott

---

@Ben Stott：嗯...也许我没有完全理解这个问题，但是最大流不是假设我们已经有了一个图吗？在我的情况下，决策是在线的，可能需要构建每个层次的图...啊...我可能错了。您介意将其与我的问题联系起来或者可能提供一个小例子吗？ - Legend

“在线”是什么意思？是指只有在数据到达时才能获取数据，并且在此之前已经需要做出决策，还是其他情况？ 具体而言，你的算法是否必须针对每个t值解决问题，或者可以等待所有输入都完成后再进行处理？ - Ben Stott

@Ben Stott：哦，所以我使用“在线”这个词是指我需要在t时刻立即做出决定，否则我将永远无法再次做出决定，即如果我看到30个人并错过了机会，我可能再也见不到他们了，因此我需要在那个时候决定该怎么做。 - Legend

是的，这就是上述算法将要做的事情。只要你能等待所有输入到达后再进行计算，上述算法就应该可以工作。 具体来说，对于每个t，将节点t添加到您的第一层节点中，作为超级源的子节点。然后将每个时间t让您与之交谈的人添加到第二层中，作为t的子节点和超级汇点的父节点。然后，在您的输入列表结束时，您可以运行基本的最大流算法来回答您的问题。它仍然会考虑同时看到30个人的情况！ - Ben Stott

@Ben Stott- 我相信你对于最大流算法的要求，即“必须等到收到所有输入后才能进行任何计算”，在Legend的问题中并不适用。这就是他所说的“在线算法”的意思，例如，他需要在每个时间段做出前进/停止的决策，而不必等待看看未来时间段会发生什么。 - bdk

Answer 2

我不知道是否真的有一种方法来解决这个问题或者有一种算法可以按照你的方式来做。

看起来，你基本上是想用两个公告来达到最大人数。但是如果没有事先了解任何关于人群的信息，你就无法做出任何智能决策，无论是使用第一个公告还是不使用。至少第二个公告知道什么时候不使用（即如果该组没有新成员，则可以知道不值得浪费公告）。但它仍然基本上存在相同的问题。

唯一真正解决这个问题的方法是利用关于数据类型或期望结果的知识来进行猜测。如果你知道平均每组有100人，标准差为10，那么你可以拒绝在少于90人的情况下发布公告。或者，如果你知道你需要用两个公告达到至少100人，你可以选择从一开始就不要向少于50人的人发布公告。显然，这些方法会冒着永远不发布公告的风险，如果实际数据不符合你的预期，那么你可能永远不会发布公告。但无论你做什么，你都可能在第一组中得到1个人，然后在其余所有组中得到0个人。

或者，您可以尝试更清晰地定义问题，我很难理解如何将其与计算机相关联。

- SoapBox

---

+1 谢谢。根据你的建议，也许知道我的位置有多受欢迎会很好，如果我的位置不受欢迎，选择一个较低的数字来宣布是有道理的，以减少我无法吸引更多人的风险；但是在热门地区，我可以冒险等待更多的人。现在解释我评论中所有模糊术语可能会有些棘手，而且正如我在问题中提到的，我实际上正在构思问题本身，所以我可以进行一些调整以便解决问题。 - Legend

Answer 3

让我们从解决最简单的问题变体开始：假设有N个人和K个时间段，但只有一个可能的公告。同时假设每个人只会在一个时间段内停留，并且每个尚未出现的人在任何未来时间段都有同等可能的出现机会。

在这些简化条件下，每个时间段您都要查看当前时间段宣布的回报，并将其与未来时间段具有更高回报的机会进行比较。例如，假设有4个人和3个时间段：

时间段1：第1个人出现了，因此您知道宣布可以获得1的回报，但是您还有3个人要在剩余的2个时间段内出现，因此其中至少一个时间段保证有2个人，因此不要宣布。

在每个时间段，您可以通过将剩余的（N）人和（K）时间段视为从1..k中的每个N个独立随机数字来计算后续时间段比当前时间段具有更高回报的机会，并计算至少一个值k被命中超过或等于当前回报次数的机会。（类似于生日问题，但对于多个碰撞）然后，您需要根据预期方差决定折扣率。 （鸟在手等）

将此解决方案推广到原始问题留给读者作为练习。

- bdk