algorithm - 选择均匀分布的点算法

Question

假设一条线段上有25个点，这些点可能分布(空间)不均匀，如下图所示:

我的问题是如何在这25个点中选择10个点，让这10个点在空间上尽可能均匀分布。在想法的情况下，选择的点应该是这样的:

编辑:如果我能说出证明“均匀分布”的标准，这个问题确实可以变得更优雅。我所知道的是我对所选点的期望:如果我将线段分成 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;
}

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

Answer 1

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

将范围分成 10 个大小相等的 bin。在每个 bin 中选择最接近每个 bin 中心的点。工作完成。

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

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