請(qǐng)教一道看似簡(jiǎn)單，卻不平凡的算法題！

A.com

沒(méi)法證明哪個(gè)較優(yōu)，缺少必要因子

peidright

可以證明的，等下我拿出證明

peidright

回復(fù) 11# A.com
沒(méi)證明出來(lái)，還要想想，好像確實(shí)如你所說(shuō)。 如果確定 n的范圍[0-N],但不確定具體的值，應(yīng)該有各種情況下，有跟N相關(guān)的平均最佳方法。
上面的證明貌似也有問(wèn)題，這個(gè)問(wèn)題跟N也比較密切。 假如上面的證明正確，為4N,假設(shè)4N步的時(shí)候，正好在端點(diǎn)。那么在N+1的情況下，
雖然只差一個(gè)點(diǎn)，也需要 多走2N步。 因此，那時(shí)候，則需要 6N步左右。

A.com

假設(shè)n是有限的人在x坐標(biāo)處，那么最優(yōu)的辦法是向某一方向走到頭（最大步數(shù)n-x或|x-n|），如果路上沒(méi)有門(mén)，則反向走到頭（最大步數(shù)n）。全程最大步數(shù)是2n-x或者是n+x。但是，現(xiàn)在n是無(wú)窮大，故以上方法中的n只能作為振蕩中的第一個(gè)周期的振幅m。至于后面每個(gè)周期振幅增加多少個(gè)m我們且不去管他。單單這個(gè)m就沒(méi)法證明取3比取4較優(yōu)或者是取4比取3較優(yōu)。因?yàn)闊o(wú)論m多大或多小，只有在結(jié)果確定，也就是門(mén)的位置確定以后你才能知道他m具體什么值才是最優(yōu)值（等于到門(mén)的步數(shù)）。現(xiàn)在因?yàn)槿鄙俦匾�的那個(gè)門(mén)的位置的因子，所以就證明不出m多大才最優(yōu)。

peidright

回復(fù) 14# A.com

界 應(yīng)該是 （3n, kn)，  實(shí)際上這個(gè)k應(yīng)該是趨近于3，也就是最小的k是達(dá)不到的。

cjaizss

找這么一個(gè)可導(dǎo)函數(shù),f(x),要求其n(n為所有自然數(shù))階導(dǎo)數(shù)越大越好.
然后第一次向左f(1)步,第二次向右f(2)步,第三次向左f(3)步.............
這樣的好處是,隨著n增大,其最壞系數(shù)越來(lái)越接近3(3是沒(méi)有辦法避免的)
比如我取f(x)=2^(x^2)

peidright

郁悶了，思維越來(lái)越遲鈍，13樓我的回復(fù)又錯(cuò)了。工作中把握不住思考，工作，學(xué)習(xí)的關(guān)系，真是悲哀。
覺(jué)得這里主要是這樣一個(gè)問(wèn)題迷惑了我。n的不確定。一但n確定，肯定明智的選擇是3N, 而一旦n不確定，實(shí)際最優(yōu)步長(zhǎng)是跟n相關(guān)的，這里N是個(gè)奇點(diǎn)。 類似于

y = (1/x)    x>0
    3N       x=0;
類似這種函數(shù)

bleem1998

如果墻不是無(wú)限延伸的
那最好的辦法應(yīng)該是向左走到頭然后向右走到頭
呵呵

xyfree

1. 你面對(duì)一堵左右無(wú)限延伸的墻；
2. 該墻有且只有1扇門(mén)，它在離你 n 步遠(yuǎn)的地方；
3. 你不知道 n 的大小，也不知道門(mén)在你左邊還是右邊；
4. 你一次能夠向左或者向右走一步，你只有走到門(mén)所在的位置才能出去。
請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)的算法，找到這扇門(mén)。
請(qǐng)問(wèn)在最壞情況下，你這個(gè)O(n)算法的常數(shù)系數(shù)最小是多少？也就是說(shuō)，在最壞情況下，你找到門(mén)需要走的步數(shù)
S <= K*n+C, K和C都是常數(shù)，求最小的K。
emacsnw 發(fā)表于 2006-01-18 03:41

假定墻的長(zhǎng)度為L(zhǎng) ，L 趨近于無(wú)窮時(shí)，墻在我的左邊和和在我右邊的概率是相等的。（這一步的證明過(guò)程忘了）
因此，一般情況下，每回合嘗試若干次并回歸出發(fā)點(diǎn)后，左右兩方相等步長(zhǎng)的區(qū)域內(nèi)的墻都已經(jīng)嘗試過(guò)的話，
都能夠把問(wèn)題的狀態(tài)歸納為出發(fā)前的狀況，算法可以繼續(xù)有效演算。


這個(gè)算法的時(shí)間復(fù)雜度對(duì)于總次數(shù)是O(n)的，證明過(guò)程如下:

設(shè)在第r回合嘗試中，根據(jù)不同的回合，嘗試向左或向右次數(shù)為t，有t(r)。
則該回合嘗試中所走的總次數(shù) s(r) = 2t(r) + 2t(r) = 4t(r) （向左走t次，然后向右走2t次，再向左走t次回到起點(diǎn)）

到門(mén)之前總的嘗試走的次數(shù)可以表示為 s(0) + s(1) + s(2) + ... + s(k)，記為 S
其中k必然小于等于n，因?yàn)榧词棺畋Ｊ氐牟呗�，t=r，在第r回合中也只需走n次即可找到門(mén)。
于是，總的次數(shù)可以表示為不定積分 S =∫s(r)dr = s(0) + s(1) + s(2) + ... + s(k)

對(duì)于固定的策略來(lái)說(shuō)，t(r) 是一個(gè) m次多項(xiàng)式，
即 t 對(duì) r 的函數(shù)必然可以表示為 t = k[0]× r^m + k[1]× r^(m-1) + ... +k[m] 的形式

不難求得
∫s(r)dr = 4(k[0]× r^(m-1) + k[1]× r^(m-2) + ... + k[m-1])r
            = t(k[0]× r^(m-1) + k1× r^(m-2) + ... + k[m-1])

因?yàn)檎业介T(mén)的時(shí)候，r是確定的常數(shù)，即(k[0]× r^(m-1) + k1× r^(m-2) + ... + k[m-1])是一個(gè)常數(shù)c
所以，找到門(mén)的時(shí)候嘗試的次數(shù) S(t) = ct

于是，算法的時(shí)間復(fù)雜度函數(shù)呈O(n) 形式。命題得證。



前面算法合理的前提是，墻無(wú)限長(zhǎng)，因此門(mén)在我左邊或者右邊的概率是相等的
并且因?yàn)樗惴ǖ拿恳徊絿L試，即針對(duì)不同步長(zhǎng)的嘗試失敗之后，我回到原來(lái)的位置，這時(shí)候不改變概率。


在某種策略下，在第r回合當(dāng)我嘗試往左邊和右邊各走t次的時(shí)候，我找到這個(gè)門(mén)的概率是 t/n。
因?yàn)閷?shí)際上門(mén)在未知方向的n步之外，但我在左右兩個(gè)方向上各只嘗試了t次。
把向某個(gè)方向走t次看做是一次獨(dú)立試驗(yàn)，如果門(mén)在這個(gè)方向上，那我走n步的時(shí)候必然發(fā)生目標(biāo)事件。
概率就等于樣本除以總量得到某一次嘗試就找到門(mén)的概率是t/n。

這樣在這種策略下，經(jīng)過(guò)若干回合嘗試，終于找到了門(mén)。
因?yàn)樵谧顗牡那闆r下最終必然找到了門(mén)，就可以表示為當(dāng)r和n都趨向于無(wú)窮大的時(shí)候，找到門(mén)的概率是1。

所以有以下極限
lim[ r->∞, n->∞] s(0)/n + ( s(1)-s(0) )/n + ( s(2)-s(1) )/n + ... + ( s(r)-s(r-1) )/n = 1
結(jié)果是 lim[ r->∞, n->∞] s(r)/n = 1。

------------------------- 下面證實(shí)是錯(cuò)的 ----------------- 悲劇了

因?yàn)?s(r) = 4t(r)
所以嘗試找門(mén)的策略應(yīng)該是 t=r，這樣可以滿足上面的式子
就是說(shuō)，改變每回合嘗試向某個(gè)方向走的次數(shù)時(shí)，都只比上一次增加1次，就是向左和向右各增加一次。

即有 k = 4, m = 1
由c = (k[0]× r^(m-1) + k1× r^(m-2) + ... + k[m-1]) 得 c = 4
因?yàn)?S(t) = ct，
所以 S = 4n

peidright

看不懂樓上的證明，證明O(n),舉一個(gè)O(n)的例子就行了