最短路徑|x0-x1|+|y0-y1|

以下題目不知能從何處思考？請大大指教，謝謝

DaDaSnake 住在一個名為 DaDaWorld 的世界，DaDaWorld 是一個棋盤格世界，就是所有位置都可以用整數座標 (x,y) 表示。還有一點就是因為 DaDaSnake 每次只能往上、下、左、右其中一個方向走一步，所以兩點之間的距離為曼哈頓距離，就是 P0(x0,y0) ,P1(x1,y1) 的距離為 |x0-x1|+|y0-y1|，記作 D(P0,P1)。...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

x、y 分離，找個別的中位數
該點即為 O
然後再算出距離總和

a333221

感覺像是作業，直觀地做就行了：

1. 寫函數計算 D(O,P1)+D(O,P2)+...+D(O,Pn)
2. 想一下所有可能的 O 有哪些？不用很精確沒關係，直觀想得到就可以，且可以多但不要少
3. 將 2 的結果代入 1，並將得到的最小值記錄下來，該值就是所求

如果不是作業，或如果在意速度，可以使用 snowflying 的建議，

註：滿足最小距離的 O 可能不止一個

a333221

1. 可以弄最佳解，最好也了解一下原因，好比中位數為何就是最佳解？
2. 用直觀寫出來的東西可能不是最快的，但寫完後還可以再進行調整。
3. 最小值只有一個，但符合最小值的 O 可能有好幾個

snowflying

a333221 發表於 2015-10-25 09:59 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

1. 可以弄最佳解，最好也了解一下原因，好比中位數為何就是最佳解？
2. 用直觀寫出來的東西可能不是最快的 ...

一般來講，競賽的題目若有多種解，題目會說明
...

瀏覽完整內容，請先 註冊 或 登入會員

找到一個 O(xo,yo)，使 D(O,P1)+D(O,P2)+...+D(O,Pn) 最小

只要找到一個 O(xo,yo)即可

要證明為什麼取中位數應該不難
自己想一下吧

a333221

一起回好像比較容易，就回在一起囉！

1. 證明為什麼取中位數對我來說並不難。

2. 直接回中位數的做法，個人主觀覺得對於發問者來說，有點像是：他問了一題數學的應用問題，
    問說「不知能從何處思考？」結果解答者沒回答怎麼思考？而是直接幫他把式子列好，然後說：
...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

a333221 發表於 2015-10-26 09:32 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

一起回好像比較容易，就回在一起囉！

1. 證明為什麼取中位數對我來說並不難。

...

瀏覽完整內容，請先 註冊 或 登入會員

舉例來說
1. 奇數個: 1, 4, 10
               |4-1| + |4-4| + |4-10| = 9 為最小 O=4
2. 偶數個: 1, 4, 10, 11
               |4-1|+|4-4|+|4-10|+|4-11| = |5-1|+|5-4|+|5-10|+|5-11| = ... = 16
               所以 O = {4, 5, 6, 7, 8, 9, 10} 皆有最小值 16  ...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

snowflying 發表於 2015-10-27 01:32 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

2.
給式子並沒有什麼問題
這一題相信就是要考 "中位數" 的概念

...

瀏覽完整內容，請先 註冊 或 登入會員

a333221

假設　x_1 ≦ x_2 ≦ ... ≦ x_n
定義 x_0 = -∞, x_n+1 = +∞, f(x) = Σ|x - x_k|, k = 1 ~ n;
僅需考慮 x_j < x_j+1 的開區間 (x_j, x_j+1), 且設 a,b 屬於 (x_j, x_j+1) and a < b
則,
  
  f(b)
= Σ|b - x_k|
= Σ|b - a + a - x_k|
= (Σ|a - x_k|) + j (b - a) - (n - j) (b - a)
= (Σ|a - x_k|) + (2j - n)(b - a)
...

瀏覽完整內容，請先 註冊 或 登入會員