3

我有一个 M 平面之间的测量角度矩阵

 0    52    77    79
52     0    10    14
77    10     0     3
79    14     3     0

我有一个平面之间已知角度的列表，这是一个我命名的 N×N 矩阵rho。这是它的一个子集（它太大而无法显示）：

 0    51    68    75    78    81    82
51     0    17    24    28    30    32
68    17     0     7    11    13    15
75    24     7     0     4     6     8
78    28    11     4     0     2     4
81    30    13     6     2     0     2
82    32    15     8     4     2     0

我的任务是找到一组 M 平面，其角度rho最接近测量的角度。例如，上面显示的平面的测量角度相对接近平面 1、2、4 和 6 之间的已知角度。

换句话说，我需要在距离矩阵（使用余弦相关距离）中找到一组与我测量的距离匹配的点。这也可以被认为是将图案与模具相匹配。

在我的问题中，我有 M=5 和 N=415。

我真的很想弄清楚它，但时间已经不多了。所以目前我正在使用最简单的方法：迭代 3 个平面的所有可能组合，但这很慢，目前只为 M=3 编写。然后，我返回按匹配分数排序的匹配平面列表：

function [scores] = which_zones(rho, angles)
    N = size(rho,1);
    scores = zeros(N^3, 4);
    index = 1;
    for i=1:N-2
        for j=(i+1):N-1
            for k=(j+1):N
                found_angles = [rho(i,j) rho(i,k) rho(j,k)];
                score = sqrt(sum((found_angles-angles).^2));
                scores(index,:)=[score i j k];
                index = index + 1;
            end
        end;
    end
    scores=scores(1:(index-1),:); % was too lazy to pre-calculate #
    scores=sortrows(scores, 1);
end

我有一种感觉pdist2可能会有所帮助，但不确定如何。我将不胜感激任何帮助解决这个问题。

4

1 回答 1

1

有 http://www.mathworks.nl/help/matlab/ref/dsearchn.html 用于最近点搜索，但这需要相同的维度。我认为无论如何您都必须蛮力找到它，因为这只是一个特殊问题。

这是一种蛮力迭代第二个矩阵的所有唯一组合并计算 的方法score，之后您可以找到得分最低的那个。

A=[ 0    52    77    79;
   52     0    10    14;
   77    10     0     3;
   79    14     3     0];
B=[ 0    51    68    75    78    81    82;
   51     0    17    24    28    30    32;
   68    17     0     7    11    13    15;
   75    24     7     0     4     6     8;
   78    28    11     4     0     2     4;
   81    30    13     6     2     0     2;
   82    32    15     8     4     2     0];

M = size(A,1);
N = size(B,1);

% find all unique permutations of `1:M`
idx = nchoosek(1:N,M);
K = size(idx,1); % number of combinations = valid candidates for matching A

score = NaN(K,1);
idx_triu = triu(true(M,M),1);
Atriu = A(idx_triu);

for ii=1:K
    partB = B(idx(ii,:),idx(ii,:));
    partB_triu = partB(idx_triu);
    score = norm(Atriu-partB_triu,2);
end

[~, best_match_idx] = min(score);
best_match = idx(best_match_idx,:);

你的例子的解决方案实际上是[1 2 3 4]，所以左上部分Band not [1 2 4 6]。

这在理论上可以解决你的问题，我不知道如何让这个算法更快。但对于大量用户来说，它仍然会很慢。例如，对于您的M=5和N=415，有一些100 128 170 583组合B是可能的解决方案；仅在 32 位中生成选择器索引是不可能的，因为您无法解决所有问题。

NxN我认为这里真正的优化在于在前面的过滤部分中切除矩阵中的一些平面。

于 2013-07-07T18:17:01.360 回答