集訓(xùn)隊作業(yè)helin冬令營airpig解題報告_第1頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、Airpig 解題【題目描述】略?！倦S機貪心法】這種近似題目，很容易讓人想到貪心法；而對于提交無疑是最鋒利的利刃。式的題目，隨機化因此的第一個思路定格在隨機+貪心上。首先可以建立一個豬和圈的對應(yīng)序列：(PPig, SStall)(P1,S1), (P2,S2), , (Pm, Sm)（這里 m 表示豬的數(shù)目）表示讓 Pi 進 Si。然后 再其次是 P3以此類推。開始貪心。貪心的過程中，優(yōu)先考慮 P1,然后 P2，每一步按 P1,P2,Pm 的順序考慮。如果某個 Pi 已經(jīng)在按照最短路徑往 Si 飛，那就不管它。這個豬被稱為最優(yōu)豬。否則的話，就要把這個豬往它的最短路徑方向吹（注意：吹的時候不能改

2、變之前最優(yōu)豬的方向！）；若有兩個方向可以吹，隨機選一個。選定之后退出即可。這一步就完成了，執(zhí)行該吹氣命令即可。如果這個豬的所有吹氣方向都被封死了（也就是說都會改變之前的最優(yōu)豬的方向），那么這個豬就不管了。這種豬叫劣質(zhì)豬。按照上面說的方法，如果所有的豬都找完了，還是找不到合適的吹氣方向，就取命令 X0。以上是每一步如何決定吹氣命令的方法。每次決定一個吹氣命令后，就執(zhí)行。直到某一頭豬進圈了，再重新確定一個新的序列(P1,S1), (P2,S2), , (Pm, Sm)（mpiglimit 時匹配；如果豬數(shù)piglimit 就隨機貪心。Estimate_match.dpr 實現(xiàn)了這個程序。通過對參數(shù)的適當修改（吹氣系數(shù)，piglimit,randomtimes），大多數(shù)數(shù)據(jù)都能夠得出比較優(yōu)的解（第 7 個點除外，第 7 個點還是用純隨機貪心得到的解比較好）。最后的解如下：【附錄】1、感謝對我在匹配算法上的指導(dǎo)。2、感謝周源對我在貪心算法上的指導(dǎo)。3、最后兩個點運行時間極慢，需要等待。實際上第 9 個點，因為太慢了，我采用了折衷的辦法，首先用隨機貪心讓一些豬進圈，然后再匹配（因為一些豬已經(jīng)進圈，這時候匹配就快一點）；匹配到剩下 piglimit 頭豬時，再隨機貪心。結(jié)果比要稍差一點。這個程序是 save_time.dpr。所以這個點12345678910最終 結(jié)果5223

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論