集訓(xùn)隊(duì)作業(yè)helin冬令營(yíng)airpig解題報(bào)告

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

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