最低運輸費用 - 拼圖

先把題目簡化：

有 ABCD 四個地方各多一輛車，PQRS四個地方各少一輛車。

一樣要找出最少的代價把車子補滿。代價如下：

P Q R S
A 7 5 4 5
B 2 8 3 4
C 3 3 4 7
D 6 5 2 2

不過，在你準備找出最好的組合時，你發現一件事，

如果在 ABCD 把車賣掉，會有 u_A, u_B, u_C, u_D 的進帳

如果在 PQRS 直接買車，要花 v_P, v_Q, v_R, v_S

如果 u_i + v_j < c_ij ，

那與其把車從 i 運到 j，不如把 i 的車賣掉，在 j 直接買，

甚至，當 u_i + v_j <= c_ij 對所有的 i, j 都成立時，

就不用煩腦這個問題了，直接賣掉再買就好。

很剛好的是，你是一個車商，負責車子的買、賣，而你在這幾個地方也都有據點，

所以，你想要找到一個定價，使得你可以賺最多錢，

而為了讓他們把所有的車都讓你處理，你當然要讓 u_i + v_j <= c_ij 都成立

有一個顯然會成立的定價方法是： u_i = 0, v_j = min{c_ij}

不過，這可能不是最好的定價方法，你希望可以賺更多的錢。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

看到這裡，可能會有人問，車商的定價到底和原本的問題有什麼關係？

假設 u_i + v_j <= c_ij 對所有 i, j 都成立

那 sum {u_i} + sum {v_j} <= 任何一種運送方式的成本

假設 c_AP c_BQ c_CR c_DS 是你選的運送方式，那麼

u_A + v_P <= c_AP
u_B + v_Q <= c_BQ
u_C + v_R <= c_CR
u_D + v_S <= c_DS

sum {u_i} + sum {v_j} <= 你的成本

換言之，任意符合這樣條件的 u, v ，上面的等式都成立。

而我們知道運送成本有最小值，而這個就是 sum {u_i} + sum {v_j} 的最大值

而且，等號是可以成立的，假設剛剛的 c_AP + c_BQ + c_CR + c_DS 是最小，

那我們讓 u_i = 0, v_j = c_ij (c_ij 是被選到的配對)

就是一個 sum {u_i} + sum {v_j} = c_AP + c_BQ + c_CR + c_DS 的例子

也就是說，如果我們可以找到 sum {u_i} + sum {v_j} 的最大值

那這個值就是運送成本的最小值，兩個問題其實是一樣的。


現在，讓我們來解解看新的問題，

P Q R S
A 7 5 4 5
B 2 8 3 4
C 3 3 4 7
D 6 5 2 2

我們先找一個可能的 u, v 組合，然後再慢慢的把他變大。

我們就選個 u_i = 0, v_j = min {c_ij} 吧，

括號中的是 u_i 或 v_j ，中間的表格則是 c_ij - u_i - v_j

P(2) Q(3) R(2) S(2)
A(0) 5 2 2 3
B(0) 0 5 1 2
C(0) 1 0 2 5
D(0) 4 2 0 0

因為我們知道最大值發生時，會有 c_ij = u_i + v_j （ij 是我們選中的匹配）

也就是上面表格中的 0 ，如果我們可以找到四個 0 ，他們都在不同的行和列，

那我們就完成了，可是，現在顯然無法達到，所以，我們要調整我們的 u, v ，

造成更多的 0 ，以找到更多的匹配，可是調整的時候，

還要要有 u_i + v_j <= c_ij for all i, j

調整的方法是：

先選出最少的行和列，使得所有的 0 都在這幾個行或列中，比如：

P(2) Q(3) R(2) S(2) P(2) Q(3) R(2) S(2)
A(0) 5 2 2 3 A(0) 5 2 2 3
B(0) 0 5 1 2 或是 B(0) 0 5 1 2
C(0) 1 0 2 5 C(0) 1 0 2 5
D(0) 4 2 0 0 D(0) 4 2 0 0

都用了三個行或列就包含了所有的 0 ，現在，我們在沒被覆蓋的格子中，選出最小的，

右邊被選出的行、列為 Z = {D, P, Q} ，

(Z 沒有什麼特別的意義，只是集合的 S 被用掉了)

而在沒被覆蓋的格子中，最小的是 1 ，令這個值為 e

我們順便定義 X = {A, B, C, D} , Y = {P, Q, R, S}

現在要來調整 u, v 了

對 x_i \in (X ∩ Z) , u_i <- u_i - e
y_j \in (Y \ Z) , v_j <- v_j + e (x <- .... 代表新的 x 的值為 ....)

以現在的狀況來說， X ∩ Z = {D}, Y \ Z = {R, S}

所以，

u_D <- u_D - 1 = 0 - 1 = -1
v_R <- v_R + 1 = 2 + 1 = 3
v_S <- v_S + 1 = 2 + 1 = 3

新的表格為：

P(2) Q(3) R(3) S(3)
A( 0) 5 2 1 2
B( 0) 0 5 0 1
C( 0) 1 0 1 4
D(-1) 5 3 0 0

重複上面的動作，再找出最少的行和列來包括所有的 0

P(2) Q(3) R(3) S(3)
A( 0) 5 2 1 2
B( 0) 0 5 0 1
C( 0) 1 0 1 4
D(-1) 5 3 0 0

Z = {B, C, D}
e = 1

X ∩ Z = {B, C, D}
Y \ Z = {P, Q, R, S}

u_B <- u_B - 1 = -1
u_C <- u_C - 1 = -1
u_D <- u_D - 1 = -2

v_P <- v_P + 1 = 3
v_Q <- v_Q + 1 = 4
v_R <- v_R + 1 = 4
v_S <- v_S + 1 = 4

P(3) Q(4) R(4) S(4)
A( 0) 4 1 0 1
B(-1) 0 5 0 1
C(-1) 1 0 1 4
D(-2) 5 3 0 0

現在我們可以找到一個完美匹配, A-R 、B-P 、C-Q 、D-S

這個匹配的花費為 c_AR + c_BP + c_CQ + c_DS = 4 + 2 + 3 + 2 = 11

而你的 sum {u_i} + sum {v_j} = -1 + -1 + -2 + 3 + 4 + 4 + 4 = 11

而這也是最少的花費。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

整理一下：

X = {A, B, C, D, ...} 是所有多出一台車的地方
Y = {a, b, c, d, ...} 是所有少一台車的地方

|X| = |Y| = N (我們總是可以透過增加一些無用的據點，讓這個調件成立)

c_ij (i \in X, j \in Y) 是從 i 運到 j 的花費，

那我們一開始令 u_i = 0, v_j = min {c_ij}

1. 考慮 c_ij - u_i - v_j 這張表中的 0 ，如果這些 0 可以形成一組完美匹配，

那現在的 sum {u_i} + sum {v_j} 就是答案，而那組完美匹配就是你要的運送方式，

否則就到步驟二

2. 找到最少的行或列，使所有的 0 都被這些行或列包含，令此行、列的集合為 Z

3. let e = min {c_ij - u_i - v_j | i \in (X\Z), j \in (Y\Z)}

4. for all x_i \in X ∩ Z, u_i <- u_i - e
for all y_j \in Y \ Z, v_j <- v_j + e

回到步驟一

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

再來是比較痛苦的證明...

1. 從 u, v 變成 u', v' ，新的 u, v 還是滿足

u'_i + v'_j <= c_ij for all i, j

這個條件。

考慮 x_i \in X \ Z, y_j \in Y ∩ Z

因為 u_i, v_j 都沒變，所以不等式還是成立

考慮 x_i \in X ∩ Z, y_j \in Y \ Z

u_i 少了 e ，v_j 多了 e ， u'_i + v'_j 不變，還是成立

考慮 x_i \in X ∩ Z, y_j \in Y ∩ Z

u_i 少了 e ，v_j 不變，所以 u'_i + v'_j 變小，還是成立

考慮 x_i \in X \ Z, y_j \in Y \ Z

u_i 不變，v_j 少 e ，u'_i + v'_j 變大了，不過

e = min {c_ij - u_i - v_j | i \in X\Z, j \in Y\Z}

也就是 e <= c_ij - u_i - v_j

u'_i + v'_j = u_i + v_j - e <= u_i + v_j - (c_ij - u_i - v_j)

u'_i + v'_j <= c_ij 還是成立

所以 u', v' 還是滿足這個性質

再來是停止條件，由前面我們可以知道 u, v 的和不會超過任何的運送方式，

而最便宜的運送方式恰好和 u, v 和的最大值相同，在我們的終止條件中，

是用 u, v 找到一組完美匹配 M ，這個匹配有 c(M) = sum {u} + sum {v}

c(M) 代表 M 的花費

所以 M 是最少的花費， sum {u} + sum {v} 則是最大的 u, v 組合

所以，如果我們的操作可以達到終止條件，那我們得到的答案一定是對的，

再來的問題是我們可以達到終止條件嗎？

答案當然是可以

首先， c_ij - u_i - v_j >= 0 for all i, j

而 e = min {c_ij - u_i - v_j | i \in X\Z, j \in Y\Z}

Z 中的行或列已經包括了所有的 0 ，所以， e > 0

現在，假設 |X ∩ Z| = a, |Y ∩ Z| = b , |X| = |Y| = N, a + b = |Z| = z

那麼，有 a 個 u_i 會被減少，N - b 個 v_j 會被增加

sum {u'} + sum {v'} = sum {u} - (a * e) + sum {v} + (N - b) * e

= sum {u} + sum {v} + (N - a - b) * e

= sum {u} + sum {v} + (N - z) * e

因為 z < N (因為找不到完美匹配，如果 z = N ，一定找得到完美匹配)

所以 sum {u} + sum {v} 在每一次的操作都會增加，直到我們找到完美匹配為止

================

其實我們還可以證明在 N^2 次的操作內就會停止，不過有點麻煩，就略過了。

而且我也應該要給出 Z 的選擇流程，不過，人眼看還滿快的，也被我略過了。

======================

而在原本的問題呢，各地都多了數輛車或少了數輛車，

和我們簡化過的各地都只有一輛多的或少的車有點不同，

不過，我們可以把一個地方看成很多個小地方，他們都多或少一輛車，

比如 A 地，原本多了九輛，現在變成 A_1 ~ A_9 各多了一輛車，

而 P 地則變成 P_1 ~ P_5 ，各少一輛車，並且 A_i 到 P_j 的花費都是 60 元

這樣就和簡化過的問題一樣了。


如果，今天多了 x 輛車，少了 y 輛車，且 x > y ，代表有 x - y 輛車不用動

我們可以加入 x - y 個地點，他們都少了 1 輛車，並且，

不論從哪裡把車子運過來，花費都是 0 元，這樣又和簡化過的問題一樣了。

如果今天是 x < y ，我們可以反過來加入一些幽靈車，讓 x 和 y 變成一樣多。


大概就介紹到這邊吧

--