算法設(shè)計(jì)與分析課程設(shè)計(jì)--用貪心算法解決汽車加油次數(shù)最少問題(參考版)
2025-01-12 09:24本頁面
【正文】 不是每個(gè)問題用貪心算法都可以一定得到最優(yōu)解，除非該問題具有貪心選擇性質(zhì)（所求問題的整體最優(yōu)解可 以通過一系列局部最優(yōu)的選擇而得到）和最優(yōu)子結(jié)構(gòu)性質(zhì)。 五、實(shí)驗(yàn)心得： 在貪心算法中，每次做出的選擇僅在當(dāng)前的狀態(tài)下做出的最好的選擇，即局部最優(yōu)選擇。由于（ b[1],b[2],??b[n]）是這段路程加油次數(shù)最少的一個(gè)滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個(gè)加油站加油時(shí)， b[1]=1,則（ b[2],b[3],??b[n]）是從 a[2]到 a[n]這段路 程 上 加 油 次 數(shù) 最 少 且 這 段 路 程 上 的 加 油 站 個(gè) 數(shù) 為（ a[2],a[3],??a[n]）的最優(yōu)解 ,即每次汽車中剩下的油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油，每個(gè)過 程從加油開始行駛到再次加油滿足貪心且每一次加油后 ， 相當(dāng)于與起點(diǎn)具有相同的條件，每個(gè)過程都是相同且獨(dú)立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 該題設(shè)在加滿油后可行駛的 N 千米這段路程上任取兩個(gè)加油站Ａ、Ｂ，且Ａ距離始點(diǎn)比Ｂ距離始點(diǎn)近，則若在Ｂ加油不能到達(dá)終點(diǎn)那么在Ａ加油一定不能到達(dá)終點(diǎn)，因?yàn)?m+Nn+N，即在 B 點(diǎn)加油可行駛的路程比在 A點(diǎn)加油可行駛的路程要長 nm千米，所以只要終點(diǎn)不在 B、 C之間且在 C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會(huì)選擇距離加滿油得點(diǎn)遠(yuǎn)一些的加油站去加油，因此，加 油次數(shù)最少滿足貪心選擇性質(zhì)。 } ： （ 1） 貪心選擇性質(zhì) ： 所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解 可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。N)。 scanf(/n)。
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1