資源描述：
《本科畢業(yè)論文--一種求解一維裝箱問題的近似算法的研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、武漢科技大學(xué)本科畢業(yè)論文摘要一維裝箱問題來源于人們的長(zhǎng)期以來的生產(chǎn)實(shí)踐，是一種組合優(yōu)化問題。給定有窮個(gè)物體，每個(gè)物體的重量是已知的正實(shí)數(shù)。給定足夠多個(gè)空箱子，問題是要在滿足兩個(gè)約束條件的前提下，將所有物體放到箱子中去，使得所用箱子的個(gè)數(shù)盡可能地少。兩個(gè)約束條件是：第一，每個(gè)物體均保持完整，恰好放到一個(gè)箱子中去。不能將物體分割成幾塊。第二，每個(gè)箱子中所放的物體的重量之和均不能超過一個(gè)相同的上限，這個(gè)上限是一個(gè)已知的正實(shí)數(shù)。一維裝箱問題具有很高的理論價(jià)值和實(shí)際價(jià)值。一方面，學(xué)者已經(jīng)證明一維裝箱問題是一個(gè)NP難度問題，因此一維裝箱問題具有很高的理論價(jià)值。另一方
2、面，一維裝箱問題出現(xiàn)在實(shí)際生產(chǎn)的一些領(lǐng)域，因此也具有很高的實(shí)際價(jià)值。迄今為止，國(guó)內(nèi)外學(xué)者提出了許多用來求解一維裝箱問題的嚴(yán)格算法和近似算法。一方面，嚴(yán)格的最優(yōu)算法所花時(shí)間太長(zhǎng)，實(shí)際部門無法忍受。另一方面，近似算法由于可能快速地生成最優(yōu)解或者接近最優(yōu)解而為實(shí)際生產(chǎn)部門所廣泛采用。人類把物體往容器中裝，已有幾千年以上的經(jīng)驗(yàn)。這些生活經(jīng)驗(yàn)可引導(dǎo)出高效率的算法。本文提出了一種擬人算法。算法由三個(gè)部分組成。第一部分是降序最佳適合算法，用于生成初始解。第二部分是鄰域搜索算法。給定一個(gè)解，用鄰域搜索算法可以通過迭代改進(jìn)這個(gè)解。本文的鄰域定義的思想來源于“天之道損有余而
3、補(bǔ)不足”。第三部分是跳坑策略。跳坑策略用于跳出局部最優(yōu)解，將搜索引向有希望的區(qū)域，從而提高算法的效率。跳坑策略的思想來源是“三十六計(jì)走為上”。本文的程序計(jì)算了一組共17個(gè)國(guó)際公認(rèn)的問題實(shí)例。這組問題實(shí)例分為兩類。第一類為8個(gè)問題實(shí)例，目前尚未確定其客觀最優(yōu)解。第二類為9個(gè)問題實(shí)例，目前已經(jīng)確定了其客觀最優(yōu)解。擬人算法對(duì)第一類問題實(shí)例中的6個(gè)問題實(shí)例找出了與當(dāng)前已知最好解質(zhì)量相同的解。擬人算法還證明了TEST0068這個(gè)問題實(shí)例的目前已知最好解正是客觀最優(yōu)解。擬人算法快速地找出了第二類問題實(shí)例中全部9個(gè)問題實(shí)例的客觀最優(yōu)解。計(jì)算結(jié)果表明，擬人算法是一種有效
4、的求解一維裝箱問題的近似算法。關(guān)鍵詞：NP難度；擬人；鄰域搜索；跳坑；裝箱IV武漢科技大學(xué)本科畢業(yè)論文AbstractTheonedimensionalbinpackingproblem,whichisafamouscombinatorialoptimizationproblem,comesfromlongtermpracticeofhumanbeing.Thedefinitionoftheonedimensionalbinpackingproblemdiscussedinthispaperisasfollowing.Givenitemsandenoug
5、hidenticalbins,theweightofeachitemisaknownpositiverealnumber.Thecapacitiesofallbinsareequal.Theproblemistopackallitemsintothebinswiththeobjectiveofminimizingthenumberofoccupiedbins,subjecttotwofollowingconstraints.(1)Eachitemispackedintoexactonebin.Eachitemcannotbedividedintoseve
6、ralpartsandputintodifferentbins.(2)Thesumofweightofallitemsofeachbincannotexceeditscapacity.Theonedimensionalbinpackingproblemisofbothhighlytheoreticalandpracticalvalues.Ononehand,theonedimensionalbinpackingproblemhasbeenprovedtobeNP-hard.Ontheotherhand,theonedimensionalbinpackin
7、gproblemappearsinsomerealworldfactories.Sofar,manyexactalgorithmsandapproximationalgorithmshavebeenproposedtosolvetheonedimensionalbinpackingproblem.Exactalgorithmsrequiretoomuchcomputingtimeandcannotbeacceptedbyworkers.Ontheotherhand,approximationalgorithmsarewidelyusedbyworkers
8、,sincetheymaygiveoptimalornearoptimalsol
