Matlab最近的邻居/跟踪点

我有一组n复杂的数字，从时间步骤1到nsampl，通过复杂的平面。我想绘制这些数字和它们随时间的轨迹（y轴表示虚部，x轴表示实部）。这些数字存储在n x nsampl向量中。然而，在每个时间步中，n点的顺序是随机的。因此，在每个时间步中，我会在上一个时间步中选取一个点，在当前时间步中找到其最近的邻居，并将其放置在与当前点相同的位置。然后我重复所有其他n-1点并继续下一个时间步骤。这样，上一步中的每个点都与新步骤中的一个点（1：1关系）相关联。我目前的实施和一个例子如下。但是，我的实现非常慢（10 x 4000复数需要大约10秒）。由于我想增加两者，集合大小n和时间框架nsampl这对我来说非常重要。有没有更聪明的方法来实现这一点，以获得一些表现？Matlab最近的邻居/跟踪点

例，其中n = 3和nsampl = 2：

%manually create a test vector X 
X=zeros(3,2); % zeros(n,nsampl) 
X(:,1)=[1+1i; 2+2i; 3+3i]; 
X(:,2)=[2.1+2i; 5+5i; 1.1+1.1i]; % <-- this is my vector with complex numbers 

%vector sort algorithm 
for k=2:nsampl 
    Xlast=[real(X(:,k-1)) imag(X(:,k-1))];   % create vector with x/y-coords from last time step 
    Xcur=[real(X(:,k)) imag(X(:,k))];    % create vector with x/y-coords from current time step 
    for i=1:size(X,1) % loop over all n points 
     idx = knnsearch(Xcur(i:end,:),Xlast(i,:)); %find nearest neighbor to Xlast(i,:), but only use the points not already associated, thus Xcur(i:end,:) points 
     idx = idx + i - 1; 
     Xcur([i idx],:) = Xcur([idx i],:);   %sort nearest neighbor to the same position in the vector as it was in the last time step 
    end 
    X(:,k) = Xcur(:,1)+1i*Xcur(:,2);    %revert x/y coordinates to a complex number 
end

结果：

X(:,2)=[1.1+1.1i; 2.1+2i; 5+5i];

谁能帮我加快这个代码？

来源

2015-09-01 DayAndNight

是否有必要精确地复制算法的行为？特别是步骤k中的两个点（可以说是第一个和第二个）具有第k + 1步的第7个点，因为它是邻居，将其移动两次。 – Daniel

或者为了进一步精确我之前的评论，您的描述听起来像是“加权二分图的匹配”（最小化权重），并且您的代码会执行一个贪婪版本，这接近最佳解决方案。 – Daniel

我希望我能理解你的评论权利，因为我对双方图表一无所知。我想我不需要复制完全相同的行为，只要还有1：1的关系（即'X（：，2）= [1.1 + 1.1i; 2.1 + 2i; 2.1 + 2i]'因为它为两个不同的祖先找到了两次相同的最近邻居 – DayAndNight

您正在试图解决的问题是由the hungarian algorithm（又名munkres）解决的组合优化问题。幸运的是，有一个matlab实现available for download.下载文件，并将其放在搜索路径或函数旁边。使用它的代码是：

for k=2:size(X,2) 
    %build up a cost matrix, here cost is the distance between two points. 
    pairwise_distances=abs(bsxfun(@minus,X(:,k-1),X(:,k).')); 
    %let the algorithm find the optimal pairing 
    permutation=munkres(pairwise_distances); 
    %apply it 
    X(:,k)=X(permutation,k); 
end

来源

2015-09-01 23:20:17 Daniel

Matlab最近的邻居/跟踪点

回答

相关问题