貪心算法 活動(dòng)安排問(wèn)題.docx

《貪心算法 活動(dòng)安排問(wèn)題.docx》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、活動(dòng)安排問(wèn)題，對(duì)每項(xiàng)活動(dòng)的按照結(jié)束時(shí)間非減序排列。然后選第一個(gè)。按照第一個(gè)的結(jié)束時(shí)間來(lái)看接下去怎么選，以此類(lèi)推。貪心選擇性質(zhì)的證明：1.活動(dòng)安排問(wèn)題的一個(gè)最優(yōu)解是以貪心選擇開(kāi)始。即最優(yōu)解包含第一個(gè)活動(dòng)（叫做活動(dòng)1）。證明：假設(shè)有一個(gè)最優(yōu)解叫做A。它的活動(dòng)也是以結(jié)束時(shí)間的非減序進(jìn)行排列。假設(shè)A中第一個(gè)活動(dòng)叫做K。如果K是我們的活動(dòng)1，則A就是以活動(dòng)1開(kāi)始的。如果K不是活動(dòng)1.則把K從A中去掉，并加上活動(dòng)1，而且活動(dòng)1是相容的是因?yàn)榛顒?dòng)1的結(jié)束時(shí)間最早。所以證明了活動(dòng)安排問(wèn)題的一個(gè)最優(yōu)解是以貪心選擇開(kāi)始。最優(yōu)子結(jié)構(gòu)的證明：把起始時(shí)間大于活動(dòng)1的

2、結(jié)束時(shí)間的活動(dòng)去掉，A也可以把K去掉，這樣子有一個(gè)遞推的關(guān)系就是（總活動(dòng)中）接下去那個(gè)與活動(dòng)1相容的解必然可以相容在最優(yōu)解（A-K）里面。（因它又可以化為一個(gè)貪心選擇的開(kāi)始）所以每一步做出的貪心選擇將使得原問(wèn)題化為規(guī)模變小的相似的子問(wèn)題。