給定兩個陣列A和B，如何獲得其爲最接近於B值甲

Question

假設我有兩個陣列以升序排序，即：

A = [1 5 7]，B = [1 2 3 6 9 10]

我想從B創建一個新的向量B'，它只包含最接近A值的值（每個值爲1）。

我也需要索引。所以，在我的例子我想獲得：

B」 = [1 6 9]，IDX = [1 4 5]

注意，第三個值爲9實際上6是更接近7，但它已經'採取'，因爲它已接近4.

任何想法適合的代碼？

注：我真正的數組是更大，包含真正的（不是int）值

而且，它被賦予B是不再那麼A

謝謝！

Answer 1

假設要整體差異的A元件和匹配元件之間的最小化在B，問題可被寫爲分配給每行（的A元件）的柱（的B元件）的分配問題給出了一個成本矩陣C。匈牙利語（或Munkres'）算法解決了分配問題。

我假設你希望儘量減少在BA之間匹配元素累積平方距離，並通過異草從https://www.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems--v2-3-使用功能[assignment,cost] = munkres(costMat)：

A = [1 5 7]; 
B = [1 2 3 6 9 10]; 
[Bprime,matches] = matching(A,B) 

function [Bprime,matches] = matching(A,B) 
    C = (repmat(A',1,length(B)) - repmat(B,length(A),1)).^2; 
    [matches,~] = munkres(C); 
    Bprime = B(matches); 
end 

假設，而不是你想遞歸尋找匹配 ，正如你的問題所建議的那樣，你可以通過A，A中的每個元素找到B中最接近的剩餘元素並丟棄它（下面的sortedmatching）;潛在

A = [1 5 7]; 
B = [1 2 3 6 9 10]; 
[~,~,Bprime,matches] = sortedmatching(A,B,[],[]) 
[~,~,Bprime,matches] = greedymatching(A,B,[],[]) 

function [A,B,Bprime,matches] = sortedmatching(A,B,Bprime,matches) 
    [~,ix] = min((A(1) - B).^2); 
    matches = [matches ix]; 
    Bprime = [Bprime B(ix)]; 
    A = A(2:end); 
    B(ix) = Inf; 
    if(not(isempty(A))) 
     [A,B,Bprime,matches] = sortedmatching(A,B,Bprime,matches); 
    end 
end 

function [A,B,Bprime,matches] = greedymatching(A,B,Bprime,matches) 
    C = (repmat(A',1,length(B)) - repmat(B,length(A),1)).^2; 
    [minrows,ixrows] = min(C); 
    [~,ixcol] = min(minrows); 
    ixrow = ixrows(ixcol); 
    matches(ixrow) = ixcol; 
    Bprime(ixrow) = B(ixcol); 
    A(ixrow) = -Inf; 
    B(ixcol) = Inf; 
    if(max(A) > -Inf) 
     [A,B,Bprime,matches] = greedymatching(A,B,Bprime,matches); 
    end 
end 

同時產生在你的例子相同的結果，所有的三種方法：或者你可以迭代地形成，並丟棄剩餘的元件之間的距離最小化的匹配在A和B直到A所有元素都匹配（greedymatching）對相同的數據給出不同的答案。

Answer 2

通常情況下，我會在Matlab中運行for和while循環，但在這種情況下，我看不出如何向量化解決方案。至少它是O（N）（或接近足夠，取決於B中每個A(i)有多少同等接近的匹配）。這將是非常簡單的用C編寫以下，並把它編譯成MEX文件，使其以最佳的速度運行，但這裏有一個純Matlab的解決方案：

function [out, ind] = greedy_nearest(A, B) 

if nargin < 1, A = [1 5 7]; end 
if nargin < 2, B = [1 2 3 6 9 10]; end 

ind = A * 0; 
walk = 1; 
for i = 1:numel(A) 
    match = 0; 
    lastDelta = inf; 
    while walk < numel(B) 
     delta = abs(B(walk) - A(i)); 
     if delta < lastDelta, match = walk; end 
     if delta > lastDelta, break, end 
     lastDelta = delta; 
     walk = walk + 1; 
    end 
    ind(i) = match; 
    walk = match + 1; 
end 
out = B(ind); 

Answer 3

你可以首先從絕對距離將A中的每個值分配給B中的每個值，對它們進行排序，然後在每列中向下看時獲取序列的第一個唯一值。

% Get distance from each value in A to each value in B 
[~, minIdx] = sort(abs(bsxfun(@minus, A,B.'))); 

% Get first unique sequence looking down each column 
idx = zeros(size(A)); 
for iCol = 1:numel(A) 
    for iRow = 1:iCol 
     if ~ismember(idx, minIdx(iRow,iCol)) 
      idx(iCol) = minIdx(iRow,iCol); 
      break 
     end 
    end 
end 

申請時idx到B

>> idx 
1  4  5 
>> B(idx) 
1  6  9