2007/10/26

Adversary Argument

還是先懺悔:我去年幾乎沒做助教出的 voluntary exercises,只記得有次助教解答有附一份關於 adversary argument 的文件,但那時看沒什麼感覺 XD。

這次為了證明 "double-end problem"(說不定隨機客的一大樂趣就是為問題取名字?XD)的比較次數下界為 3n/2 苦思良久。昨晚十一點多想到說不定可以把它化成圖論問題(因為 "champion problem" 的比較次數下界用 graph connectedness 思考非常直覺),但沒看出什麼性質。接著從 decision tree model 慢慢磨出 adversary argument 的邏輯,但因為我是從圖論的脈絡過來,討論繁複,沒辦法找到足夠簡單的分析方式。後來上網一找發現 "adversary argument" 這詞,才知道是以前不認真,自食惡果 XD。

--
今年就趁機會把隨機客的演算法作業都想一遍吧。(其實是不得不想 ─ 也是自食惡果?XD)

Labels: