4貪心算法與最優(yōu)策略-資料下載頁(yè)
2025-02-07 01:53本頁(yè)面
【正文】 借助于 擬陣 ，可以用 帶權(quán)擬陣的貪心算法 有效求解。 對(duì)于一個(gè)給定的 S的時(shí)間表，在截止時(shí)間之前完成的任務(wù)稱(chēng)為 及時(shí)任務(wù) ，在截止時(shí)間之后完成的任務(wù)稱(chēng)為 誤時(shí)任務(wù) 。 S的任一時(shí)間表可以調(diào)整成 及時(shí)優(yōu)先形式 ，即其中所有及時(shí)任務(wù)先于誤時(shí)任務(wù)，而不影響原時(shí)間表中各任務(wù)的及時(shí)或誤時(shí)性質(zhì)。 類(lèi)似地，還可將 S的任一時(shí)間表調(diào)整成為 規(guī)范形式 ，其中及時(shí)任務(wù)先于誤時(shí)任務(wù)，且及時(shí)任務(wù)依其截止時(shí)間的非減序排列。 53 貪心算法的理論基礎(chǔ) 首先可將時(shí)間表調(diào)整為及時(shí)優(yōu)先形式，然后再進(jìn)一步調(diào)整及時(shí)任務(wù)的次序。 任務(wù)時(shí)間表問(wèn)題 等價(jià)于 確定最優(yōu)時(shí)間表中 及時(shí)任務(wù)子集 A的問(wèn)題。一旦確定了及時(shí)任務(wù)子集 A，將 A中各任務(wù)依其截止時(shí)間的非減序列出，然后再以任意次序列出誤時(shí)任務(wù)，即 SA中各任務(wù)，由此產(chǎn)生 S的一個(gè)規(guī)范的最優(yōu)時(shí)間表。 對(duì)時(shí)間 t=1,2,?,n ， 設(shè) (A)是任務(wù)子集 A中所有截止時(shí)間是 t或更早的任務(wù)數(shù)?？疾烊蝿?wù)子集 A的獨(dú)立性。 tN54 貪心算法的理論基礎(chǔ) 引理 ： 對(duì)于 S的任一任務(wù)子集 A，下面的各命題是等價(jià)的。 (1) 任務(wù)子集 A是獨(dú)立子集。 (2) 對(duì)于 t=1,2,?,n ， (A)≤t 。 (3) 若 A中任務(wù)依其截止時(shí)間非減序排列，則 A中所有任務(wù)都是及時(shí)的。 任務(wù)時(shí)間表問(wèn)題 要求使總誤時(shí)懲罰達(dá)到最小，這等價(jià)于使任務(wù)時(shí)間表中的及時(shí)任務(wù)的懲罰值之和達(dá)到最大。下面的 定理 表明可用帶權(quán)擬陣的貪心算法解任務(wù)時(shí)間表問(wèn)題。 tN55 貪心算法的理論基礎(chǔ) 定理 ： 設(shè) S是帶有截止時(shí)間的單位時(shí)間任務(wù)集， I是 S的所有獨(dú)立任務(wù)子集構(gòu)成的集合。則有序?qū)?(S,I)是擬陣。 由 定理 ，用帶權(quán)擬陣的貪心算法可以求得最大權(quán) (懲罰 )獨(dú)立任務(wù)子集 A，以 A作為最優(yōu)時(shí)間表中的及時(shí)任務(wù)子集，容易構(gòu)造最優(yōu)時(shí)間表。 任務(wù)時(shí)間表問(wèn)題的貪心算法的 計(jì)算時(shí)間復(fù)雜性是 。其中 f(n)是用于檢測(cè)任務(wù)子集 A的獨(dú)立性所需的時(shí)間。用引理 (2)容易設(shè)計(jì)一個(gè) 時(shí)間算法來(lái)檢測(cè)任務(wù)子集的獨(dú)立性。因此，整個(gè)算法的計(jì)算時(shí)間 為 。具體算法 greedyJob可描述如 P130。 )( 2nO )(nO ))(log( nnfnn ?56 貪心算法的理論基礎(chǔ) 用抽象數(shù)據(jù)類(lèi)型并查集 UnionFind可對(duì)上述算法作進(jìn)一步改進(jìn)。如果不計(jì)預(yù)處理的時(shí)間，改進(jìn)后的算法fasterJob所需的 計(jì)算時(shí)間 為 。 )log( * nnO57 靜夜四無(wú)鄰，荒居舊業(yè)貧。 , February 26, 2023 雨中黃葉樹(shù)，燈下白頭人。 01:37:5301:37:5301:372/26/2023 1:37:53 AM 1以我獨(dú)沈久，愧君相見(jiàn)頻。 :37:5301:37Feb2326Feb23 1故人江海別，幾度隔山川。 01:37:5301:37:5301:37Sunday, February 26, 2023 1乍見(jiàn)翻疑夢(mèng)，相悲各問(wèn)年。 :37:5301:37:53February 26, 2023 1他鄉(xiāng)生白發(fā)，舊國(guó)見(jiàn)青山。 2023年 2月 26日星期日 上午 1時(shí) 37分 53秒 01:37: 1比不了得就不比，得不到的就不要。 2023年 2月 上午 1時(shí) 37分 :37February 26, 2023 1行動(dòng)出成果，工作出財(cái)富。 2023年 2月 26日星期日 1時(shí) 37分 53秒 01:37:5326 February 2023 1做前，能夠環(huán)視四周；做時(shí)，你只能或者最好沿著以腳為起點(diǎn)的射線向前。 上午 1時(shí) 37分 53秒 上午 1時(shí) 37分 01:37: 沒(méi)有失敗，只有暫時(shí)停止成功！。 , February 26, 2023 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒(méi)有。 01:37:5301:37:5301:372/26/2023 1:37:53 AM 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 :37:5301:37Feb2326Feb23 1世間成事，不求其絕對(duì)圓滿，留一份不足，可得無(wú)限完美。 01:37:5301:37:5301:37Sunday, February 26, 2023 1不知香積寺，數(shù)里入云峰。 :37:5301:37:53February 26, 2023 1意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 2月 26日星期日 上午 1時(shí) 37分 53秒 01:37: 1楚塞三湘接，荊門(mén)九派通。 2023年 2月 上午 1時(shí) 37分 :37February 26, 2023 1少年十五二十時(shí)，步行奪得胡馬騎。 2023年 2月 26日星期日 1時(shí) 37分 53秒 01:37:5326 February 2023 1空山新雨后，天氣晚來(lái)秋。 上午 1時(shí) 37分 53秒 上午 1時(shí) 37分 01:37: 楊柳散和風(fēng)，青山澹吾慮。 , February 26, 2023 閱讀一切好書(shū)如同和過(guò)去最杰出的人談話。 01:37:5301:37:5301:372/26/2023 1:37:53 AM 1越是沒(méi)有本領(lǐng)的就越加自命不凡。 :37:5301:37Feb2326Feb23 1越是無(wú)能的人，越喜歡挑剔別人的錯(cuò)兒。 01:37:5301:37:5301:37Sunday, February 26, 2023 1知人者智，自知者明。勝人者有力，自勝者強(qiáng)。 :37:5301:37:53February 26, 2023 1意志堅(jiān)強(qiáng)的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 2月 26日星期日 上午 1時(shí) 37分 53秒 01:37: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過(guò)于提升自我。 2023年 2月 上午 1時(shí) 37分 :37February 26, 2023 1業(yè)余生活要有意義，不要越軌。 2023年 2月 26日星期日 1時(shí) 37分 53秒 01:37:5326 February 2023 1一個(gè)人即使已登上頂峰，也仍要自強(qiáng)不息。 上午 1時(shí) 37分 53秒 上午 1時(shí) 37分 01:37: MOMODA POWERPOINT Lorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感謝您的下載觀看 專(zhuān)家告訴
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1