演算法問題，一個人在1-100中任選一個數，另一個人來猜？

01-21

版本一：在1～100中等概率隨機抽一個數，每次猜告訴你大了還是小了還是猜中了。如果每次猜的成本是常數，（即要最小化猜的次數）問怎麼猜？
（直接答了，經典的二叉搜索。但這一問只是引子）
版本二：
依然是等概率隨機抽取。但每次猜的成本，正比於你猜的那個數，問這個時候要怎麼猜？

補充問題背景：一段一百行的代碼報錯。每次test須從第一行開始run。如果每次test用時一樣（或代碼很快，成本僅僅是run的次數），顯然還是二分法，先跑1到50行，然後根據報錯與否跑1-25或1-75，依次類推。但如果每run一次用時正比於代碼行數，此時如何調試以節約時間？求演算法。（與猜數略有不同在於只返回錯誤行大於或小於等於當前行，但大同小異）
版本3：
第三問純開腦洞想著玩：（從博弈論角度）假設甲並非等概率選取而是可以以某一策略任選數，在1，2兩種規則下，問甲乙各自策略是什麼（甲希望最大化乙的預期成本，乙希望最小化），有沒有均衡解，有多少
以上

問題重述

考慮從 $1, ldots, N$ 中隨機抽一個數 $X$ 。

記 $vec{p} = (p_1, ldots, p_N)^T$ 為抽數的概率質量分布，即 $P(X=k) = p_k$ 。

定義 $U_k(m, n; vec{p})$ 為：已知 $m le X le n$ 和 $vec{p}$ ，當前猜測 $X = k$ 增加的期望成本。

進一步定義 $U(m, n; vec{p})$ 為最優策略下的期望成本，即

$U(m, n; vec{p}) = underset{m le k le n}{min}, U_k(m, n; vec{p})$

其中

$U_k(m, n; vec{p}) = Cost(k) + frac{p_m + cdots + p_{k - 1}}{p_m + cdots + p_n} U(m, k - 1; vec{p}) + frac{p_{k + 1} + cdots + p_n}{p_m + cdots + p_n} U(k + 1, n; vec{p}), qquad m le k le n$

其中 $Cost(k)$ 為猜測 $X = k$ 這個行動的成本。對於問題一， $Cost(k)$ 為常數；而對於問題二， $Cost(k) propto k$ 。

邊界條件為

$U(m, n) = 0 quad extrm{for}quad m ge n$

演算法

如匿名用戶所說的打表計算：

先初始化一個大小為 $N imes N$ 的零矩陣，其中 $(m, n)$ 位置的元素用以表示 $U(m, n; vec{p})$ 。

然後從對角線開始，一層層地遞推計算，一直推到 $(1, N)$ 位置的元素 $U(1, N; vec{p})$ 即為所求。

在具體實現的過程中，可以順便用一個 $N imes N$ 的上三角矩陣 $A$ 存下對應的最佳猜測。

數值計算

對於問題二， $vec{p} = (1/N, ldots, 1 / N)^T$ ， $Cost(k) = k$

$U(1, 100; vec{p}) = 261.9$

對應的最佳策略下首次猜測的數是37。

有意思的是， $37/100 = 0.37 approx e^{-1}$ 。

（對於 $N = 200$ ，最佳首次猜測為75，而 $75/200 = 0.375$ ）

猜測：對於大 $N$ 的情形，從上述差分遞推式出發作微分方程近似，可以給出 $e^{-1}$ 的解。

嗯猜測不成立，見 @Helena 的答案。復現了她的結果如下（具體實現取計算結果中 $U$ 和 $A$ 的第一行即可）：

博弈問題

對於問題三，由於其是一個零和博弈的問題，其解為

$max_{vec{p}} min_{s} u_2(vec{p}, s)$

這裡 $u_2$ 為乙的收益函數， $s$ 為乙猜測的策略。

注意到乙猜測的策略可以由之前數值計算時提到的矩陣 $A$ 來表示，且由於之前動態規劃得到的是最佳策略，我們有

$u_2(vec{p}, s) ge u_2(vec{p}, A(vec{p})) = U(1, N; vec{p}), qquad forall s$

則上述博弈問題的解簡化為

$max_{vec{p}} U(1, N; vec{p})$

其中 $vec{p}$ 取值在標準simplex上。

在理論推導之前先暴力上個退火演算法的結果（ $Cost(k) = k$ ）：

左圖是 $U(1, N; vec{p})$ 的優化過程（最終值為338.88），右圖是最後結果的概率質量分布圖。

回答一下第二個問題。

典型的Discrete Stochastic Dynamic Programming, 用Markov決策過程框架求解即可。

本來懶得打字，看見樓上匿名用戶已經把Bellman optimality equation打出來了，就再補充幾句：

設我們要求區間 [m,n] 中的最優初始猜測, i.e. optimal policy f(m,n), 以及此最優策略下得到最終結果而要付出的獎勵函數之和的期望 c(m,n), 也就是value function.

定義：

狀態空間 S = { s = [g,h], [g,h] 包含於 [m,n] }

動作空間 A = { a(s)∈s }

狀態轉移概率矩陣 P: (p(s"|s,a)), s∈S, s"∈S, a∈A

獎勵函數 r(a,s) = k·a(s) (因為我們要最小化此處的獎勵函數之和，獎勵函數正比於此時的guess; k為給定常數，此處不妨設 k=1)

Discount factor γ= 1, 即我們考慮的是 E[total reward function]

那麼四元組{ S, A, P(·,·), r(·,·) } 構成了一個Markov決策過程(MDP)。我們要求的就是c(1,100),以及最優策略 f(m,n), 1&<=m&

假如可以證明 f(m,n) 是線性函數的話，難度會降低不少，我們可以直接待定係數求出；如果是一般情況要精確求解的話backward induction即可，其中要用到的Bellman equation樓上匿名用戶已經寫出來了，也很直白；如果複雜度太高就是各種強化學習近似演算法了。

//忙裡偷閒寫的答案，給昊神捧個場。如有錯誤請指正！

對於這個問題的目標，有兩個不同的interpretation，一個要用DP，一個不要用DP。

#### 用DP的情況 ####

考慮1-N的情況，如果N這個數字事實上不大，但是現實中N對應的每單位事情事實上很costly（例如只有100行程序但是每run一行需要十分鐘），這個時候目標就是就要另外單獨寫一個程序算具體的策略，但是不需要考慮這個算策略的方法的複雜度的問題。

寫了個程序，用樓下的DP公式把N在1500以內的情況算出來了：

對於大多數的N，最優起始查詢位置和N的關係畫出來是個分形函數 (＝＝)||| 瀑布汗。。。

該函數在N/3到N/2之間搖擺。

橫軸：問題規模Ｎ縱軸：最優起始查詢位置Ｋ

DP解出來的最優成本還是很低的，下圖這個線幾乎是O(N)了。事實上這個問題直接用二叉樹查找就已經有O(NlogN)了，DP給出一個近乎O(N)的解還是很正常的。

橫軸：問題規模Ｎ縱軸：最優期望成本

DP演算法本身的複雜度是O(N^3)，這增長也太大了，N稍微大一點就intractable了（我拿matlab跑N=2000都不太跑的出來）
（首先N*N的狀態格子，每一個格點內部要走n-m步迭代找最優子解法，這個加起來肯定N^3）

#### 不用DP的情況 ####

N如果大於2000，DP解就顯然太慢了。。。

考慮scalability的話，直接modify一下原本的二分演算法或者另立更簡單的演算法顯然比DP窮舉更合適。

直接從1出發一直試到N，期望複雜度是 $frac1Nsum_{i=1}^Nfrac{i(i+1)}{2}$ ，O(N^2)，比DP低。
從 $[N/2]$ 出發二分查找，期望複雜度是O(NlogN)
證法如下：從開始找到找到預期需要花的步驟數是 $log_2N$ （也就是搜索樹的高度），每一步的預期成本都是N/2（因為搜索樹是對稱的）所以總成本在O(NlogN)
從 $[N/3]$ 出發，每一步取左三分之一處的點。期望複雜度是O(NlogN)

這個也是一個搜索樹的結構，但是和樓上不一樣的是每一步的預期成本略低於N/2，總共花的步數略高於 $log_2N$ ，乘起來就不知道了。。（根據DP給出的結果，這個應該會比直接二分快一點）

這兩個到底哪個快也可以蒙特卡羅編程算出來的。然而懶得編了＝＝

Appendix: 算DP的Matlab函數：

N = 100;
c = zeros(N,N); %% cost function
k = zeros(N,N); %% optimal position
for i = 1:N
k(i,i) = i;
end
for n = 2:N
m = 1;

while n &<= N
min_cost = inf;
min_position = m;
for t = m:n
current_cost = t;
if t &> m
current_cost = current_cost + c(m,t-1)*(t-m)/(n-m+1);
end
if t &< n
current_cost = current_cost + c(t+1,n)*(n-t)/(n-m+1);
end
if current_cost &< min_cost
min_cost = current_cost;
min_position = t;
end
end
c(m,n) = min_cost;
k(m,n) = min_position;
n = n+1;
m = m+1;
end
end

第二問自己給一個答案，遞歸，存一個向量，表示如果搜索範圍是1-n，其預期成本是多少。然後一點點拉長這個向量。用這種方式找到最優演算法的時間複雜度是n方，因為每次向量長度加一，需時間正比於當前長度。

（但這是找到最優演算法的複雜度，不是最優演算法本身的預期成本）

期待大神們給出更直接的演算法。

--------------------

複雜度貌似不是n方，要維護的是一個矩陣，從k1到k2的子列，複雜度應該是三次方…… gg思密達

定義 c(m,n) 為：

有一個隨機整數 m&<=x&<=n。一個演算法不知道 x。對任意整數 y，演算法可以詢問 x 是否滿足 x&y，詢問的代價為 y。在最優策略下，演算法為了得知 x 所付出的期望代價是 c(m,n)。

當 m&>n 時，c(m,n) 已經沒有定義了。為了方便，當 m&>n 時，令 c(m,n)=0。

於是問題大抵就是問 c(1,100) 等於多少。

對簡單的情況，當 m&>n 時，c(m,n)=0；當 m=n 時，c(m,n)=0。

對稍複雜的情況，當 m&

$c(m,n) = min_{mleq lleq n} left(l + frac{l-m}{n-m+1} c(m,l-1) + frac{n-l}{n-m+1} c(l+1,n) ight)$

然後打個表算算吧。

已知 m&<=x&<=n 時，應該詢問那個元素？

如果 m=n，顯然不用詢問了。

如果 m&

幾周之後會取匿的

計算雙週期誤差的算術均值，或多周期時序加權均值，或方差平方差等各種差，並代入，求邊際。

持續調參，連續歸一。

以上是針對問題本身。

以下是深入問題背後，針對發問因子的主動追索結果所做出的主動答複。

實際運行針對不同情況，則又有不同。

金融資本市場，盤內數據，盤外事件，盤內時序，盤外人心……盤內行情，盤內基本面……任何被忽略的因素都可成為跳樓的核心驅動力。

我是野路子，非社會科學，非經濟學，非金融學，非金融工程或金融數學專業，且非自然科學下數學專業背景。（注意順序）

我用模式識別，具體是同位識別。

當我說出一種有效方法或實用工具時，針對亦步亦趨者的針對性戰術準備一定處於就緒狀態，戰備等級轉換實裝測試已結束。換句話說，若有針對我而來的襲擊，這是一個坑。

嗯，任何機器學習分類器，包括各種GAN，都是可以被欺騙的。這也是我的一貫認知，和實踐指南。即使FGSM（快步梯度），或其它針對性對抗、非針對性對抗、自感知、自適應、高魯棒……都可以。

至於在將大腦神經元構造，以形式化邏輯方式表達後能不能再欺騙……演算法或科技進步時，這一切的主導者——化學能驅動的碳基人形智能體，已先進步，也先適配。

so……

還是專研意音語素文字吧，保持相關的欺騙與欺騙性迴應腦區持續保持高激活，比歸一啦、分類啦……有趣多了。

最後，建議認真讀一讀這篇《物質世界中的對抗性實例》https://research.google.com/pubs/pub45471.html

怎麼就看見這個題目了呢。。。標準的區間動態規劃，一個演算法可以解決三個版本，調整cost function就行。

首先想狀態。這個問題里我們關心的信息是那個數在哪裡，而遊戲規則導致每一步我們對那個數在哪裡的知識可以用一個區間 $[l, r]$ 來表示：那個數肯定大於等於 $l$ 小於等於 $r$ 。每次操作都是在把這個區間逐漸縮小：挑一個 $i$ ，然後根據回答，我們能夠把區間縮小為 $[l, i-1], [i, i], [i+1, r]$ 中的一個。什麼時候結束？當區間的長度為1的時候。

我們要最優化的是（期望或者最壞）成本。用 $Cost[l, r]$ 表示給定那個數已經確認在 $[l, r]$ 中了，找到那個數的最小成本。由於可能的操作是在 $[l, r]$ 中選一個數 $i$ 來問，它與更小的區間的最優成本的關係應該是

$Cost[l, r] = min_{l le i le r}{c(i) + phi_{l, i, r}(Cost[l, i-1], Cost[i+1, l])}.$

其中 $c(i)$ 表示的是你選 $i$ 來問的成本是多少。在版本1中，這個恆等於 $1$ ，在另外兩個版本中 $c(i) = i$ 。 $phi_{l, i, r}$ 函數表示的是怎麼把兩個區間 $[l, i-1], [i+1, r]$ 的成本合起來（ $[i, i]$ 區間的成本恆等於 $0$ ，所以可以扔掉）。在版本一二當中，由於我們算的是期望成本，

$egin{align*} phi_{l, i, r}(Cost[l, i-1],Cost[i+1, r]) =\ P(X in [l, i-1] mid X in [l, r]) imes Cost[l, i-1] + \ P(X in [i+1, r] mid X in [l, r]) imes Cost[i+1, r] end{align*}$

其中 $P$ 給的是要找的變數（用 $X$ 表示）的概率分布（這裡就是 $[1, 100]$ 上的均勻分布）。所以真的是期望成本，不過要用條件概率，因為在狀態 $[l, r]$ 表示的是那個數已經在區間中了。

在版本三中，由於是最壞情況，你的對手一定會選那個成本較大的區間，所以 $phi_{l, i, r} = max$ 。說白了也就是經典的Minimax演算法。

這個遞歸怎麼算呢？ $Cost[l, r]$ 取決於那些長度比 $[l, r]$ 短的區間，而長度小於等於 $1$ 的區間就是邊界了，並且 $Cost$ 為 $0$ ，所以可以算，並且時間複雜度是 $n^3$ ：狀態兩方，轉移一方（枚舉提問的 $i$ ）。在很多情況下轉移的枚舉可以優化（比如利用 $min$ 後面整個關於 $i$ 函數的Convexity，可以二分斜率牛頓法什麼的），偶爾狀態也可以優化，比如有可能 $Cost[l, r]$ 其實只取決於 $[l, r]$ 的長度。算策略的話全部換成 $arg min, arg max$ 就完了。所以均衡是有的（其實是廢話，因為是有窮完美信息博弈，對面的actions是選擇回答大還是小）。