如何計算搜索圖形的最短預期時間？

我有一個簡單的圖形問題，我遍歷圖尋找一個項目。圖中的每個節點的概率都是n/100，其中所有概率之和等於1.我怎樣才能找到在整個圖中搜索該項的最短期望時間？如何計算搜索圖形的最短預期時間？

該項目保證只存在於一個節點中。

乍一看，它似乎是一個旅遊銷售人員的問題，這很簡單。只需獲取路徑的排列並計算每條路徑的路徑並返回最小值。

但是，當我需要找到最短的預期時間時，它會變得棘手。是否有任何數學公式可以插入最小路徑來獲得結果？

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

還是有什麼更復雜的，需要做？

2011-02-24 TheOne

請不要用什麼_might_作爲可能的解決方案標記問題。此外，你錯過了細節。你究竟如何遍歷圖表？ – 2011-02-24 18:58:04

@Moron：你的意思是數學嗎？關於遍歷，我提到我得到所有路徑的排列並以最小的代價返回那個排列。 – TheOne 2011-02-24 19:01:30

我的意思是[旅行推銷員]。另外，我的觀點是，預期的時間取決於你如何穿過。你聲稱你正在尋找一個項目....如果你正在尋找所有的排列，爲什麼甚至談論一個圖表？你的問題並不清楚。 – 2011-02-24 19:04:45

如果你正在做的只是尋找一個特定的項目，那麼你保證至多是n查找。

如果該項目100％保證存在於圖表中，並且它將只存在一次，那麼在大約n/2次搜索後您會發現它。因此（搜索一個節點的時間）*（n/2）是您的預期時間。

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

此外，您應該說明「圖中的每個節點具有該項目的概率n/100」的含義。這似乎表明，如果我的圖中有1個節點，我檢查的節點上有1/100的機會，但如果我有100個節點，我有100/100的機會。那個，我的朋友，和穿黑色短裙的黑猩猩一樣有意義。

2011-02-24 19:34:56 corsiKa

是的，這是模糊的：所有可能性的總和等於1 – TheOne 2011-02-24 19:39:59

那麼你的預期時間將是'aw * n/2'，其中'aw'是節點的平均權重（假設權重和時間成比例）。平均來說，你將不得不搜索一半節點。 – corsiKa 2011-02-24 21:08:59

但是如果路徑包含死角，那麼你必須重新訪問一些已經命中的節點？在我看來，這是一個相當困難的問題，並且可能與最小TSP長度有關，正如OP所建議的那樣。 – Xodarap 2011-02-25 19:03:41

回答