イスラマバードからラホールまで車で行かなければならないとします。開始時、ガソリンタンクは満タンです。ガソリン タンクが満タンの場合m、何マイルも移動するのに十分なガソリンが入っています。また、ルートに沿ったガソリン スタンド間の距離を示した地図があります。イスラマバードからガソリン スタンドまでの距離をd1 < d2 < … < dn、ルートに沿ったすべてのガソリン スタンドの場所とします。di隣り合うガソリンスタンド間の距離はせいぜいmマイルです。また、最後のガソリンスタンドからラホールまでの距離はせいぜいmマイルです。
あなたの目標は、途中でガソリンスタンドをできるだけ少なくすることです。どのガソリンスタンドに立ち寄るべきかを決定する貪欲なアルゴリズムを (疑似コード形式で) 与えてください。
あなたのソリューションは最適ですか？ソリューションの時間計算量はどのくらいですか?
このアルゴリズムはイスラマバードから始まり、ガス欠にならずにできるだけ遠くまで運転しようと繰り返し試みます。
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) の複雑さを持ち、計算によって最適解を返しますが、返されるルートは非常に「均一な」または「滑らかな」ルートではない可能性があります。人々が実際に使用するルートを作成するには、より均等に停車するルートを検討する必要があります。