5

次の図に示すように、線分に 25 個の点があり、これらの点が (空間的に) 不均一に分布しているとします。 ここに画像の説明を入力

私の質問は、これらの 25 点の中から 10 点を選択して、これらの 10 点をできるだけ空間的に均等に分散させるにはどうすればよいかということです。アイデアの状況では、選択されたポイントは次のようになります。 ここに画像の説明を入力

編集： 「均等な分布」を正当化する基準を知ることができれば、この質問がより洗練されたものになることは事実です。私が知っているのは、選択した点に対する私の期待です: 線分を 10 個の等しい線分に分割した場合。小さな線分ごとに 1 つの点があるはずです。もちろん、いくつかの小さな線分では、代表点を見つけることができない場合があります。その場合、代表点を持つ隣接する小さな線分に頼ります。次のステップでは、選択した隣接セグメントをさらに 2 つの部分に分割します。各部分に代表点がある場合、空の代表点の問題は解決されます。小さい線分の 1 つに代表点が見つからない場合は、さらに小さな線分に分割できます。または、次の隣接する線分に頼ることができます。

編集: 動的プログラミングを使用すると、可能な解決策は次のように実装されます。

#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 個の同じサイズのビンに分割します。各ビンの中心に最も近い各ビンのポイントを選択します。ジョブ完了。

いずれかのビンが空であることがわかった場合は、より少ない数のビンを選択して、もう一度やり直してください。

実装しようとしている科学モデルに関する情報がなければ、(a) より適切なアルゴリズムを提案すること、および/または (b) より複雑なアルゴリズムの計算作業を正当化することは困難です。

于 2013-08-14T09:01:42.160 に答える
3

ポイントが重み付けされている場合、Adaptive Non-maximal Suppression (ANMS) アルゴリズムを使用して近似解を見つけることができます。アルゴリズムは、n 個の最適なポイントを選択し、それらを空間的に適切に分散させます (ほとんどは空間全体に分散します)。

分布基準に基づいてポイントの重みを割り当てることができると思います-たとえば、選択した均一な格子からの距離。最適な結果を得るには、ラティスに n-1 個のビンが必要だと思います。

2D ケースについて説明している次の論文を参照できます (アルゴリズムは 1D で簡単に実現できます)。

  1. Turk、Steffen Gauglitz、Luca Foschini Matthew、および Tobias Höllerer。「ビジュアルトラッキング用に空間的に分散されたキーポイントを効率的に選択します。」

  2. ブラウン、マシュー、リチャード・シェリスキー、サイモン・ウィンダー。「マルチスケール指向パッチを使用したマルチ画像マッチング。」コンピュータ ビジョンとパターン認識、2005 年。CVPR 2005。IEEE コンピュータ ソサエティ カンファレンス。巻。1. IEEE、2005 年。

2番目の論文はあなたの問題とはあまり関係がありませんが、基本的なANMSアルゴリズムについて説明しています。最初の論文は、より迅速なソリューションを提供します。適度な量のポイント（〜10K）の場合、どちらも1Dでうまくいくと思います。

于 2015-08-21T11:07:59.283 に答える
3

{x[i]} を順序付けられたポイントのセットとします。あなたがする必要があるのは、y[-1] = 0 で \sum{|y[i]-y[i-1]-0.1|} を最小化する 10 点 {y[i]} のサブセットを見つけることだと思います。 .

ここで、各ノードが 25 の double の 1 つであり、すべてのエッジのコストが |y[i]-y[i-1]-0.1| である、強く接続された有向グラフとして構成を見る場合、次のことができるはずです。ダイクストラのアルゴリズムを使用して O(n^2 +nlogn) 時間で問題を解決します。

おそらくより良い結果につながる別のアイデアは、動的計画法を使用することです。要素 x[i] が解決策の一部である場合、合計最小値は、x[i] ポイントに到達するための最小値と最後の点を取得するための最小値なので、最小のものから始めて、前任者間の最小値を次の点に使用して、各点の最小解を書くことができます。

ソリューション セットから 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 に答える