算法合集之淺談隨機(jī)化在信息學(xué)競賽中的應(yīng)用-文庫吧資料
2024-10-22 20:33本頁面
【正文】 ? 我們用 Kruskal算法計(jì)算出符合點(diǎn)的度限制的一棵生成樹 ? 由于有了度限制，所以這樣得出的生成樹不一定是最優(yōu)的 ? 我們可以在按邊權(quán)大小排序后，再隨機(jī)打亂部分邊的順序，再用 Kruskal算法，以求得到更優(yōu)的解。 例題：小 H的聚會 (NOI2021) ? 題目數(shù)據(jù)的第三種類型包括第 710個數(shù)據(jù)，數(shù)據(jù)中所有點(diǎn)都有度限制 ,沒有太好的準(zhǔn)確算法 ? 而這個題目又是不要求最優(yōu)解的開放性題目 ? 這種問題實(shí)在是隨機(jī)化算法自由翱翔的廣闊天空。 例題： Two sawmills(CEOI2021) ? 我們驚喜地發(fā)現(xiàn)，這種隨機(jī)化算法對于測試數(shù)據(jù)能夠全部通過！ 例題： Two sawmills(CEOI2021) ? 隨機(jī)化算法的靈活多變使得它的具有更為廣闊的運(yùn)用范圍 ? 而這樣的多變性也使得我們需要靈活恰當(dāng)?shù)剡\(yùn)用隨機(jī)化算法才能發(fā)揮出它的優(yōu)勢 ? 隨機(jī)化算法并不只是簡單地隨便亂來，使用隨機(jī)化算法的時候與其他算法一樣值得細(xì)細(xì)斟酌，需要匠心獨(dú)運(yùn) 通過這道題目可以看出： 下面 讓我們來看看隨機(jī)化算法 在實(shí)際比賽中的運(yùn)用解析 實(shí)戰(zhàn)解析 ? 題目大意是給出由 N個點(diǎn)、 M條邊組成的圖，求最大生成樹 ? 在圖 1所示例子中黑色邊組成的樹即為最優(yōu)方案 例題：小 H的聚會 (NOI2021) 例題：小 H的聚會 (NOI2021) ? 但是，為了減輕每個頂點(diǎn)的負(fù)擔(dān)，題目設(shè)定了每個頂點(diǎn)的最大連接邊數(shù) ki ? 還是用圖 1的例子，若我們?yōu)?1至 5每個點(diǎn)分別加上了 ki = 1, 1, 4, 2, 2的限制，則上述方案就不能滿足要求了。 ? 但是，這種算法對能力要求不小，不太容易想到。廣東省韶關(guān)市第一中學(xué)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1