[其他] 最佳化: 2元狀態搜尋
請教數學達人一個最佳化問題:
如果今天需要猜測一個未給定的二元狀態如(1, 1, 0, 1, 1).
每次猜測後, 會得知猜測解和正解的Hamming distance.
假設這個pattern是一個N維的向量, 因為在整個向量空間中共有2^N個狀態,
如果不重覆地循序亂猜, 最遭糕的情況(upper bound)共要猜2^N次.
然而, 因為向量空間中兩點最大的距離是N,
如果系統性地一次翻動一個位元, 如果距離變大就翻回來,最遭糕只要翻N次.
想要請問的是, 這已經是最佳的演算法了嗎? 如果不平行搜尋, 還有更快的方法嗎?
如果這是最佳演算法, 如何用理論證明它的最佳性(optimality)呢?
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.138.44.18
→
12/01 09:06, , 1F
12/01 09:06, 1F
推
12/01 09:09, , 2F
12/01 09:09, 2F
討論串 (同標題文章)