在數軸上找一點使得該點到所有其他點的距離之和最小

方法：找到大小為中位數的點，該點就是要求的點（如有兩個取之間任意一點都行）

證明：

　　先看看當只有2個點時的情況：

　

　　分類討論：

　　如果在A的左邊(如 $P_1$ )，距離之和( $sum$ )為：$dis(P_1,A)+dis(P_1,B)=dis(P_1,A)+dis(P_1,A)+dis(A,B)$

　　( $dis(a,b)$ 為 $a$ 到 $b$ 的距離)

　　如果在 $A$ 和 $B$ 的中間（包括 $A,B$）： $sum=dis(P_2,A)+dis(P_2,B)=dis(A,B)$

　　如果在右邊： $sum=dis(P_3,A)+dis(P_3,B)=dis(A,B)+dis(P_3,B)+dis(P_3,B)$

　　顯然在 $A$ 和 $B$ 中間時距離之和最小。

　　那對于 $3$ 個點時呢：

　　設中間的點為 $C$ ，旁邊的為 $A,B$

　　一個點 $P$ 到各個點的距離之和為： $dis(A,P)+dis(B,P)+dis(C,P)=(dis(A,P)+dis(B,P))+dis(C,P)$

　　如果在能夠滿足 $dis(A,P)+dis(B,P)$ 最小的情況下還能滿足 $dis(C,P)$ 最小，那么就一定是最優的方案

　　顯然 當 $P$ 在 $A,B$ 中間時滿足 $dis(A,P)+dis(B,P)$ 最小，

　　又因為 點 $C$ 在 $A,B$ 中，所以當點 $P$ 和點 $C$ 重合時不僅 $dis(C,P)=0$ 最小，而且 $dis(A,P)+dis(B,P)$ 最小

　　所以取中間的點C是最優的方案。

　　對于4個點時：

　　同樣的思路：

　　設中間的點為 $C,D$，旁邊的為 $A,B$

　　如果能滿足在 $A,B$ 中間能找到一個點 $P$?使得 $P$ 到 $C,D$ 的距離之和最小

　　那么 $P$ 就是最優方案（因為已經滿足 $P$ 到 $A,B$ 的距離之和最小了...）

　　由前面可知，當 $P$ 在 $C,D$ 中間時 $P$ 到 $C,D$ 的距離之和最小，并且因為 $C,D$ 又在 $A,B$ 中間

　　所以當 $P$在 $C,D$ 中間時，$P$ 到各點的距離最小。

?

　　那么對于多個點時：

　　首先找到最外面的兩個點，點 $P$ 要在它們之間

　　然后在找次外面的點，點 $P$ 也要在它們之間

　　......

　　一直找到只剩 $1$ 或 $2$ 個點

　　如果只剩一個點，那么最優方案就是 $P$ 取這個點

　　否則 $P$ 可以取兩個點之間的任意位置

　　這樣就可以保證方案最優

　　?即：找到大小為中位數的點（如有兩個取之間任意一點都行）

?證明完畢.

　　

?

轉載于:https://www.cnblogs.com/LLTYYC/p/9537677.html

總結

以上是生活随笔為你收集整理的关于货仓选址问题的方法及证明（在数轴上找一点使得该点到所有其他点的距离之和最小）...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。