Как рассчитать минимальное ожидаемое время для поиска на графике?

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.Это, мой друг, имеет такой же смысл, как и шимпанзе в пачке.