Les bidons d'essence

L'algorithme glouton consiste à s'arrêter à la station accessible la plus lointaine à chaque étape.

def arrets(p: list, K: int) -> list:
    stops, position = [], 0
    i = 0
    while p[i] != p[-1]:
        # Rechercher la station la plus lointaine à portée d'autonomie
        while i + 1 < len(p) and p[i + 1] - position <= K:
            i += 1
        stops.append(p[i])
        position = p[i]
    return stops[:-1] if stops and stops[-1] == p[-1] else stops

Preuve (le glouton reste devant) : Notons $g_1<g_2<\cdots <g_r$ les positions des arrêts choisis par le glouton, et $o_1<o_2<\cdots <o_s$ ceux d'une planification optimale. Montrons par récurrence que $g_j\ge o_j$.

• Pour $j=1$ : le glouton choisit la station maximale accessible depuis le départ $p_0$, donc $g_1\ge o_1$.
• Si $g_j\ge o_j$ : la station $o_{j+1}$ est à une distance maximale de $K$ de $o_j$, et donc a fortiori à une distance inférieure ou égale à $K-(g_j-o_j)\le K$ du point $g_j$. L'autonomie de la voiture permet de franchir l'intervalle depuis $g_j$. Le choix du glouton $g_{j+1}$ étant maximal sur cet intervalle, on a $g_{j+1}\ge o_{j+1}$. Par conséquent, le glouton atteint l'arrivée avec un nombre d'arrêts $r\le s$.