5

假设一条线段有 25 个点，这些点可能分布不均（空间上），如下图所示： 在此处输入图像描述

我的问题是我们如何在这 25 个点中选择 10 个点，使这 10 个点在空间上尽可能均匀分布。在idea的情况下，选择的点应该是这样的： 在此处输入图像描述

编辑： 确实，如果我能说出证明“均匀分布”的标准，这个问题会变得更加优雅。我所知道的是我对选定点的期望：如果我将线段分成 10 个相等的线段。我希望每个小线段上应该有一个点。当然也有可能在一些小的线段中找不到代表点。在这种情况下，我将求助于具有代表点的相邻小线段。下一步我将把选中的相邻段进一步分成两部分：如果每一部分都有代表点，那么空代表点问题就解决了。如果我们无法在其中一个小线段中找到代表点，我们可以将其进一步划分为更小的部分。或者我们可以求助于下一个相邻的线段。

编辑： 使用动态编程，一个可能的解决方案实现如下：

#include <iostream>
#include <vector>
using namespace std;


struct  Note
{
    int previous_node;
    double cost;

};
typedef struct Note Note;

int main()
{

    double dis[25] = 
    {0.0344460805029088, 0.118997681558377, 0.162611735194631,
    0.186872604554379, 0.223811939491137, 0.276025076998578,
    0.317099480060861, 0.340385726666133, 0.381558457093008,
    0.438744359656398, 0.445586200710900, 0.489764395788231,
    0.498364051982143, 0.585267750979777, 0.646313010111265,
    0.655098003973841, 0.679702676853675, 0.694828622975817,
    0.709364830858073, 0.754686681982361, 0.765516788149002,
    0.795199901137063, 0.823457828327293, 0.950222048838355, 0.959743958516081};

    Note solutions[25];
    for(int i=0; i<25; i++)
    {
        solutions[i].cost = 1000000;
    }
    solutions[0].cost = 0;
    solutions[0].previous_node = 0;



    for(int i=0; i<25; i++)
    {
        for(int j= i-1; j>=0; j--)
        {
            double tempcost = solutions[j].cost + std::abs(dis[i]-dis[j]-0.1);
            if (tempcost<solutions[i].cost)
            {
                solutions[i].previous_node = j;
                solutions[i].cost = tempcost;
            }

        }
    }
    vector<int> selected_points_index;
    int i= 24;
    selected_points_index.push_back(i);
    while (solutions[i].previous_node != 0)
    {
        i = solutions[i].previous_node;
        selected_points_index.push_back(i);

    }
    selected_points_index.push_back(0);

    std::reverse(selected_points_index.begin(),selected_points_index.end());

    for(int i=0; i<selected_points_index.size(); i++)
        cout<<selected_points_index[i]<<endl;





    return 0;
}

结果如下图所示，其中选中的点用绿色表示：

在此处输入图像描述

4

3 回答 3

6

直到一个好的，可能的O(n^2)解决方案出现，使用这个近似值：

将范围划分为 10 个大小相等的箱。在每个 bin 中选择最靠近每个 bin 中心的点。任务完成。

如果您发现任何垃圾箱是空的，请选择较少数量的垃圾箱并重试。

如果没有有关您尝试实现的科学模型的信息，就很难 (a) 提出更合适的算法和/或 (b) 证明更复杂算法的计算工作是合理的。

于 2013-08-14T09:01:42.160 回答
3

让 {x[i]} 成为您的一组有序点。我想你需要做的是找到 10 个点的子集 {y[i]} 最小化 \sum{|y[i]-y[i-1]-0.1|} 与 y[-1] = 0 .

现在，如果您将配置视为强连通有向图，其中每个节点是 25 个双精度图之一，并且每条边的成本为 |y[i]-y[i-1]-0.1|，您应该能够使用 Dijkstra 算法在 O(n^2 +nlogn) 时间内解决问题。

另一个可能会带来更好结果的想法是使用动态规划：如果元素 x[i] 是我们解决方案的一部分，则总最小值是到达 x[i] 点的最小值加上minimum 得到最后一个点，所以你可以为每个点写一个最小的解决方案，从最小的一个开始，下一个使用他的前辈之间的最小值。

请注意，您可能需要做一些额外的工作才能从解决方案集中挑选 10 分的解决方案子集。

编辑

我用c#写了这个：

  for (int i = 0; i < 25; i++)
  {
    for (int j = i-1; j > 0; j--)
    {
      double tmpcost = solution[j].cost + Math.Abs(arr[i] - arr[j] - 0.1);
      if (tmpcost < solution[i].cost)
      {
         solution[i].previousNode = j;
         solution[i].cost = tmpcost;
      }
    }
  }

我没有做很多测试，如果25个元素中的“洞”很宽，导致解决方案少于10个元素，可能会出现一些问题......但这只是给你一些想法从事于 ：）

于 2013-08-14T09:38:10.383 回答
3

如果对点进行加权，您可以使用自适应非极大值抑制 (ANMS) 算法找到近似解。该算法选择 n 个最佳点，同时保持它们在空间上的良好分布（大部分分布在空间中）。

我想您可以根据您的分布标准分配点权重 - 例如与您选择的均匀晶格的距离。我认为格子应该有 n-1 个箱以获得最佳结果。

您可以查看以下讨论 2D 案例的论文（该算法可以在 1D 中轻松实现）：

  1. Turk、Steffen Gauglitz Luca Foschini Matthew 和 Tobias Höllerer。“有效地选择空间分布的关键点进行视觉跟踪。 ”

  2. 布朗、马修、理查德·塞利斯基和西蒙·温德。“使用面向多尺度的补丁进行多图像匹配。 ”计算机视觉和模式识别，2005。CVPR 2005。IEEE 计算机学会会议。卷。1. IEEE，2005。

第二篇论文与您的问题不太相关，但它描述了基本的 ANMS 算法。第一篇论文提供了更快的解决方案。我猜两者都将在一维中进行适度的点数（〜10K）。

于 2015-08-21T11:07:59.283 回答