國家集訓隊2008論文集淺談隨機化思想在幾何-資料下載頁
2025-05-02 00:18本頁面
【正文】 果，作為問題的近似解的過程。 模擬退火算法的原理 ? 模擬退火算法是一種元啟發(fā)式（ MetaHeuristics）算法，來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時，固體內部粒子隨溫升變?yōu)闊o序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態(tài)，最后在常溫時達到基態(tài)，內能減為最小。根據(jù)Metropolis準則，粒子在溫度 T時趨于平衡的概率為 ? ，其中 E為溫度 T時的內能， ΔE為其改變量， k為Boltzmann常數(shù)。 Tte??元啟發(fā)式算法 ? 元啟發(fā)式算法（ MetaHeuristics）是一種啟發(fā)式策略，意思就是指導啟發(fā)式算法進行工作的方法。常見的元啟發(fā)式算法有： ? 模擬退火算法 ? 遺傳算法 ? 蟻群算法 ? PSO(粒子群優(yōu)化 ) 精確度分析的一個例子 ? 最優(yōu)解附近（如點 A， B）的點非常稀少且距離很遠，因此有候選解在它周圍（所在的 Delaunay三角剖分區(qū)域內）的概率是很大的。而且此時的距離比較大，我們對方向進行多次嘗試，因此調整出去的概率也很小。 精確度分析的一個例子 ? 如圖，假設一次隨機調整成功的概率為 P，則 精確度分析的一個例子 ? 若我們的 L取 30 ? ?………… (d=0,g=0) ? ??取到 最小值 。 ? 1） 因為此時兩者垂直，因此對于答案的影響很小。 ? 2） 我們使用了放縮過程，把 g、 d都當成 0計算，因此實際的調整概率還要更高。 精確度分析的一個例子 ? 但是如果題目的精度要求非常高，怎么辦呢？既然很難隨機到向量和 Voronoi邊平行，我們可以直接枚舉平行于 Voronoi邊的向量，雖然在時間上付出一點代價，但是在調整成功的概率和解的精度無疑將大大提高。當然對于普通的題目（本節(jié)三道例題 Run Away、 Empire Strikes Back、激光坦克），普通的隨機調整就可以了。 URAL1520： Empire Strikes Back 激光坦克 激光坦克 Testcase k N M 6 0 202100 0 2 1 2 50 3 1 2 1000 7 1 10000 3 5 2 3 30 8 2 3 70 1 3 4 4 4 3 2 35 9 3 18 30 10 5 25 100 可以使用隨機化思想的幾何題目 ? 1 Expensive Drink ? 2 最小外接圓 /球 ? 3 Run Away ? 4 Empire strikes back ? 5 激光坦克 ? 6 A star not a tree? ? 7 Mammoth Hunt ? TopCoder Marathon中數(shù)道幾何題目 隨機增量算法 模擬退火算法 調整法
環(huán)評公示相關推薦
鄂ICP備17016276號-1