貪婪算法僞代碼

-4

假設你必須從伊斯蘭堡驅車前往拉合爾。在開始時，你的油箱已滿。您的油箱充滿後，將持有足夠的油氣以行駛m英里，並且您有一張地圖可以給出沿途加油站之間的距離。假設d1 < d2 < … < dn是沿途所有加油站的位置，其中di是從伊斯蘭堡到加油站的距離。相鄰加油站之間的距離最多爲m英里。此外，最後一個加油站和拉合爾之間的距離最大爲m英里。貪婪算法僞代碼

你的目標是在儘可能少的地方停下加油站。給出一個貪婪算法（以僞代碼形式）來確定你應該停止哪個加油站。

您的解決方案是否最優？你的解決方案的時間複雜度是多少？

來源

2013-07-25 user2617096

這個問題看起來像一些家庭作業的複製和粘貼作業。無論如何，這是**的主題**爲*「提出問題的代碼必須證明**對所解決問題的最小理解**，包括嘗試解決方案，爲什麼他們沒有工作，以及預期的結果。：[堆棧溢出問題清單]（http://meta.stackexchange.com/questions/156810/stack-overflow-question-checklist）「* –

我無法映射貪婪算法的類型，請幫助！ – user2617096

比TSP容易得多。我猜這是訂單N，其中N是兩個城市之間的加油站數量。 – Jiminion

這個算法開始於伊斯蘭堡，並反覆試圖儘可能開車，而不用耗盡氣體。

current_distance = 0 
current_stop = 0 
stops = [] 
while current != lahore: 
    next_stop = 0 
    while distance(next_stop) - current_distance <= m: 
    next_stop = next_stop + 1 
    next_stop = next_stop - 1 

    current_stop = next_stop 
    current_distance = distance(current_stop) 
    add next_stop to stops 
return stops

這是一個最佳解決方案。爲了看到這一點，我們注意到任何一個停止序列花費較少的停止，那麼貪婪算法就不得不在路徑某個點「傳遞」貪婪算法。

使用歸納法，我們可以看到，如果貪婪算法是最遠的，它可以在第一站之後，並且在第n站之後，它可以是最遠的，可以停止n-1，那麼貪婪算法必須是沿着路線的所有站點可以達到最遠。

雖然這個算法具有複雜度O（n）並且計算返回最優解，但它返回的路線可能不是一條非常「平坦」或「平滑」的路線。爲了生產人們實際使用的路線，需要考慮更多的路線，以便更均勻地停靠它們。

來源

2013-07-25 04:51:33 cptroot

貪婪算法僞代碼

回答

相關問題