技術(shù)參考貪心策略ppt課件-資料下載頁(yè)
2025-05-12 08:29本頁(yè)面
【正文】 展分為兩個(gè)階段：第一階段是 19891996年，這一時(shí)期奧賽題目的特點(diǎn)是：試題全部為 P類問(wèn)題，且只允許求最優(yōu)解，題目的設(shè)計(jì)強(qiáng)調(diào)對(duì)選手基本算法的掌握。第二階段為 1997年至今。在南非舉行的 IOI97中，命題方向一舉突破傳統(tǒng)模式， NPC類問(wèn)題在競(jìng)賽中大量出現(xiàn)，每道題目到具有一定的實(shí)際背景，引進(jìn)了嶄新的程序評(píng)測(cè)機(jī)制。在求解 P類問(wèn)題時(shí)允許得出較優(yōu)解并得到相應(yīng)的分?jǐn)?shù)。這些變化無(wú)疑更好地考察了選手的綜合素質(zhì)。在對(duì) P類較優(yōu)解問(wèn)題的求解過(guò)程中，貪心策略無(wú)疑扮演著重要角色。 IOI97中的障礙物探測(cè)器問(wèn)題便是運(yùn)用貪心策略來(lái)求得較優(yōu)解的 P類問(wèn)題。 [例 5] 障礙物探測(cè)器問(wèn)題 試題描述 有一個(gè)登陸艙（ POD），里面裝有許多障礙物探測(cè)車（ MEV），將在火星表面著陸，著陸后，探測(cè)車離開登陸艙向相距不遠(yuǎn)的先期到達(dá)的傳送器（ Transmitter）移動(dòng)。 MEV一邊移動(dòng)，采集巖石（ ROCK）標(biāo)本，巖石由第一個(gè)訪問(wèn)到它的 MEV所采集，每塊巖石只能被采集一次，但是這以后，其他MEV可以從該處通過(guò)。探測(cè)車 MEV不能通過(guò)有障礙的地面。 本題限定探測(cè)車 MEV只能沿著格子向南或向東從登陸處向傳送器 transmitter移動(dòng)，允許多個(gè)探測(cè)車MEV在同一時(shí)間占據(jù)同一位置。 警告： 如果某個(gè)探測(cè)車 MEV在到達(dá)傳送器以前不能在繼續(xù)合法前進(jìn)時(shí)，則車中的石塊必定不可挽回地全部丟失。 任務(wù)： 計(jì)算機(jī)探測(cè)車的每一步移動(dòng)，使其送到傳送器的巖石標(biāo)本的數(shù)量盡可能多。這兩項(xiàng)都做到會(huì)使你的得分最高。 輸入： 火星表面上登陸艙 POD和傳送器之間的位置用網(wǎng)格 P和 Q表示，登陸艙 POD的位置總是在（ 1，1）點(diǎn)，傳送器的位置總是在（ P， Q）點(diǎn)。 火星上的不同表面用三中不同的數(shù)字符號(hào)來(lái)表示： ● 0代表平坦無(wú)障礙 ● 1代表障礙 ● 2代表石塊 輸入文件的第一行為探測(cè)車的個(gè)數(shù)，第二行為 P的值，第三行為 Q的值。接下來(lái)的 Q行為一個(gè) Q P的矩陣。 輸出： 表示 MEV移向 transmitter的行動(dòng)序列。每行包含探測(cè)車號(hào)和一個(gè)數(shù)， 0或 1，這里 0表示向南移動(dòng)， 1表示向東移動(dòng)。 得分： 分?jǐn)?shù)的計(jì)算將根據(jù)收集的巖石樣本（取到傳送器上）的數(shù)目， MEV到達(dá)傳送器和不到達(dá)傳送器的數(shù)目有關(guān) ● 非法移動(dòng)將導(dǎo)致求解無(wú)效，并記作零分，當(dāng)MEV的障礙物上移動(dòng)或移出網(wǎng)格，即視為非法。 ● 得分 =（收集的樣品并取到傳送器上的數(shù)目+MEV到達(dá)傳送器上的數(shù)目 MEV沒(méi)有到達(dá)傳送器上的數(shù)目）與應(yīng)得的最大的數(shù)目之比（ %） ● 最高分為 100%，最低分為 0% 就到這里吧！
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1