算法合集之淺談隨機(jī)化在信息學(xué)競賽中的應(yīng)用-閱讀頁
2024-10-31 20:33本頁面
【正文】 隨機(jī)化來縮小區(qū)域范圍 有沒有更好的方法呢 ？ 例題： Two sawmills(CEOI2021) ? 我們建立一個矩陣 P， P[X,Y]表示第一個鋸木場建立在 X， 第二個鋸木場建立在 Y時的總運(yùn)費(fèi) 例題： Two sawmills(CEOI2021) ? 一開始時，矩陣的邊長為 N ? 我們隨機(jī)尋找一定數(shù)量的點(diǎn)，計(jì)算出它們的值 例題： Two sawmills(CEOI2021) ? 選取值最小的點(diǎn) ? 以這個點(diǎn)為新矩陣的中心，以現(xiàn)在矩陣的邊長的固定比例長度作為新矩形的邊長 (如圖中取 3/4)，從原來的矩陣中取出一塊作為新矩陣的范圍 例題： Two sawmills(CEOI2021) ? 然后繼續(xù)在新矩陣中重復(fù)這樣的操作 ，直至新矩陣足夠小時 ， 我們即可枚舉新矩陣上的每一個點(diǎn) ， 取其中最小值作為答案 。此時的最優(yōu)方案如圖 2所示 例題：小 H的聚會 (NOI2021) ? 這是一道提交答案題，題目數(shù)據(jù)分為三種類型 ? 第一種類型包括第 13個數(shù)據(jù)，每個點(diǎn)的度限制均為 N1， 等同于沒有限制，直接用最小生成樹算法即可解決 ? 第二種類型包括第 46個數(shù)據(jù)，其中 N1個點(diǎn)的度限制為 N1， 只有一個點(diǎn)有度限制，可以使用最小度限制生成樹算法解決。 ? 我們可以采取隨機(jī)化算法結(jié)合不同算法解決這個題目。 方法一：基于 Kruskal的隨機(jī)化算法 例題：小 H的聚會 (NOI2021) ? 在每次得到這樣一棵較大的生成樹后，我們再隨機(jī)化選取一條不在生成樹上的邊，加入生成樹上得到一個圈 ? 再在這個圈上試圖刪除一條邊使得生成樹仍然滿足度限制并且結(jié)果更優(yōu) ? 如此重復(fù)多次，以得到不能再通過這種方法得到更優(yōu)解
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1