algorithme pour placer une boîte aux lettres pour minimiser la distance totale que les résidents se déplacent pour obtenir leur courrier

Question

On suppose que l'entrée est spécifiée comme un tableau d'objets de construction, où chaque bâtiment a un certain nombre de résidents d'une sa distance depuis le début de la rue .

Distance totale = SOMME (distance [i] * #residents [i])

Je trouve ici deux questions qui sont semblables, mais ils ont des exigences légèrement différentes:

• Minimizing weighted sum: La solution de cette question trouve le chemin minimum traversant tous les points. Ici, je cherche une somme minimale des distances totales de chaque bâtiment à l'endroit où la boîte aux lettres est.

• Minimum Total Distance From Locations: Il utilise des coordonnées 2D, et plus important, la solution ne tient pas compte du poids (nombre de résidents) sur chaque emplacement.

J'ai vu ce problème lors de la lecture des éléments des entrevues de programmation (livre vraiment sympa, d'ailleurs), et cela est répertorié comme une variante de l'algorithme de QuickSelect. Considérant que la médiane est le point qui minimise la somme des distances, il semble que la solution impliquerait la sélection rapide pour trouver le bâtiment à la position «médiane» de la rue en O (N).

Mais je ne peux pas comprendre comment compte les résidents de chaque bâtiment et garder toujours la solution linéaire.

Answer 1

Nous pouvons utiliser les deltas pour déterminer la direction. Je vais expliquer ce que je veux dire. En ce qui concerne le choix d'un emplacement de boîte aux lettres à l'un des bâtiments (qui est, non pas entre les deux bâtiments):

Choisissez l'un des bâtiments comme un pivot (emplacement potentiel de boîte aux lettres). Partitionner les bâtiments en fonction de leur emplacement par rapport au pivot. Bien que le partitionnement, tenir un registre de l'immeuble le plus proche de chaque côté du pivot, ainsi que (1) le nombre total de résidents de chaque côté du pivot, et (2) f(side, pivot) représentant la somme totale de la distance de chacun des bâtiments de le pivot multiplié par le nombre de résidents dans ce bâtiment.

Maintenant, nous avons:

L pivot R 

Pour déterminer si une amélioration peut être faite pour notre choix, essayez chacun des bâtiments les plus proches que nous avons enregistrés plus tôt:

Si nous devions passer notre choix d'un bâtiment à gauche, comment les résultats changeraient-ils? Appelons le bâtiment le plus proche sur la gauche build_l, et la droite, build_r. Ainsi, les nouveaux résultats en mouvement notre choix un bâtiment à gauche serait:

Côté gauche:

f(L, pivot) 
- distance(build_l, pivot) * num_residents(build_l) 

Côté droit:

f(R, pivot) 
    // we saved this earlier 
+ total_residents(R) * distance(pivot, build_l) 
+ num_residents(pivot) * distance(pivot, build_l) 

Effectuer un calcul similaire pour déplacer le choix d'un bâtiment le droit de voir qui donne un plus petit total. Ensuite, choisissez le côté avec le bâtiment qui produit une amélioration et partitionnez-le récursivement de la même manière, jusqu'à ce qu'un résultat optimal soit trouvé.Pour l'autre côté, nous gardons une trace du nombre total de résidents, et le résultat total pour f jusqu'à présent, que nous pouvons mettre à jour avec les nouveaux ajouts que nous allons.