4秘書問題最優(yōu)解(已修改)
2025-09-01 19:03 本頁面
【正文】 第 1 頁 共 20 頁 秘書問題最優(yōu)解 要 ]經(jīng)典秘書問題是最優(yōu)停止理論中的一個著名例子，屬于一類序貫觀察選擇問題。其報酬函數(shù)僅與觀察項的秩相關(guān)，而與觀察項的實際值無關(guān)。現(xiàn)在一定假設(shè)條件下，將經(jīng)典秘書問題推廣，建立一個更有實際意義的模型。采用動態(tài)規(guī)劃的方法得到該類模型的選擇策略，為實際決策問題提供一種可供參考的方法。秘書問題是一類序貫觀察與選擇問題，描述了一種動態(tài)的信息搜索與決策過程。 [關(guān)鍵詞 ]秘書問題；簡易公式；最小概率 [前 言 ]已有解決秘書問題的方法，主要特征是以取樣選項中的最大值作為標(biāo)桿，其優(yōu)點是能保證贏的概率最大，其不足是很少考慮決策者的有限理性與啟發(fā)式偏見。提出了基于次大值標(biāo)桿策略的設(shè)想，通過理論求解以及仿真實驗的方法研究了該策略的特征與規(guī)律。結(jié)果發(fā)現(xiàn)：贏的概率隨著標(biāo)桿由最大值向次大值、第三大值等的變化而逐漸降低，且最優(yōu)截止閥值也不斷后移。 一、假設(shè)與最優(yōu)停止規(guī)則 [1]： 假設(shè)下列條件成立（只要左方構(gòu)成條件的事件的概率大于零） 條件 b）的直觀意義是：如果已知第 n個到達的姑娘的相對名次 ，則在此時刻以前的信息下引理：若若（ 1）式成立則最優(yōu)停止規(guī)則是：其中 sn可以歸納地計算出來：，對于預(yù)測她的絕對 第 2 頁 共 20 頁 名次及拒聘與否，不起任何作用。根據(jù)如 （ 1）則 這里約定 ，對空的指標(biāo)集求和為零。所以最優(yōu)停止規(guī)則是。 二、秘書問題的兩個簡單公式 [2]： 我們知道秘書問題中有兩個簡易的計算公式。它是對 n 為有限情形的秘書問題給出兩個簡易計算公式。 情形 1：設(shè)經(jīng)理放過前 k個申請者不予考慮，從第 k+1 個開始選擇比前面都好的那位（如果有的話），記 ak={放過前 k位結(jié)果選到 1 號 } 因此，對于 n 個申請者的情形， ，使選到最差的那位概率最小。 情形 2。對于 n 個申請者由于經(jīng)理每次招見一批人，他可以在同一批中選擇最好的，如果最后一批的人數(shù)大于 1，經(jīng)理不可能招聘到 1 號申請者（最差的那位），因此我們只考慮最后一批人數(shù)為 1 的情形。 設(shè)這 n個人隨機地按 d批進見經(jīng)理，各批的人數(shù)分別為 n1，n2， ， nd， nd= ， 最小 .即經(jīng)理應(yīng)放掉第 1位，才能 1，記。假設(shè)經(jīng)理放過前k 批不予考慮，從第 k+1 批開始選擇比前面各批都好的那 位（如 第 3 頁 共 20 頁 果有的話）， ak={放過前 k 批最后結(jié)果選到 1號 }，則有 公式 2在上述條件下由此可計算的最優(yōu)值。 [3] 。 三、次大值標(biāo)桿策略的仿真實驗 解決秘書問題的關(guān)鍵，并非決定去選擇哪一個選項，而是決定何時停止取樣觀察選項，即何時停止搜索決策信息。但近些年研究發(fā)現(xiàn)，相比較最優(yōu)解策略，人們往往停止搜索得太早或者搜索量太少 [4]。這意味著決策者往往并沒有遵循最優(yōu)解策略去決策。下面我們做一個仿真實驗來解決秘書問題的滿意解。 實驗內(nèi)容是截止閥值與標(biāo)桿交叉組合的 截止閥法則。根據(jù)最優(yōu)解策略的閥值 37%以及現(xiàn)實生活中的經(jīng)驗值，我們測試了 7個截止閥值 r與 2個標(biāo)桿 m 的策略組合。它們分別是：截止閥值為選項集的 10%、 1/ 37%、 50%、 06 1 2/ 90%。標(biāo)桿為取樣選項集中的最大值（ m=1）與次大值（ m=2）。這樣，本研究一共實驗了 14（ 7x2）個組合策略。 首先，與已有研究 [4]類似，我們用數(shù)字的大小表示選項的優(yōu)劣程度，數(shù)字越大意味著選項越優(yōu)，否則越差。其次，采用序數(shù)集的隨機排列來模擬選項被隨機會見的情境。設(shè)選項集 n=100， 第 4 頁 共 20 頁 將 …… 、 100 共一百個序數(shù)隨機置亂作為測試集。在不同的截止閥值下，分別采用最大值與次大值標(biāo)桿進行選擇 。而截止閥值與標(biāo)桿的每種組合策略重復(fù)測試 100 次。然后計算即贏的次數(shù)（選中最大值 100的次數(shù)），實驗結(jié)果如表 1所示。 從表中可以看出。（ 1）當(dāng)采用最大值標(biāo)桿（ m=1）時，截止閥值 r 為 37%的組合策略贏的概率最大，即組合點（ r=37%， m=1）贏的概率為 35%。（ 2）當(dāng)采用次大值標(biāo)桿（ m=2）時，截止閥值 r為 50%的組合策略贏的概率最大。即組合點（ r=50%， m=2）贏的概率為 23%。（ 3）在最大化贏的概率的條件下，隨著標(biāo)桿由最大值（ m=1）向次大值（ m=2）的變化，截止閥值也由 r=37%向 r=50%變動。這說明標(biāo)桿不同，截止閥值也不同 。而且還有標(biāo)桿降低、截止閥值后移的趨勢。 另外，從表中還可以看出。在閥值 37%、最大值標(biāo)桿處，贏的概率達到最大（為 35%）。該值與理論計算的贏的概率1/e=37%[5]只差 2 個百分點，與
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1