有一個地球的定向版本漫步者距離

Question

我現在有一個問題，在這裏我想比較兩個一維分佈。我的情況我試圖找到我需要移動其中一個分配才能將其轉換爲另一個分配，因此我將使用地球移動器距離進行比較。不過，我也對分配轉移到另一個方向的實際方向感興趣。

是否有1D移土機距離的定向版本？

更確切地說，我有兩個分配f : {1...N} -> |R和g : {1...N} -> |R我必須轉向對方。現在我還想將f中的垃圾箱中的污物量增加到g的垃圾箱中，但我想說明方向。即如果「污垢」從斌x搬到倉y我要乘我已經x-y而不是d(x,y)移動作爲標準推土機距離量。然後我想找到移動的地球總量最小化的運動。

是否存在已知的算法，我可以用這個？我想我應該可以修改原來的匈牙利算法，但我不知道如何做到這一點，因爲我從來沒有使用過此算法。

Answer 1

所以，如果我理解你的問題正確的話，我認爲以下（圍棋）的代碼將在解決的問題。如果你可以假設的積分在每個分佈是相等的（這意味着有可能轉變到彼此） ，然後在整個分配過程中左右移動，並在每個點上找出需要從右側移動多少污物，或者需要將多餘的污物從那裏移到左側。在所有情況下，您都可以假設您需要的任何污垢都能夠得到，因此可以暫時使用「負面」污垢。

// Finds out how to move dirt to transform b into a. 
// assumes that the integrals over a and b are equal 
func earthMover(a, b []int) []int { 
    r := make([]int, len(a)) 
    for i := 0; i < len(a); i++ { 
    // if diff is positive it means that there is too much dirt here and it 
    // must be moved to the right. if it is negative it means some dirt 
    // needs to be pulled in from the right. In either case dirt can be 
    // moved over multiple spaces. 
    diff := b[i] - a[i] 
    r[i] = diff 
    b[i] -= diff 
    if i < len(a) - 1 { 
     b[i+1] += diff 
    } 
    } 
    return r 
} 

這裏是一個例子。負數表示污物從右側被拉入，正數表示從左側到右側。我覺得你的指標你只是總結了所有的移動數組中的數字，所以這種情況下的解決方案是5

target: [ 3 0 1 0 2 6] 
source: [ 1 1 5 0 1 4] 
    move: [-2 -1 3 3 2 0] 

現在，我看到的是，如果這是真正你想要什麼，然後你真的在尋找分佈的均值或質量中心（污垢）的差異。例如：

  0 1 2 3 4 5 
    target: [ 3 0 1 0 2 6] 
weighted: 0 +0 +2 +0 +8+30 = 40 

    source: [ 1 1 5 0 1 4] 
weighted: 0 +1+10 +0 +4+20 = 35 

正如你所看到的，目標減去源的質量中心的質量中心是我們前面拿到了號，40 - 35 = 5

Answer 2

你的 「距離」 是平均值（F） - 平均值（克）。爲了儘量減少移動的地球總量，而不考慮移動的距離，貪婪算法達到最優，即分佈之間的統計距離。

Answer 3

https://github.com/wihoho/VideoRecognition

• 適應作者的C implementation與Python模塊通過一個文件接口
• 該修飾的C-碼的文件夾下EarthMoverDistance源碼