algorithm - 如何计算搜索图形的最小预期时间？

Question

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

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

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

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

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

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

Answer 1

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

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

如果您想要比这更好的答案，则需要更多信息。

此外，您应该阐明“图中每个节点都有该项目存在的概率 n/100”的含义。这似乎表明如果我的图表中有 1 个节点，它有 1/100 的机会在我检查的节点上，但如果我有 100 个节点，我有 100/100 的机会。我的 friend ，这就像黑猩猩穿芭蕾舞短裙一样有意义。