國(guó)家集訓(xùn)隊(duì)2008論文集淺談隨機(jī)化思想在幾何(已修改)
2025-05-18 00:18 本頁(yè)面
【正文】 廣東中山一中 顧研 感受隨機(jī)的美 —— 淺談隨機(jī)化思想在幾何問題中的應(yīng)用 引入 隨著信息學(xué)的發(fā)展，近幾年，各種各樣靈活的幾何題目層出不窮。因此隨機(jī)算法和隨機(jī)化思想便有了表演的舞臺(tái)。 隨機(jī)算法的特點(diǎn)是： 簡(jiǎn)單 、 快速 、 靈活 和易于并行化 ，這些特點(diǎn)都會(huì)在論文中得到體現(xiàn)。 概覽 數(shù)值概率算法 拉斯維加斯算法 蒙特卡羅算法 舍伍德算法 第一部分 隨機(jī)算法簡(jiǎn)介 第二部分 隨機(jī)增量算法 第三部分 模擬退火算法 隨機(jī)增量算法的一個(gè)例子 Expensive Drink ( Beijing Site, 2021 )（經(jīng)過抽象） czbyax ??11111 rzcybxal ????22222 rzcybxal ????nnnnn rzcybxal ????maximize . …… 單純形法、內(nèi)點(diǎn)法？ (n≤100) 隨機(jī)增量算法的一般步驟 發(fā)現(xiàn)問題的本質(zhì) 提出算法 改造成增量算法 加入隨機(jī) Expensive Drink c解 c解 c解 結(jié)論 1：如果存在解，必然存在于三個(gè)平面的交點(diǎn)上。 Expensive Drink 想法：枚舉兩個(gè)平面， 得到一條直線。 枚舉其余約束，切割該直線。 結(jié)論 1：如果存在解，必然存在于三個(gè)平面的交點(diǎn)上。 Expensive Drink 想法：枚舉兩個(gè)平面， 得到一條直線。 枚舉其余約束，切割該直線。 直到最后剩下一條線段。 結(jié)論 1：如果存在解，必然存在于三個(gè)平面的交點(diǎn)上。 Expensive Drink 直線數(shù)量 O(n2) 切割復(fù)雜度 O(n) 總復(fù)雜度 O(n3) 仍需要提高 結(jié)論 2：只有線段的兩個(gè)端點(diǎn)可能成為解。 結(jié)論 1：如果存在解，必然存在于三個(gè)平面的交點(diǎn)上。 Expensive Drink 癥結(jié)：沒有利用到之前已經(jīng)計(jì)算的結(jié)果 cv對(duì)癥：引入增量算法。依次加入半空間的時(shí)候，若原先的最優(yōu)解為 v，且滿足當(dāng)前的約束，就沒有必要枚舉平面上的直線了。 Expensive Drink c復(fù)雜度仍舊為O(n3) 對(duì)策：隨機(jī)插入半空間的順序 Expensive Drink c復(fù)雜度仍舊為O(n3) 對(duì)策：隨機(jī)插入半空間的順序 復(fù)雜度分析 取隨機(jī)變量 Xi，若滿足前 i1條約束的最優(yōu)解滿足第 i條約束，則 Xi=0，否則 Xi=1。 時(shí)間復(fù)雜度為 ? ?iniXiO ???12根據(jù)期望的線性率有 ? ? ? ? ? ?ininii XEiOXiOE
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1