жадный алгоритм псевдокод

Question

Предположим, вам нужно ехать из Исламабада в Лахор. Вначале ваш газовый баллон заполнен. Ваш газовый баллон, когда он заполнен, содержит достаточно газа для перемещения m миль, и у вас есть карта, которая дает расстояние между автозаправочными станциями вдоль маршрута. Пусть d1 < d2 < … < dn - это место расположения всех АЗС по маршруту, где di - расстояние от Исламабада до АЗС. Расстояние между соседними АЗС составляет не более m миль. Кроме того, расстояние между последней бензоколонкой и Лахором составляет не более m миль.

Ваша цель - сделать как можно меньше газовых остановок по пути. Дайте жадный алгоритм (в форме псевдокода), чтобы определить, на каких автозаправочных станциях вы должны остановиться.

Является ли ваше решение оптимальным? Какова временная сложность вашего решения?

Answer 1

Этот алгоритм начинается в Исламабаде и неоднократно пытается проехать как можно дальше, не исчерпав газа.

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-й остановки самым дальним можно было бы дать stop n-1, тогда жадный алгоритм должен быть самый дальний он может быть для всех остановок по маршруту.

Хотя этот алгоритм имеет сложность O (n) и вычисляет оптимальное решение, маршрут, который он возвращает, может быть не очень «четным» или «гладким». Для того, чтобы создавать маршруты для фактического использования людьми, больше нужно было бы рассмотреть больше маршрутов, которые ограничивают их остановки более равномерно.