算法合集之淺談隨機(jī)化思想在幾何問題中的應(yīng)用(編輯修改稿)
2025-06-17 22:06 本頁面
【文章內(nèi)容簡介】 k次反射后擊中所有目標(biāo)的前提下，距離的最大值最小。 N=4 M=4 k=2 模擬退火算法的例子 激光坦克（ CTSC2021） N=4 M=4 k=2 本題是一個最大距離最小的問題，如果不考慮鏡子的因素，可以使用最遠(yuǎn)點(diǎn) Voronoi圖或前面的隨機(jī)增量算法來解決，但是鏡子的存在使得問題非常棘手。 模擬退火算法的例子 激光坦克（ CTSC2021） N=4 M=4 k=2 此時，模擬退火算法的可移植性的優(yōu)勢就體現(xiàn)了出來，我們可以在主算法的框架上，分別獨(dú)立編寫與鏡子不同次數(shù)相交的評價函數(shù)。 激光坦克的得分與代價 Testcase k 不處理反射 處理一次反射 處理兩次反射 6 0 10 10 10 2 1 10 10 10 3 1 0 10 10 7 1 1 10 10 5 2 10 10 10 8 2 6 10 10 1 3 9 10 10 4 3 10 10 10 9 3 0 0 10 10 5 0 0 0 總得分 56 80 90 代碼長度 90 160 240 300 總結(jié) ? 本文通過幾道例題，以及體現(xiàn)出的一種思想，希望能為大家打開一扇窗，在遇到幾何問題的時候多一種思路。當(dāng)然，隨機(jī)化思想的靈活運(yùn)用，是在對于經(jīng)典問題熟練掌握的前提下的，因?yàn)閯?chuàng)新永遠(yuǎn)建立在扎實(shí)的基礎(chǔ)之上。 Expensive Drink題目描述 zyx ???0有 3種物品的價格（設(shè)為 x, y, z）要滿足 n組約束 iiiii RzcybxaL ????且 求 的最大值 czbyax ??Expensive Drink c解 c解 c解 結(jié)論 1：如果存在解，必然存在于三個平面的交點(diǎn)上。 Expensive Drink 想法：枚舉兩個平面， 得到一條直線。 枚舉其余約束，切割該直線。 結(jié)論 1：如果存在解，必然存在于三個平面的交點(diǎn)上。 結(jié)論 1：如果存在解，必然存在于三個平面的交點(diǎn)上。 Expensive Drink 想法：枚舉兩個平面， 得到一條直線。 枚舉其余約束，切割該直線。 直到最后剩下一條線段。 引理 1 只有線段的兩個端點(diǎn)可能是的目標(biāo)函數(shù)的 最大值。 Expensive Drink 引理 2 不會有某三個平面的交點(diǎn)被遺漏。 結(jié)論 2：只有線段的兩個端點(diǎn)可能成為解。 Expensive Drink 引理 1 只有線段的兩個端點(diǎn)可能是的目標(biāo)函數(shù)的最大值。 Expensive Drink 引理 2 不會有某三個平面的交
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1