0

我有一个简单的绘图问题，我遍历一个图表来寻找一个项目。图中的每个节点都有一个项目存在的概率 n/100，其中所有概率的总和等于 1。如何找到在整个图中搜索项目的最小预期时间？

该项目保证仅存在于一个节点中。

乍一看，这似乎是一个旅行推销员问题，这很简单。只需获取路径的排列并计算每个路径并返回最小值。

但是当我需要找到最小的预期时间时，它变得很棘手。是否有任何数学公式可以插入到最小路径上以获得结果？

ie: sum = 0
    for node in path:
        sum += node.prob * node.weight

还是需要做一些更复杂的事情？

4

1 回答 1

2

如果您所做的只是查找特定项目，那么您最多可以保证进行 n 次查找。

如果该项目 100% 保证存在于图表中，并且仅存在一次，那么您将在大约 n/2 次搜索后找到它。所以（搜索一个节点的时间）* (n / 2) 是您的预期时间。

如果您想要一个更好的答案，您需要更多信息。

此外，您应该澄清“图中每个节点的概率为 n/100”的含义。这似乎表明我的图表中是否有 1 个节点，它有 1/100 的机会出现在我检查的节点上，但如果我有 100 个节点，我有 100/100 的机会。我的朋友，这就像穿着芭蕾舞短裙的黑猩猩一样有意义。

于 2011-02-24T19:34:56.883 回答