Question d'algorithme : Trouver le vol le moins cher

Question

J'ai récemment passé un entretien dans une entreprise (commençant par M et se terminant par A) qui m'a posé cette question. Toujours en train de pratiquer mes algorithmes, j'espérais que quelqu'un pourrait m'aider à comprendre comment résoudre ce problème, et ces types de problèmes.

Le problème :

Vous disposez de 2 tableaux. Par exemple :

D = [10,7,13,12,4]
R = [5,12,7,10,12]

D représente les prix de départ des vols de la ville A à la ville B. R représente les prix de retour des vols de la ville B à la ville A. Trouvez le coût minimum d'un vol aller-retour entre la ville A et la ville B. Par exemple, le minimum dans l'exemple est D[1] + R[2].

(il est possible de prendre le vol de retour sur le même index ou un index supérieur au vol de départ)

La partie délicate est que, évidemment, vous devez partir avant de revenir.

L'approche naïve est juste une double boucle for combinant toutes les possibilités. Cependant, je sais qu'il existe une meilleure approche, mais je n'arrive pas à la comprendre. Je crois que nous voulons créer une sorte de tableau temporaire avec le minimum jusqu'à présent ou quelque chose comme ça...

Merci de m'avoir lu.

Answer 1

Je suis parfaitement satisfait de la solution de @user1984. Mais si vous voulez vraiment les impressionner :

from itertools import accumulate

monoQ = list(accumulate(reversed(R), min))
monoQ.reverse()

best = min(d + r for d, r in zip(D, monoQ))

La plupart des gens connaissent list(accumulate((1, 2, 3, 4 5), operator.add)) qui renvoie (1, 3, 6, 10, 15), mais en utilisant min, le résultat est l'élément le plus petit vu jusqu'à présent. Comme vous voulez le plus petit élément d'ici à la fin, vous devez inverser la liste, accumuler, puis la reverser à nouveau.

---

Comme cela a été mentionné dans une des autres réponses, ceci pourrait être réécrit pour être une solution en espace O(1).

best = min(d + r for d, r in zip(reversed(D), accumulate(reversed(R), min)))

C'est un peu bricolé, et je ne le recommanderais pas sauf si vous êtes spécifiquement demandé une solution en espace O(1).

Malheureusement, vous devez utiliser reverse(D) et travailler depuis la fin de la liste plutôt que reverse(accumulate(...)) car vous ne pouvez pas appliquer reverse à une accumulation. zip, reversed, et accumulate renvoient tous des itérateurs plutôt que des listes ou des tuples.

Answer 2

Créez une file/pile mono à partir du tableau de prix de retour R, puis vous pouvez le résoudre en O(n) où n est la longueur de D.

R = [5, 12, 9, 10, 12] => [5, 9, 9, 10, 12]

Comme vous pouvez le voir à chaque étape, nous avons accès au vol de retour le moins cher possible à l'index i et au-dessus.

Maintenant, itérez sur les éléments de D et regardez cet index dans monoQ. Comme cet index dans monoQ est le plus petit possible dans R pour i et au-dessus, vous savez maintenant que vous ne pouvez pas faire mieux à ce stade.

En code:

D = [10,7,15,12,4]
R = [5,12,9,10,12]

monoQ = [0]*len(R)
monoQ[-1] = R[-1]

for i in range(len(R)-2, -1, -1):
  monoQ[i] = min(monoQ[i+1], R[i])

best = R[0]+D[0]
for i, el in enumerate(D):
  best = min(best, D[i]+monoQ[i])
print(best)