算法設(shè)計與分析課程設(shè)計--用貪心算法解決汽車加油次數(shù)最少問題-文庫吧
2025-05-18 01:59 本頁面
【正文】 等，即ａ [i]=a[j]=L=N，則加油次數(shù)最少 k=n； B： 加油站間的距離相等，即ａ [i]=a[j]=LN，則不可能到達(dá)終點； C： 加油站間的距離相等， 即ａ [i]=a[j]=LN，則加油次數(shù)k=n/N(n%N==0)或 k=[n/N]+1(n%N！ =0)； D： 加油站間的距離不相等，即ａ [i]！ =a[j]，則加油次數(shù) k通過以下算法求解。 三 、 算法描述 該題目求加油最少次數(shù)，即求最優(yōu)解的問題，可分成幾個步驟，一般來說，每個步驟的最優(yōu)解不一定是整個問題的最優(yōu)解，然而對于有些問題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問題的求解過程看作是一系列選擇，從問題的某一個初始解出發(fā)，向給定目標(biāo)推進。推進的每一階段 不是依據(jù)某一個固定的遞推式，而是在每一個階段都看上去是一個最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下） 。 不斷地 將問題實例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個全局得最優(yōu)解。 貪心算法適用的問題必須滿足兩個屬性： （１）貪心性質(zhì)： 整體的最優(yōu)解可通過一系列局部最優(yōu)解達(dá)到，并且每次的選擇可以依賴以前做出的選擇，但不能依賴于以后的選擇。 （２）最優(yōu)子結(jié)構(gòu)： 問題的整體最優(yōu)解包含著它的子問題的最優(yōu)解。 （１）分解：將原問題分解為若干相互獨立的階段。 （２）解決：對于每一個階段求局部的最優(yōu)解。 （３）合并：將各個階段的解合并為原問題的解 。 [問題分析 ] 由于汽車是由始向終點方向開的 ,我們最大的麻煩就是不知道在哪個加油站加油可以使我們
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1