作者tren (窗外有蓝天)
看板Programming
标题[问题] 演算法: 2元状态搜寻
时间Thu Dec 1 02:00:37 2011
请教演算法达人一个最佳化问题:
如果今天需要猜测一个未给定的二元状态如(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
1F：→ Semisphere:也可一次翻动多个位元，用线性规划法可118.166.210.189 12/01 08:44
2F：→ Semisphere:保证每次算都一样，但也可以用随机搜寻118.166.210.189 12/01 08:44
3F：→ Semisphere:法，但就不保证每次结果都一样，但有可118.166.210.189 12/01 08:45
4F：→ Semisphere:能搜寻性能更佳118.166.210.189 12/01 08:46