用於在鐘形值列表中查找最大值的快速算法

我有一個值增加到最大值然後再減少值的列表（它是一個觀察到的高斯/鐘形分佈）。用於在鐘形值列表中查找最大值的快速算法

values = [0, 4, 5, 15, 30, 20, 10, 5, 0];

但分佈也可以轉移：

values = [0, 0, 0, 1, 2, 3, 8, 15, 30];

或類似的：

values = [30, 20, 5, 2, 1, 1, 0, 0, 0];

在一個特定的指標判定值是在這個特定的應用程序非常昂貴，所以它是使用盡可能少的數組查找很重要。

解決方案，如hill climbing或binary search的變種應該工作。什麼是儘可能少的步驟的算法？

很長的查找時間是由於真實世界的測量設備（時間以秒爲單位）。

來源

2016-11-19 Yeti

數組數據結構的用法很重要嗎？ – LmTinyToon

不是，它也可以是一個未知的函數'f（x）'，對於一個給定的'x'，測量一個值。這與'x'的輸入數組離散值和輸出數組的結果相似。你爲什麼要問？ – Yeti

我的想法是使用二叉搜索樹。這樣根總是最大的。它可以o優化最大搜索。 – LmTinyToon

您正在尋找三元搜索，可能與插值搜索一些啓發。

基本上，開始

def search(f, begin, end): 
    if end - begin <= 3: 
     return max(map(f, range(begin, end))) 
    low = (begin * 2 + end)/3 
    high = (begin + end * 2)/3 
    if f(low) > f(high): 
     return search(f, begin, high - 1) 
    else: 
     return search(f, low + 1, end)

漸近，這是你可以不依賴於你的價值的一些性質，做到最好。如果它不夠好，請更改表達式low和high以更好地匹配您的實際數據。

來源

2016-11-19 17:30:34 deniss

我使用了這種方法。其實，我給它一個參數'k'。也就是說，對於'k = 2'來說，它是二進制搜索，對於'k = 3'是三元搜索，對於'k'的較高值，它只是查看更多的值到'開始'和'結束'邊界。此外，對於近似測量，它也可以用來檢查'abs（f（low） - f（high））'是否小於某個值，如果是，那麼同時執行'low'和'high '作爲'begin'和'end'的值。畢竟，這對我來說並不是真的必要。 – Yeti

假設您沒有局部最大值（因爲它通常會發生在測量中），二進制查找是最快的方法。如果你有1000個數據點，那麼當最大值位於中間的某個位置時，最終會出現大約10次檢查。

爲了應對最大數據位於數據右側或左側的情況（如第二個和第三個示例中所示），只需檢查兩端中的任一端是否高於其連續點，如果確實如此，則最終以不超過兩次檢查結束搜索。

來源

2016-11-19 17:11:42 FDavidov

你的算法不能解決重複問題。如果您在46個相同元素的序列中間着陸，那麼您爲了在10次迭代中完成而將「中點」設置爲「什麼」？順便說一句，我的算法*不適用於最大值在任何一端。也許你誤解了如何。 –

正如FDavidov提到的，您應該使用二進制搜索的變體，因爲您只需在最差情況下訪問ceil[O(logn)]左右的索引。

二進制搜索變種的僞代碼如下所示：

left := 0 
right := n - 1 
while left < right do 
    mid := left + (right - left)/2 
    if values[mid] > values[mid + 1] 
     right := mid 
    else 
     left := mid 
end 

print left

然而，要找到非凸形曲線的最大值或最小值點，ternary search效果最好。但是，三元搜索會根據一些不適合整數的非整數評估函數來削減空間。

如果您不需要確切的結果並且近似值可以接受，那麼您也可以嘗試三元搜索。

來源

2016-11-19 17:24:14

您的算法僞代碼發佈爲'[0,1,0,0,0,0,0]'返回不正確的結果' –

用於在鐘形值列表中查找最大值的快速算法

回答

相關問題