※ 引述《tren (窗外有藍天)》之銘言：
: 請教數學達人一個最佳化問題:
: 如果今天需要猜測一個未給定的二元狀態如(1, 1, 0, 1, 1).
: 每次猜測後, 會得知猜測解和正解的Hamming distance.
: 假設這個pattern是一個N維的向量, 因為在整個向量空間中共有2^N個狀態,
: 如果不重覆地循序亂猜, 最遭糕的情況(upper bound)共要猜2^N次.
: 然而, 因為向量空間中兩點最大的距離是N,
: 如果系統性地一次翻動一個位元, 如果距離變大就翻回來,最遭糕只要翻N次.
: 想要請問的是, 這已經是最佳的演算法了嗎? 如果不平行搜尋, 還有更快的方法嗎?
: 如果這是最佳演算法, 如何用理論證明它的最佳性(optimality)呢?
: 謝謝!
這個問題可以變成找偽幣問題，給n個金幣，其中每個金幣不是良幣就是偽幣
良幣重1，偽幣重0
給你一個電子秤，每次你可以放上全部或部份的金幣，秤會顯示總重
問至少需要秤幾次，才能找出所有偽幣
這個應該已經有蠻多文獻有結論
有一種手段是找原問題的子問題來證明
考慮這個子問題: 一開始你猜測完總是回答距離剩下1
c+log(n)的時間是upper bound也是lower bound(by adversary)
考慮另一個子問題: 一開始你猜測完總是回答距離剩下2
c+2log(n/2)的時間是upper bound但我不確定是不是lower bound
子問題推廣下去，有可能得到你想要的結論
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.57.12