[問題] 演算法: 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 08:44, , 1F
12/01 08:44, 1F
→
12/01 08:44, , 2F
12/01 08:44, 2F
→
12/01 08:45, , 3F
12/01 08:45, 3F
→
12/01 08:46, , 4F
12/01 08:46, 4F
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
